find_non_repeating_number.cpp File Reference

Implementation to find the non repeating integer in an array of repeating integers. Single Number More...

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

Include dependency graph for find_non_repeating_number.cpp:

Go to the source code of this file.

Namespaces
namespace	bit_manipulation
	for assert
namespace	find_non_repeating_integer
	Functions to find the non repeating integer in an array of repeating integers. Single Number

Functions
int64_t	bit_manipulation::find_non_repeating_integer::find_non_repeating_integer (const std::vector< int > &nums)
	The main function implements find single number.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Implementation to find the non repeating integer in an array of repeating integers. Single Number

Given an array of integers in which all of the numbers occur exactly twice except one integer which occurs only once. Find the non-repeating integer.

Worst Case Time Complexity: O(n) Space complexity: O(1)

Author

Ravidev Pandey

Definition in file find_non_repeating_number.cpp.

Function Documentation

find_non_repeating_integer()

int64_t bit_manipulation::find_non_repeating_integer::find_non_repeating_integer

(

const std::vector< int > &

nums

)

The main function implements find single number.

Parameters

nums	vector of integers

Returns

returns the integer that occurs only once

Definition at line 39 of file find_non_repeating_number.cpp.

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

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 85 of file find_non_repeating_number.cpp.

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 62 of file find_non_repeating_number.cpp.

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