Single Number ~ Coding Interview Questions With Solutions

Sunday, 28 August 2016

Single Number

Krishna Chaurasia array, bitwise, geeksforgeeks, interview, interviewbit, xor 19 comments

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Example:
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3

Approach: Take xor of all the elements. The number of terms occurring even number of times get cancelled due to property of xor that a ^ a = 0

#include<iostream>
using namespace std;

int main(){
    int arr[] = {2, 3, 3, 3, 3, 4, 2, 4, 4, 2, 4}; //{1, 2, 4, 4, 10, -8};

    int n = sizeof(arr)/sizeof(arr[0]);
    int result = 0;
    for(int i = 0 ; i < n ; i++ ){
        result = result ^ arr[i];
    }
    cout << result << " is the odd time occurring element!" << endl;
    return 0;
}