Friday, 25 May 2018

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;}

Spoj Problem ACMCEG2C - Pick the candies (C++)

  The problem link may be found here.       Explanation: Use Deque to keep track of elements of the variety of candies. If i is gre...