Find Single Non-Duplicate Number

Find Single Non-Duplicate Number

Hard C++ Operators 37 views
Explanation Complexity

Problem Statement

All numbers appear twice except one. Find that single number.
Real Life: Finding unique item in paired data.

Input Format

An integer n (size of array)
Then n integers
(All numbers appear twice except one number)

Output Format

The single number that appears only once.

Example

5
2 3 2 4 3

4

Constraints

• n is odd

• Exactly one number appears once

• All other numbers appear twice

Concept Explanation

When a number appears twice, it cancels itself using XOR.
The number that appears once remains.

Step-by-Step Explanation

1.Initialize result = 0.

2.Traverse the array from index 0 to n-1.

3.For each element arr[i]:

• Do result = result ^ arr[i].

4.Rules of XOR used:

5.x ^ x = 0

6.x ^ 0 = x

7.All paired numbers become 0.

8.The remaining value in result is the single number.

9.Print result.

Concept Explanation

When a number appears twice, it cancels itself using XOR.
The number that appears once remains.

Step-by-Step Explanation

1.Initialize result = 0.

2.Traverse the array from index 0 to n-1.

3.For each element arr[i]:

• Do result = result ^ arr[i].

4.Rules of XOR used:

5.x ^ x = 0

6.x ^ 0 = x

7.All paired numbers become 0.

8.The remaining value in result is the single number.

9.Print result.

Input / Output Format

Input Format
An integer n (size of array)
Then n integers
(All numbers appear twice except one number)
Output Format
The single number that appears only once.
Constraints
• n is odd

• Exactly one number appears once

• All other numbers appear twice

Examples

Input:
5 2 3 2 4 3
Output:
4

Example Solution (Public)

C++ 
void operator_q13_single_number() {
    int arr[] = {4, 1, 2, 1, 2, 4, 7};
    int size = 7;
    int result = 0;
    
    for(int i = 0; i < size; i++) {
        result = result ^ arr[i];
    }
    
    cout << "Single non-duplicate number: " << result << endl;
}

Official Solution Code

void operator_q13_single_number() {
    int arr[] = {4, 1, 2, 1, 2, 4, 7};
    int size = 7;
    int result = 0;
    
    for(int i = 0; i < size; i++) {
        result = result ^ arr[i];
    }
    
    cout << "Single non-duplicate number: " << result << endl;
}
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.