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:

Namespaces
namespace	bit_manipulation
	for IO operations

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

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

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

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

Here is the call graph for this function:

◆ test()

static void test ( )

static

Self-test implementations.

Returns: void

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