# PAYU Hiring Challenge 2nd Question

It is 2nd Question from Yesterday’s PayU Hiring Challenge on Hackerearth

PROBLEM

Given an array with size n and maximum value l compute

(\sum_{i=0}^{l} t_i * 31^l) % mod

where mod=10e9+7

t_i=size of maximum subset whose xor is i

If there is no subset whose xor is i then t_i=0

Constraints

n<=10^4

a[i]<=10^3

Sample Example

4

1 2 3 4

Output

3755653

Explanation

l=4

For i=0 31^0 * 3 Subset is (1,2,3)

For i=1 31^1 * 2 Subset is (2,3)

For i=2 31^2 * 2 Subset is (1,3)

For i=3 31^3 * 2 Subset is (1,2)

For i=4 31^4 * 4 Subset is (1,2,3,4)

I used DP to solve this problem but got WA

Here is link to my Solution

It would be grateful if someone can point out my mistake

Do you remember problem name?? I can look up in my submissions and check… I solved that question successfully and remember that there was some edge condition in dp… I can help easily then…

for i in range(1,n):
for j in range(0,1001):
dp[i][j]=dp[i-1][j]
for j in range(0,1001):
dp[i][a[i]^j]=max(dp[i-1][j]+1,dp[i-1][a[i]^j])

why range here is 1001 and not 1024 because xor can vary till 1024. Although a[i] <=1000 but a[i]^j can be above 1000 till 1024… no?? and this will affect when you are calculating max using dp… because you have not updated cells of j>1000…

2 Likes

Thanks a lot