Find the Number Occurring Odd Number of Times in O(n) Time (C++)

Question - We are given an Array(or vector) of integer, in which each element occurs even number of times apart from one element,which occurs odd number of times.
Our job is to find the element with odd occurrence in O(n) time complexity and O(1) Auxiliary space.

The solution is to do bitwise XOR. XOR (^) of all elements gives us odd occurring element. 

#include<bits/stdc++.h>

using namespace std;

void findOddOccuring(int arr[], int size){

int x=0; // Initializing with zero.

for(int i=0;i<size;i++){

x^=arr[i];

}

printf("The number appearing odd times is %d\n",x);

//3 occurs odd number of times.Feel free to change

// elements in the array.

}

#include<bits/stdc++.h>

using namespace std;

int main(){

int arr[]={1,2,1,3,4,4,2};

int size = sizeof(arr)/sizeof(arr[0]);

findOddOccuring(arr,size);

return 0;}

Codeforces Problem 950D - A Leapfrog in the Array (C++)

Welcome:
The question to the problem can be found here:

Explanation:

1. It is a tricky one but easy to code if you understand it.
2. using the index of the array we can solve it.
3. First lets test your attention skill. Look at the IV Figure and then the I figure.
4. If the array index number is a odd number(see input) if you add one and divide by 2, you get the required answer(the value at that index)
5. On the other hand as long as the index number is even, do x+=n- x/2.
6. Do them in Bitwise so it will reduce a lot of time to run.
7. Happy Coding.


Code:

#include<bits/stdc++.h>
using namespace std;
int main(){
long long int n,q,x;
cin>>n>>q;
while(q--){
    cin>>x;
    while(!(x&1)){
        x+=n-x/2;
    }
    cout<<(x+1>>1)<<endl;

}



return 0;}