Maximize It! HackerRank Solution

Problem

You are given a function f(X) = X². You are also given K lists. The i^th list consists of N elements.

You have to pick one element from each list so that the value from the equation below is maximized:

S = (f(X₁) + f(X₂) + … + f(X_n)) %M

X_i denotes the element picked from the i^th list. Find the maximized value S_max obtained.

% denotes the modulo operator.

Note that you need to take exactly one element from each list, not necessarily the largest element. You add the squares of the chosen elements and perform the modulo operation. The maximum value that you can obtain, will be the answer to the problem.

Input Format

The first line contains 2 space separated integers K and M.

The next K lines each contains an integer N_i, denoting the number of elements in the i^th list, followed by  space separated integers denoting the elements in the list.

Constraints

1 ≤ K ≤ 7

1 ≤ M ≤ 1000

1 ≤ N_I ≤ 7

1 ≤ Magnitude sof elements in list ≤ 10⁹

Output Format

Output a single integer denoting the value Smax.

Sample Input

3 10002 5 43 7 8 9 5 5 7 8 9 10 

Sample Output

206

Explanation

Picking 5 from the 1^st list, 9 from the 2^nd list and 10 from the 3^rd list gives the maximum S value equal to (5² + 9² + 10²) % 1000  = 206.

Solution to HackerRank Maximize It! In Python

from itertools import productK,M = map(int,input().split())N = (list(map(int, input().split()))[1:] for _ in range(K))results = map(lambda x: sum(i**2 for i in x)%M, product(*N))print(max(results))