# Hackerrank - Maximize It! Solution

You are given a function *f(X) = X ^{2}*. You are also given

*K*lists. The

*i*list consists of

^{th}*Ni*elements.

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

*S = (f(X1)+f(X2)+....+f(Xk))%M*

*Xi* denotes the element picked from the *i ^{th}* list . Find the maximized value

*Smax*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 *Ni*, denoting the number of elements in the* i ^{th}* list, followed by

*Ni*space separated integers denoting the elements in the list.

**Output Format**

Output a single integer denoting the value *Smax*.

**Sample Input**

```
3 1000
2 5 4
3 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^{2} + 9^{2} + 10 ^{2})%1000 =206.

### Solution in python

```
from itertools import product
K,M = map(int,input().split())
nums = []
for _ in range(K):
row = map(int,input().split()[1:])
nums.append(map(lambda x:x**2%M, row))
print(max(map(lambda x: sum(x)%M, product(*nums))))
```

## Answer Explanation

**Required Knowledge**

Before we get started, we must know that the follow 2 gives us equal results

(5^{2} + 9^{2} + 10 ^{2})%1000 =206

(5^{2} %1000 + 9^{2} %1000 + 10 ^{2} %1000) %1000 =206%1000 = 206

Also we should know the following python functions

- map function
- split method
- list function

**Original Answer**

The following code takes the value of K (no. of rows) and M(modulus) from the user and convert both values to integer using map() function

`K,M = map(int,input().split()) `

Then we create an empty list and name it nums, and we loop K(no. of row ) times

```
nums = []
for _ in range(K):
row = map(int,input().split()[1:])
nums.append(map(lambda x:x**2%M, row))
```

We use map and split function to convert the row input into list of integers.

```
>>> 2 5 4
[2,5,4]
>>> 3 7 8 9
[3,7,8,9]
>>> 5 5 7 8 9 10
[5,5,7,8,9,10]
```

Then we use [1:] to slice out the first number of each row because it is actually the count of items in that row and we don't need it.

2 5 4 means we have 2 numbers in our row and 5,4 are the required numbers, 3 7 8 9 means we have 3 numbers in our row and 7,8,9 are the required numbers and so and so

As required by the question we square and find the remainder(or we can say modulus) after diving the squared number by *M* for each numbers in the row and then we append that list to nums variable

`nums.append(map(lambda x:x**2%M, row))`

```
>>> list(map(lambda x:x**2%M, [5,4]))
[25,16]
>>> list(map(lambda x:x**2%M, [7,8,9]))
[49, 64, 81]
>>> list(map(lambda x:x**2%M, [5,7,8,9,10]))
[25, 49, 64, 81, 100]
```

In the above example i have added a list function just for unpacking the values inside the map function. However our code works without unpacking the values.

Now the following gives us all the possible ways of picking K numbers from our nums variable

```
>>> list(product(*nums))
[(25, 49, 25),
(25, 49, 49),
(25, 49, 64),
(25, 49, 81),
(25, 49, 100),
(25, 64, 25),
(25, 64, 49),
(25, 64, 64),
(25, 64, 81),
(25, 64, 100),
(25, 81, 25),
(25, 81, 49),
(25, 81, 64),
(25, 81, 81),
(25, 81, 100),
(16, 49, 25),
(16, 49, 49),
(16, 49, 64),
(16, 49, 81),
(16, 49, 100),
(16, 64, 25),
(16, 64, 49),
(16, 64, 64),
(16, 64, 81),
(16, 64, 100),
(16, 81, 25),
(16, 81, 49),
(16, 81, 64),
(16, 81, 81),
(16, 81, 100)]
```

Now our task is to sum each list and find the remainder after diving by M. For which we will use lambda, sum and map function

```
>>> list(map(lambda x: sum(x)%M, product(*nums)))
[99,
123,
138,
155,
174,
114,
138,
153,
170,
189,
131,
155,
170,
187,
206,
90,
114,
129,
146,
165,
105,
129,
144,
161,
180,
122,
146,
161,
178,
197]
```

And here you go, the greatest number of this list is our answer. Let's use the max function for finding the biggest number.

```
>>> print(max(map(lambda x: sum(x)%M, product(*nums))))
206
```

If you have any confusion just leave a comment below and I will try to make it clear for you.