POTD- 18/12/2023 | Game of XOR | Problem of the Day | GeeksforGeeks

Welcome to the daily solving of our PROBLEM OF THE DAY with Jay Dalsaniya. We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Data Structures and Algorithms but will also help you build up problem-solving skills.

So come along and solve the GFG POTD of 18th December 2023 with us!

Find daily solutions for POTD here on our channel! Make sure you are subscribed and stay updated.

-----------------------------------------------------------------------------------------


-----------------------------------------------------------------------------------------

Follow us and stay updated on everything happening in the world of geeks:

#GFGPractice #GeeksforGeeks #ProblemofTheDay #CodingQuestions #POTD #POTD18Dec #problemsolving #practice #dsa #GameOfXOR #BitMagic #bitmanipulation

[haha-uifp]

Decent solution and explanation, but it can be further optimised. The logic inside the loop calculates freq through multiplication to only check it's parity. That is more work than we need to do. We can instead use the fact that if any of the terms is even then their multiple will also be even. So for the if statement to be true both i+1 and n-i must be odd. Even just "if((i+1)%2!=0 && (n-i)%2!=0)" (if both are odd) is computationally simpler than doing the multiplication but we can do far better.
When is sum of a number and 1 odd? Only when the number is even. So we could just check if i is even. However even better is to just use the i definition and increment to only go through even numbers for i as clearly when i is odd we never change the result. So same result can be had with "for(int i=0; i<n; i+=2){if((n-i)%2!=0) result=result^arr[i]}" and it will have 2 times less steps in the loop as well as do 1 less comparisons for each iteration of the loop, so it'll be significantly faster when n is big.
The part of checking parity of n-i can also be optimised. We have already determined that i is even. Subtracting an even number never changes the parity, so for even i's (n-i)%2==n%2. Now n is a constant in our program and doesn't change in the loop, so instead of checking that n times inside the loop we could check it once outside of it and only run the loop when n is odd. When n is even the result will always be 0. The resulting optimised program will look a bit like:

if(n%2 == 0) return 0;
int result = 0;
for(int i=0; i<n; i+=2)
result ^= arr[i];
return result;

If looked through big O notation the time and space complexity stay pretty much the same (O(n) and O(1) respectively). But de facto most of the calculation power were used by the long and somewhat convoluted logic inside the loop, whereas in the optimised solution each step of the loop is about as lean and concise as possible. If checked on compiler explorer the resulting compiled program for optimised version is 8 instructions or 21% shorter than what was initially(30 instead of 38), but more importantly the loop goto changes from "34: goto 4", i.e. 30 instructions for each of n steps, into "26: goto 12", i.e. 14 simpler instructions or less than half as well as the number of iterations is also almost halved.