Repeated number in array

Repeated number in an array

In last post : Find missing number in array, we learned how to find a missing number in array of integers with values in a given range. Today, we will learn how find a repeated number in array of integers from 1 to N. Note that here also, numbers are not sorted but are confined to a range. So, if size of array is N, then range of numbers is from 1 to N-1 as one number is repeated. Examples :

A = [1,2,3,3,4,5]. Repeated number is 3
Size of array : 6 Range : 1 to 5

Repeated number : Algorithm

As we have learned while solving the missing number problem earlier, XOR principle can be applied here too. Why? Because in this case repeated number will be XORed with itself three times. Properties of XOR to understand the method and how we use them.

A XOR A = 0
0 XOR A = A

Now, when a number XORed with itself, the result is zero, and when zero is XORed with a number, the result is the number itself. Extending this, if we XORed the same number thrice or without losing generality, an odd number of times, the result will be the number itself.

Using an odd number of times XOR principle, algorithm to find repeating number in an array.

1. XOR all actual numbers in the array. Call it aXOR.
2. XOR all numbers in range 1 to N-1. Call it eXOR
3. XOR aXOR with eXOR. Result will be repeated number.

This is because all numbers except the repeated number will be XORed even number of times, and cancel each other. The repeated number will be XORed thrice, the final result will be the repeated number. Let’s take above example and see if it works

A = [1,2,2,3,4]

aXOR = 001 XOR 010 = 011 XOR 010 = 001 XOR 011 = 010 XOR 100 = 110
eXOR = 001 XOR 010 = 011 XOR 011 = 000 XOR 100 = 100

ActualXOR XOR expectedXOR = 110 XOR 100 = 010

Repeated number in array implementation

public int repeatedNumber(int[] nums) {
 
    int n =  nums.length;
     
    int nXOR = 0;
    for(int i=0; i<=n; i++){
        nXOR ^= i;
    }
     
    int aXOR = 0;
    for(int i=0; i<n; i++){
        aXOR ^= nums[i];
    }
     
    return aXOR ^ nXOR;
}

The time complexity of the XOR method to find a repeated number in an array is O(n).

Please share your thoughts through comments, if you see something is missing or wrong or not explained properly.

Find a missing number in array

Missing number in an array

Given an array of N integers, ranging from 1 to N+1, find the missing number in that array. It is easy to see that with N slots and N+1 integers, there must be a missing number in the array. For example, A = [1,2,5,4,6] N = 5 range 1 to 6. The output is 3.
A = [1,5,3,4,7,8,9,2] N = 8 range 1 to 9. Output is 6

Methods to find a missing number

Using hash
Create a hash with the size equal to N+1. Scan through elements of the array and mark as true in the hash. Go through the hash and find a number which is still set to false. That number will be the missing number in the array.
The complexity of this method is O(n) with additional O(n) space complexity.

Using mathmatics
We know that the sum of N consecutive numbers is N*(N+1)/2. If a number is missing, the sum of all numbers will not be equal to N*(N+1)/2. The missing number will be the difference between the expected sum and the actual sum.

Missing num = (N+2) * (N+1) /2 – Actual sum; N+1 because the range of numbers is from 1 to N+1
Complexity is O(n). However, there is a catch: there may be an overflow risk if N is big enough.

Using XOR
There is a beautiful property of XOR, that is: if we XOR a number with itself, the result will be zero. How can this property help us to find the missing number? In the problem, there are two sets of numbers: the first one is the range 1 to N+1, and others which are actually present in the array. These two sets differ by only one number and that is our missing number. Now if we XOR first set of numbers with the second set of numbers, all except the missing number will cancel each other. The final result will be the actual missing number.

Algorithm to find a missing number using XOR

1. Scan through the entire array and XOR all elements. Call it aXOR
2. Now XOR all numbers for 1 to N+1. Call it eXOR
3. Now XOR aXOR and eXOR, the result is the missing number

Let’s take an example and see if this works

A = [1,3,4,5] Here N = 4, Range is 1 to 5.

XORing bit representations of actual numbers
001 XOR 011 = 010 XOR 100 = 110 XOR 101 = 011 (aXOR)

XORing bit representation of expected numbers
001 XOR 010 = 011 XOR 011 = 000 XOR 100 = 100 XOR 101 = 001 (eXOR)

Now XOR actualXOR and expectedXOR;
011 XOR 001 = 010 = 2 is the missing number

Implementation

    public int missingNumber(int[] nums) {
    
        int n =  nums.length;
        
        int nXOR = 0;
        for(int i=0; i<=n; i++){
            nXOR ^= i;
        }
        
        int aXOR = 0;
        for(int i=0; i<n; i++){
            aXOR ^= nums[i];
        }
        
        return aXOR ^ nXOR;
    }

The complexity of the XOR method to find a missing number in an array of integers is O(n) with no additional space complexity.

If you want to contribute to this blog in any way, please reach out to us: Contact. Also, please share if you find something wrong or missing. We would love to hear what you have to say.