HackerRank Solution: Maximize it [Python Itertools]

Question: Maximize it [Python Itertools]

You are given a function f(X) = X2. You are also given K lists. The ith list consists of 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 ith 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 contain an integer Ni, denoting the number of elements in the ith list, followed by Ni space-separated integers denoting the elements in the list.

Constraints:

1 <= K <= 7
1 <= M <= 1000
1 <= Ni <= 7
1 <= Magnitude of elements in list <= 109

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 1st list, 9 from the 2nd list, and 10 from the 3rd list gives the maximum S value equal to (52 + 92 + 102 ) % 1000 = 206.

 

Possible solutions

Now we will discuss different possible solutions to the Maximize it problem on HackerRank. Here we will go through three different solutions;

1. Using operator module
2. Using itertools module
3. Without using any modules

 

Solution-1: Using operator module

Let us first solve the problem using operator module and then we will explain the code:

from itertools import product,starmap
from operator import mul

def dotproduct(vec1, vec2):
    "Compute a sum of products."
    return sum(starmap(mul, zip(vec1, vec2)))

K, M = map(int,input().split())
N_list = []


for _ in range(K):
    N_i, N = input().split(" ",1)
    N_list.append(list(map(int,N.split())))
    
max_S = 0
for x in product(*N_list):
   S = dotproduct(x,x)%M
   if S > max_S:
    max_S = S
    
print(max_S)

This code computes the dot product of two lists of integers, modulo a given number M, and returns the maximum result among all possible combinations of elements from the two lists. The two lists are input by the user, with the length of each list specified first. The elements of the lists are then input on subsequent lines. The itertools module's product function is used to generate all possible combinations of elements from the lists, and the dotproduct function uses the starmap function from itertools and the mul function from the operator module to compute the dot product of each combination. The maximum value of the dot product, among all the combinations, is then printed.

 

Solution-2: Using itertools module

Now we will only use itertools module to solve the problem:

import itertools

line = input()
K = int(line.split()[0])
M = int(line.split()[1])

N = []
for i in range(K):
  lst = input().split()
  lst = [ int(n) for n in lst ]
  lst = lst[1:]
  N.append(lst)

pro = list( itertools.product( *N ) )

maxi = 0
for item in pro:
  sum=0
  for num in item:
    sum += num**2
  modu = sum % M
  if (modu > maxi):
    maxi = modu

print (maxi) 

This code computes the dot product of two lists of integers, modulo a given number M, and returns the maximum result among all possible combinations of elements from the two lists. The length of the lists and the value of M are input by the user on the first line, and the elements of the lists are input on subsequent lines. The itertools module's product function is used to generate all possible combinations of elements from the lists, and a for loop is used to compute the dot product of each combination. The maximum value of the dot product, among all the combinations, is then printed.

 

Solution-3: Without using any module

Now, we will not use any module to solve the problem. We will write the code by ourselves.

rows,modus = map(int,input().split())
matrix = [tuple(set(map(int,input().split()[1:]))) for _ in range(rows)]
sq = lambda x : x**2
pair_wise = [[]]

max_value = sum(map(sq, map(max,matrix)))

if max_value < modus:
    print(max_value%modus)
else:
    for tups in matrix:
        pair_wise = [braces+[sq(items)] for braces in pair_wise for items in tups]
    pair_wise = [sum(item)%modus for item in pair_wise]
    max_value = max(pair_wise)
    print(max_value)

This code computes the maximum possible dot product of a list of tuples of integers, modulo a given number modus. The number of tuples in the list and the value of modus are input by the user on the first line, and the elements of the tuples are input on subsequent lines. The code first computes the maximum possible dot product by finding the maximum element in each tuple, squaring it, and summing the squares. If this value is less than modus, it is printed. Otherwise, the code generates all possible combinations of the elements in the tuples using a list comprehension, computes the dot product of each combination, and prints the maximum value among these dot products, which is taken modulo modus.

 

Summary

In this short article, we discussed how we can solve the Maximize it problem on HackerRank using various methods. In this article, we showed you three different methods to solve the problem.

 

Further readings

Question on hacker rank: Maximize It! [Python itertools]