Gray Similar Code

#1

To apply Binary search we have to sort elements of given array from k+1 to N, but if we sort the given array let’s say for some k, wouldn’t the array lose its original order?
I can’t figure out how can we possibly apply Binary Search.

#2

hello @subhamjaiswal885

for n<=130
we can fix first three numbers using three loop(say a[i],a[j],a[k]).
and to check whether their exist fourth number such a[i]^[j]^a[k]^fourthNUmber=0
we can use binary search on given array to find fourthNUmber= a[i]^[j]^a[k].

sorting will change the order but it will not affect the answer.
this is what we are asked to find->
Your task is to check whether there exist 4 numbers A[i1], A[i2], A[i3], A[i4] (1 <= i1 < i2 < i3 < i4 <= n) out of the given n numbers such that A[i1] xor A[i2] xor A[i3] xor A[i4] = 0 . Here xor is a bitwise operation which is same as ^ in C, C++, Java and xor in Pascal.

#3

Let’s say we have an array of 8 elements arr[]={x1,x2,x3,x4,x5,x6,x7,x8}
We apply nested for loop:
for(int i=1;i<=5;i++)
{
for(int j=i+1;j<=6;j++)
{
for(int k=j+1;k<=7;k++)
{
x=A[i]^A[j]^A[k]

        we will find x in A[k+1.....8].
        Here A[k+1....8] will be sorted.
    }
}

}
Now suppose we did not find the required x in this interval. k will be incremented by one position and we will start the search for this new x again in A[k+1 … 8]. Now suppose we did find the required x. So the output should be “Yes”. But how can we be sure that A[k] actually occurred before x in the original array too i.e, i1 < i2 < i3 < i4 order is maintained?

#4

bro sort the array before the nested loops.
and thrn use bs. on range [k+1…n-1]

#5

your pick any four number. then its obvious than one of then will occur at first then another number and then another number.

this condition is redundant , it will always hold

#6

Finally, understood where i was making mistake. Thanks a lot brother!!!

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.