find_non_repeating_number.cpp

Go to the documentation of this file.

 
#include <cassert>   
#include <iostream>  
#include <vector>    

namespace bit_manipulation {
namespace find_non_repeating_integer {
int64_t find_non_repeating_integer(const std::vector<int>& nums) {
    // The idea is based on the property of XOR.
    // We know that 'a' XOR 'a' is '0' and '0' XOR 'b'
    // is b.
    // Using this, if we XOR all the elements of the array,
    // the repeating elements will give '0' and this '0'
    // with the single number will give the number itself.
 
    int _xor = 0;
 
    for (const int& num: nums) {
        _xor ^= num;
    }
 
    return _xor;
}
}  // namespace find_non_repeating_integer
}  // namespace bit_manipulation

static void test() {
    // n = 10,2 return 14
 
    std::vector<int> nums_one{1, 1, 2, 2, 4, 5, 5};
    std::vector<int> nums_two{203, 3434, 4545, 3434, 4545};
    std::vector<int> nums_three{90, 1, 3, 90, 3};
 
    assert(bit_manipulation::find_non_repeating_integer::
               find_non_repeating_integer(nums_one) ==
           4);  // 4 is non repeating
    assert(bit_manipulation::find_non_repeating_integer::
               find_non_repeating_integer(nums_two) ==
           203);  // 203 is non repeating
    assert(bit_manipulation::find_non_repeating_integer::
               find_non_repeating_integer(nums_three) ==
           1);  // 1 is non repeating
 
    std::cout << "All test cases successfully passed!" << std::endl;
}

int main() {
    test();  // run self-test implementations
    return 0;
}