Tagged
• DSA Problems
• 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| <= 200000010
110 <= nums[i] <= INTMAX12
13Input:  nums = [1, 2, 2, 3, 1]14
15Output: 3```

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

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

# Naïve Solution

## Algorithm

```1Step 1 : For each element "ele" in array2
3Step 2 : Initialize count to 04
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 element8
```

## Code Implementation

1. Java
2. Python
3. Go

```1public class SingleNumberUsingNaiveSol {2
3    // method to find single number in the given array4    // array contains every number two times except one5    public int getSingleNumber(int[] nums) {6        // Iterate through array7        for(int i=0;i<nums.length;i++) {8            // for each element in the array9            // Initialize count to 010            int count = 0;11            // Iterate through array12            for(int j=0; j<nums.length; j++){13                // if there is a match, increment the count14                if(nums[i] == nums[j]) {15                    count++;16                }17            }18            // if count is 1, that is the single element19            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

## 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 04
5Step 1: Sort the array6
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 210Step 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

1. Java
2. Python
3. Go

```1import java.util.Arrays;2
3public class SingleNumberSolUsingSorting {4
5    // method to find single number in the given array6    // array contains every number two times except one7    public int getSingleNumber(int[] nums) {8        // Sort the array9        Arrays.sort(nums);10        int n = nums.length;11
12        // Iterate through array13        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 once17            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 number22       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

## 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 array4
5Step 1: for each element ele in the array6
7Step 2: if ele is not present in the map, insert into map with count 18
9Step 3: else : increment the value of the entry by 110
11Step 4: For each entry in map12
13Step 5: If the entry value is 1 return the entry key14
15Output : single number in the array ```

## Code Implementation

1. Java
2. Python
3. Go

```1import java.util.HashMap;2import java.util.Map;3
4public class SingleNumberSolUsingMap {5
6    // method to find single number in the given array7    // array contains every number two times except one8    public int getSingleNumber(int[] nums) {9        // Initialize Map10        // Key is element in the array11        // Value is number of occurrences of the element in the array12        Map<Integer, Integer> counterMap = new HashMap<>();13
14        // Iterate through array and insert into map15        // If key already exists in map increment the value by 116        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 map21        for(Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {22            // If any element occurs once, that is the answer23            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

## 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 03Step 1: for each element ele in the array4Step 2: result = result ^ ele (xor current element with result)5Output : result `

## Code Implementation

1. Java
2. Python
3. Go

```1public class SingleNumberSol {2
3    // method to find single number in the given array4    // array contains every number two times except one5    public int getSingleNumber(int[] nums) {6        // Initialize result to 07        int result = 0;8
9        // Iterate through array and XOR with result10        for(int i=0;i<nums.length;i++) {11            result = result ^ nums[i];12        }13
14        // return the output15        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

ApproachTime ComplexitySpace ComplexityRemarks
Naïve SolutionO(n²)O(1)Iterating array in a loop
Using SortingO( n * log(n) )O(1)Sorting Algorithm Complexity
Using MapO(n)O(n)Map uses extra space
Using Bitwise XORO(n)O(1)Applies Bitwise XOR by traversing the array

• DSA Problems
• Array
•
...