PAYU Hiring Challenge 2nd Question

general
, , ,
1

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 :slight_smile:

2

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… :slight_smile:

3

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
4

Thanks a lot :slight_smile: