Tagged

Single Number in an Array

Problem Statement

1Problem Description : Given an array of integers nums, every element appears twice except for one. Find that single one.
2
3NOTE : Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
4
5Problem Constraints :
6
7Each element in the array appears twice except for one element which appears only once.
8
91 <= |nums| <= 2000000
10
110 <= nums[i] <= INTMAX
12
13Input:  nums = [1, 2, 2, 3, 1]
14
15Output: 3

1Example 1
2  Input : nums = [1, 2, 2, 3, 1]
3
4  Output: 3
5
6  Explanation : Every number in the given array appeared two times except number 3

1Example 1
2  Input : nums = [2,2,1]
3
4  Output: 1
5
6  Explanation : number 1 appeared only once

Solution Approaches

Naïve Solution

Algorithm

1Step 1 : For each element "ele" in array
2
3Step 2 : Initialize count to 0
4
5Step 3 : Iterate through array and increment count if the array element matches with "ele"
6
7Step 4 : If count is equal to 1 return the element
8

Code Implementation

Java
Python
Go

1public class SingleNumberUsingNaiveSol {
2
3    // method to find single number in the given array
4    // array contains every number two times except one
5    public int getSingleNumber(int[] nums) {
6        // Iterate through array
7        for(int i=0;i<nums.length;i++) {
8            // for each element in the array
9            // Initialize count to 0
10            int count = 0;
11            // Iterate through array
12            for(int j=0; j<nums.length; j++){
13                // if there is a match, increment the count
14                if(nums[i] == nums[j]) {
15                    count++;
16                }
17            }
18            // if count is 1, that is the single element
19            if(count == 1) {
20                return nums[i];
21            }
22        }
23        return -1;
24    }
25
26    public static void main(String[] args) {
27        SingleNumberUsingNaiveSol obj = new SingleNumberUsingNaiveSol();
28        int[] nums1 = {1, 2, 2, 3, 1};
29        System.out.println(obj.getSingleNumber(nums1));
30
31        int[] nums2 = {2, 2, 1};
32        System.out.println(obj.getSingleNumber(nums2));
33
34        int[] nums3 = {1, 2, 3, 3, 4, 1, 4, 5, 6, 6, 5};
35        System.out.println(obj.getSingleNumber(nums3));
36    }
37}

Complexity Analysis

Time Complexity : O(n²)
Space Complexity : O(1)

Using Sorting

Prerequisite

Sorting

Intuition

If the array is sorted, the elements which are occurred twice are always next to each other. So in the array we can compare the elements in pairs (compare nums[i] with nums[i+1] for i = 0, 2, 4 and so on). If we find any scenario where the pairs does not match, first element in the pair is the single one in the array.

Algorithm

1Input : Array of Integers 
2
3Step 0: Initialize i to 0
4
5Step 1: Sort the array
6
7Step 2: if i < n-1 (where n is array's length)
8
9Step 3: If nums[i] equals to nums[i+1]  increment i by 2 and Repeat from Step 2
10Step 4: else return nums[i]
11
12Step 5: As i = n-1 and no element left to compare, so nums[i-1] is the single number 
13
14Output : single number present in the array

Code Implementation

Java
Python
Go

1import java.util.Arrays;
2
3public class SingleNumberSolUsingSorting {
4
5    // method to find single number in the given array
6    // array contains every number two times except one
7    public int getSingleNumber(int[] nums) {
8        // Sort the array
9        Arrays.sort(nums);
10        int n = nums.length;
11
12        // Iterate through array
13        for(int i=0; i<n-1; i=i+2) {
14            // compare num[i] with nums[i+1]
15            // If nums[i] not equal to nums[i+1]
16            // nums[i] is the number which occured only once
17            if(nums[i] != nums[i+1]) {
18                return nums[i];
19            }
20        }
21        // As i = n-1 and no element left to compare, so this is the single number
22       return nums[n-1];
23    }
24
25    public static void main(String[] args) {
26        SingleNumberSolUsingSorting obj = new SingleNumberSolUsingSorting();
27        int[] nums1 = {1, 2, 2, 3, 1};
28        System.out.println(obj.getSingleNumber(nums1));
29
30        int[] nums2 = {2, 2, 1};
31        System.out.println(obj.getSingleNumber(nums2));
32
33        int[] nums3 = {1, 2, 3, 3, 4, 1, 4, 5, 6, 6, 5};
34        System.out.println(nums3.length);
35        System.out.println(obj.getSingleNumber(nums3));
36    }
37
38}

Complexity Analysis

Time Complexity : O(n log (n) ) :
- To sort the array O(n log n)
- Single traversal to find the single element after sorting O(n)
So Time complexity is O(n log n) + O(n) = O(n log n)
Space Complexity : O(1)

Using Map

Prerequisite

Understanding about Map

Intuition

It is given that every element in the array appears two times except one and we have to find that single element. It means the number of occurrences of unique elements in the array will be 2 except for one element whose count will be 1. So by counting the number of occurrences we will be able to find the single number present in the given array. To achieve this we can use either a counter array or a map.

Algorithm

1Input : Array of Integers 
2
3Step 0: Initialize a map to store key values pairs, here key is array element and value is occurrence of the element in the array
4
5Step 1: for each element ele in the array
6
7Step 2: if ele is not present in the map, insert into map with count 1
8
9Step 3: else : increment the value of the entry by 1
10
11Step 4: For each entry in map
12
13Step 5: If the entry value is 1 return the entry key
14
15Output : single number in the array

Code Implementation

Java
Python
Go

1import java.util.HashMap;
2import java.util.Map;
3
4public class SingleNumberSolUsingMap {
5
6    // method to find single number in the given array
7    // array contains every number two times except one
8    public int getSingleNumber(int[] nums) {
9        // Initialize Map
10        // Key is element in the array
11        // Value is number of occurrences of the element in the array
12        Map<Integer, Integer> counterMap = new HashMap<>();
13
14        // Iterate through array and insert into map
15        // If key already exists in map increment the value by 1
16        for(int i=0;i<nums.length;i++) {
17            counterMap.put(nums[i], counterMap.getOrDefault(nums[i], 0)+1);
18        }
19
20        // Iterate through counter map
21        for(Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
22            // If any element occurs once, that is the answer
23            if(entry.getValue() == 1) {
24                return entry.getKey();
25            }
26        }
27        return -1;
28    }
29
30    public static void main(String[] args) {
31        SingleNumberSolUsingMap obj = new SingleNumberSolUsingMap();
32        int[] nums1 = {1, 2, 2, 3, 1};
33        System.out.println(obj.getSingleNumber(nums1));
34
35        int[] nums2 = {2, 2, 1};
36        System.out.println(obj.getSingleNumber(nums2));
37
38        int[] nums3 = {1, 2, 3, 3, 4, 1, 4, 5, 6, 6, 5};
39        System.out.println(obj.getSingleNumber(nums3));
40    }
41
42}

Complexity Analysis

Time Complexity : O(n)
Space Complexity : O(n)

Using Bitwise XOR

Prerequisite

Bitwise Operators

Intuition

It is given that every element in the array appears two times except one and we have to find the number which occurs only once. So the numbers which are appeared two times has to be nullified by doing some operation so that we left with single number. If we notice Bitwise XOR does the same job.

Algorithm

1Input : Array of Integers 
2Step 0: Initialize result variable as 0
3Step 1: for each element ele in the array
4Step 2: result = result ^ ele (xor current element with result)
5Output : result

Code Implementation

Java
Python
Go

1public class SingleNumberSol {
2
3    // method to find single number in the given array
4    // array contains every number two times except one
5    public int getSingleNumber(int[] nums) {
6        // Initialize result to 0
7        int result = 0;
8
9        // Iterate through array and XOR with result
10        for(int i=0;i<nums.length;i++) {
11            result = result ^ nums[i];
12        }
13
14        // return the output
15        return result;
16    }
17
18    public static void main(String[] args) {
19        SingleNumberSol obj = new SingleNumberSol();
20        int[] nums1 = {1, 2, 2, 3, 1};
21        System.out.println(obj.getSingleNumber(nums1));
22
23        int[] nums2 = {2, 2, 1};
24        System.out.println(obj.getSingleNumber(nums2));
25
26        int[] nums3 = {1, 2, 3, 3, 4, 1, 4, 5, 6, 6, 5};
27        System.out.println(obj.getSingleNumber(nums3));
28    }
29
30}

Complexity Analysis

Time Complexity : O(n)
Space Complexity : O(1)

Approaches Comparison

Approach	Time Complexity	Space Complexity	Remarks
Naïve Solution	O(n²)	O(1)	Iterating array in a loop
Using Sorting	O( n * log(n) )	O(1)	Sorting Algorithm Complexity
Using Map	O(n)	O(n)	Map uses extra space
Using Bitwise XOR	O(n)	O(1)	Applies Bitwise XOR by traversing the array

DSA Problems

Array

Closet Pair of Points

Flow Charts

...