Mahmoud and Ehab DP Concept Doubt

#21

Bhaiya, iss problem meh X ka max value ho sakta hai, maxXOR=(1<<20)+1
aur N=100005 hoga, right?

#22

ha. . … . . . . . . . .

#23

Bhaiya, abhi next kya karna hai…Naive approach to bana liye…

#24

a) watch video again.
b) try this problem again
c) read the editorial
see others code

#25

Bhaiya, video meh set se samjhaya hai…set use kiya hai.
Aur editorial meh jo likha hai whi bistaar se samjhaya hai in the video using set.

So fir se dekhu?

#26

depends on u bro.
tum jaise bhi karna chahte ho .
mein clarity ke liye chize repeat karta hu isiliye bol raha tha

#27

Bhaiya, since numbers range uptil 2^20, so XOR ka range bhi uptil 2^20 hi hoga…?
Kyun, isse jada bhi ho sakta hai na…

#28

worst case mein kya hoga ?
xor ki saari bits set ho right?
kyunki 20 bit number hai worst case mein xor 2^20 hi hoga na

1 Like
#29

Bhaiya, dp[0][0] = 1 kyun hai?
Aur empty set ka XOR ka value 1 hoga ya 0 hoga?

#30

bro :roll_eyes:?
dp[0][0] =1 becuase empty set ka xor 0 hota hai

#31

toh fir, do obsevation…

  1. dp[i][j]=0 hoga when i=0 & j!=0
  2. dp[i][j]=0 hoga when j=0 & i!=0

yah kya sahi hai?

#32

ye sahi nahi hai,
kuch element milke xor zero bana sakte hain.
example->
[3,3,4]
yaha pe dp[2][0]!=0 because {3^3 =0}

#33

Accha isiliye for loop meh i ka value 1 se suru kiya hai.
Kyun ki, 0th row ke lea dp[i][j] ka value 0 hi rahega except dp[0][0]=1.

Magar, 0th column ke le bol nhi sakte esa in dp[i][j] table…

#34

ha…
…
…

#35

Bhaiya, so naive approach le rha hai, O(10^5*2^20) time complexity which is bad.
Optimised Approach: Using SET

  1. We create a set of XOR values from the given array of elements using 2 properties.

    a. if a[i] is present in the set then (x XOR a[i]) is also present in the set for some values of x which has already present in the set.

    b. if a[i] is not present in the set then irrespective of values of x is present or not, (x XOR a[i]) is also not present in the set.

Aur yah set jo bana rhe hai only by the elements of the array and not taking any values form l and x or queries.

#36

ha… ,…

#37

Bhaiya, tab agar input meh diya hai L ka value, magar iska koi kam nhi aya…L ka mtlb hai first L elements in the array…

#38

ha solution mein iska role nahi tha.
but last me hum usi ka answer batayenge.

#39

Bhaiya, tab maan lijiye esa bhi toh ho sakta tha ki X ka value same mila magar L ka value same nhi mila…aur hume iske bare meh pata bhi nai chalega kyun ki L ka koi role hi nhi hai iss solution meh so esa case kya ban nhi sakta!!

#40

ha to ye to consider kiya hi hai humne recurrence mein.

bro ek barr phir se video + editorial dekh lo