×

# PAYU Hiring Challenge 2nd Question

 0 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 :-) asked 07 Aug '17, 12:20 4★anushi 246●1●7 accept rate: 15% 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.. :) (07 Aug '17, 13:42)

 2 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.. answered 07 Aug '17, 13:56 1.1k●1●10 accept rate: 19% Thanks a lot :-) (07 Aug '17, 20:33) anushi4★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,212
×858
×398
×5

question asked: 07 Aug '17, 12:20

question was seen: 492 times

last updated: 07 Aug '17, 20:33