top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Single Number - InterviewBit Solution

Problem: Single Number


Problem Description

Given an array of integers A, every element appears twice except for one. Find that single one. NOTE: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


Problem Constraints

  • 2 <= |A| <= 2000000

  • 0 <= A[i] <= INTMAX

Input Format

The first and only argument of input contains an integer array A.


Output Format

Return a single integer denoting the single element.


Example Input

Input 1: A = [1, 2, 2, 3, 1] Input 2: A = [1, 2, 2]


Example Output

Output 1: 3 Output 2: 1

Example Explanation

Explanation 1:
3 occurs once. 

Explanation 2:
1 occurs once.

Solution Approach:

  • If we Xor a number with itself it returns 0. That means a^a = 0

  • If we Xor any number with zero we get that number itself. That means a^0 = a.

Considering the above two points we can get the unique number if we xor all the elements of the given array.



Solution:

Code in C++:

If you have any questions or queries, feel free to drop a comment in the comments section below.


Comments


bottom of page