Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Problem
1.2.1.
Example 1
1.2.2.
Example 2
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation
2.2.1.
C++
2.2.2.
Python
2.2.3.
Complexity Analysis
3.
Optimised approach 1
3.1.
Pseudocode
3.2.
Implementation
3.2.1.
C++
3.2.2.
Python
3.2.3.
Complexity Analysis
4.
Optimised approach 2
4.1.
Pseudocode
4.2.
Implementation
4.2.1.
C++
4.2.2.
Complexity Analysis
5.
Optimised approach 3
5.1.
Pseudocode
5.2.
Implementation
5.2.1.
C++
5.2.2.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What are the different sorting algorithms that can be used in the above approach?
6.2.
What are bitwise operators?
6.3.
What is the difference between bitwise xor and bitwise or?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find the missing and repeating number in an array

Author Akshit Mehra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will be discussing the problem of finding the missing and repeating element in an array, given all the elements are in the range of 1 to n (size of the array). Here, we will discuss four approaches:

  1. Brute force: We will use a naive approach with two loops.
  2. Count array-based: In this approach, we will discuss an O(n) approach. Here, we use the array elements as the index itself.
  3. Sorting based: This is an efficient approach that uses the concept of sorting.
  4. Bitwise xor based: Here, we use the concept of Bitwise xor.

Bitwise xor: BItwise xor is a bit operation in which the resultant number has a set bit at the position if and only if one of the numbers has that bit set and another one unset. Below is an illustration of bitwise xor

X

Y

X ^ Y 

0

0

0

1

0

1

0

1

1

1

1

0

 

We hope you enjoy learning the concept in the provided blog.

Problem Statement

The problem above states that:

Given an unsorted array of size n, all the elements are in the range of 1 - n. Now, one of the elements in the provided array is missing while one of them is repeated. Find these two elements.

Sample Problem

Example 1

Input 1:

arr[] = {5,4,3,2,2}

 

Output 1:

Repeating: 2, Missing: 1

 

Explanation: In the above array, we see that element 2 is repeated while element 1 is missing.

Example 2

Input 2

arr[] = {1,5,4,6,1,3,2}

 

Output 2: 

Repeating: 1, Missing: 7

 

Explanation: In the above example, we see that element 1 is repeating while element 7 is missing.

Also see,  Rabin Karp Algorithm

Brute Force Approach

A brute force approach for the above problem involves running two loops:

  1. As the elements are in the range of 1…n, we run our first loop from 1..n.
  2. We maintain a count variable that counts the number of times the element is in the array.
  3. Check the count variable. If the count is 0, the corresponding element is missing. If it is greater than 1, the element is a repeating element.

Pseudocode

missing = 0
repeating  = 0
For i = 1 to n:
	count  = 0
	For j = 0 to n:
		If arr[j] is equal to i:
			count = count + 1
	If count is equal to 0:
		missing = i
	If count is greater than 1:
		repeating = i

Implementation

C++

#include "bits/stdc++.h"
using namespace std;

void solve()
{
   //Below is the array
   int arr[] = {1,2,2,3,5};

   //Defining the size of the array
   int n = sizeof(arr)/sizeof(int);

   //Missing Number
   int miss = 0;
  
   //Repeating Number
   int rep = 0;

   //Running the first loop checking for the number
   for(int i = 1;i<=5;i+=1){

       //Below is the count variable
       int cnt = 0;

       //Second Loop for checking the number in the array
       for(int j = 0;j<5;j+=1){

           if(arr[j] == i){
               cnt+=1;
           }
       }
       if(cnt == 0){
           miss = i;
       }
       if(cnt == 2){
           rep = i;
       }
   }

   cout<<"Missing Number: " << miss << '\n';
   cout << "Repeating Number: " << rep;
}
int main()
{
   solve();
   return 0;
}

 

Output

Missing Number:  4
Repeating Repeating:  2

Python

def solve(arr, len_):
   
    #Variable for missing and repeating element   
    miss = 0
    rep = 0
    
    #Looping over all the elements
    for i in range(1,len_+1):
        
        #Maintaining a count variable for count of each number
        count = 0
        for j in range(len_):
            if arr[j] == i:
                count+=1
        #If count of i is 0, then it did no occured.
        if count == 0:
            miss = i
        else:
            
            #If count is 2, then the element is repeated.
            if count == 2:
                rep = i


    print("Repeating Element: ", rep)
    print("Missing Element: ", miss)
    
arr = [1,2,3,3,5]
n = len(arr)
solve(arr, n)

 

Output

Repeating Element:  3
Missing Element:  4

Complexity Analysis

Time complexity: O(n2)

The time complexity for the above code is n2 as we have two nested loops applied.

Space complexity: O(1)

As in the above approach to solve the problem, we haven’t used any extra space for solving it. Therefore, the space complexity is O(1), i.e. constant.

Also Read - Selection Sort in C

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimised approach 1

An efficient approach for solving the above problem is maintaining a count array. Here, count[i] will maintain the count of element i. If count[i] > 1, then the element is repeating. If the count[i] is 0, the element is missing. Below is the solution:

  1. Traverse the array and increment count[arr[i]] as we get on arr[i].
  2. After noting the count of each arr[i], traverse the count array.
  3. If the count[i] > 1 for some i, then it is the repeating element.
  4. If the count[i] is 0 for some i, then it is the missing element.

Pseudocode

count[n];
for i = 1 to n:
	count[i] = 0
for i = 1 to n:
	count[arr[i]]++
a = 0, b = 0
for i = 1 to n:
	If count[i] is equal to 0:
		a = i
	If count[i] is greater than 1:
		b = i

Implementation

C++

#include "bits/stdc++.h"
using namespace std;

void solve()
{
   //Below is the array
   int arr[] = {1,2,2,3,5,6,7};

   //Defining the size of the array
   int n = sizeof(arr)/sizeof(int);

   //Missing Number
   int miss = 0;
  
   //Repeating Number
   int rep = 0;

   //Below is the count array initialised with 0's
   int count[n];
   memset(count, 0, sizeof(count));

   for(int i = 0;i<n;i+=1){
       count[arr[i]-1]+=1;
   }
   for(int i = 0;i<n;i+=1){
       if(count[i] == 0){
           miss=i+1;
       }
       if(count[i] == 2){
           rep = i+1;
       }
   }
   cout<<"Missing Number: " << miss << '\n';
   cout << "Repeating Number: " << rep;
}
int main()
{
   solve();
   return 0;
}

 

Output

Missing Number: 4
Repeating Number: 2

Python

def solve(arr, len_):
   
   #Maintaining a count array
    count  = [0]*n
    
    #Incrementing the count
    for i in range(len_):
        count[arr[i]-1]+=1
    
    #Variables for missing and repeating element
    miss = 0
    rep = 0
    
    for i in range(len_):
        #If count is 0, therefore the element is missing
        if count[i] == 0:
            miss = i+1
        
        #If an element is repeating, then its count is 2.
        if count[i] == 2:
            rep = i+1


    print("Repeating Element: ", rep)
    print("Missing Element: ", miss)
    
# Driver program to test above function */
arr = [1,2,3,3,5]
n = len(arr)
solve(arr, n)

 

Output

Repeating Element:  3
Missing Element:  4

Complexity Analysis

Time complexity: O(n)

As in the above approach, we use two loops of O(n) time complexity. Therefore, the final time complexity is O(2n), which is O(n)

Space complexity: O(n)

As we maintain a count array of size n, the space complexity of the above approach is O(n).

Optimised approach 2

A second efficient approach to solve the above problem is to use the absolute values of array elements as indexes. Below is the provided solution:

  1. Traverse the array. If the element at current position i is positive i.e. arr[i]>0, then we check the element at position arr[i]. If the element at arr[arr[i]] < 0, then the element arr[i] is repeated, else we just multiply it by -1.
  2. If the element at position i is negative, i.e. arr[i]<0, we check the element at position at -1*arr[i]. If the element at arr[-1*arr[i]] < 0, then the element arr[i] is repeated, else we just multiply it by -1.
  3. To get the element that is missed, we traverse the array again. The index at which the element is positive is the repeated element, as it hasn’t occurred once during the above two steps.

Pseudocode

a = 0 
b = 0 
for i = 1 to n:
	if arr[i] greater than 0:
		if arr[arr[i]] greater than 0:
			arr[arr[i]] = arr[arr[i]] * -1
		else:
			a = arr[arr[i]]
	else:
		pos = arr[arr[i]]*-1
		if arr[pos] greater 0:
			arr[pos] = arr[pos]*-1
		else:
			a = arr[pos]
for i = 1 to n:
	if arr[i] > 0:
		b = i

Implementation

C++

#include "bits/stdc++.h"
using namespace std;

void solve()
{
   //Below is the array
   int arr[] = {1,2,4,4,3};

   //Defining the size of the array
   int n = sizeof(arr)/sizeof(int);

   //Missing Number
   int miss = 0;
  
   //Repeating Number
   int rep = 0;

   //Running our first loop
   for(int i = 0;i<n;i+=1){
      
       //If the element at index i is positive, it means it is unvisited yet.
       if(arr[i]>0){

           //As our array is 0-indexed
           int ind = arr[i]-1;

           //if our array[element] is unvisited yet, then we simply mark is present
           if(arr[ind]>0){
               arr[ind]*=-1;
           }else{
               //if the array[element] is already visited, then we see that the array[element] occurs 2 times in this array.
               //Therefore repeated element is found.
               rep = -1*arr[ind];
           }
       }else{
           //We repeat the same above process, just by making the to be index element positive.
           int pos = arr[i]*-1;
           int ind = pos - 1;
           if (arr[ind] > 0)
               arr[ind] = arr[ind]*-1;
           else
               rep = -1*arr[ind];
       }
   }

   //If any index is positive, then we see that the element occured 0 times. Therefore missed.
   for(int i = 0;i<n;i+=1){
       if(arr[i]>0){
           miss=i+1;
       }
   }
   cout<<"Missing Number: " << miss << '\n';
   cout << "Repeating Number: " << rep;
}
int main()
{
   solve();
   return 0;
}

 

Output

Missing Number: 5
Repeating Number: 4

Complexity Analysis

Time complexity: O(n)

As in the above approach, we use two loops of O(n) time complexity. Therefore, the final time complexity is O(2*n), which is O(n)

Space complexity: O(1)

We are using the same array to mark negative elements, which means we haven’t used any extra space. Therefore, the space complexity for the above approach is O(1)

Optimised approach 3

For solving the above problem, we can use the concept of bitwise operators that too bitwise xor (^) specifically. For this, we note the following points:

  1. x^y = y^x
  2. x^x = 0
  3. 0^x = x

Below is the required solution:

  1. Compute the bitwise xor of all the elements of the given array. Let this be x.
  2. Compute the bitwise xor of all elements from 1 to n. Let this be z.
  3. Now, let z equals xor of x and y. i.e z = x^y. 
  4. Now, any bit set in z comes either from x or y. Therefore, we pick any bit from z and divide the array into two sets—one with the selected bit as a set and the other as the chosen bit is unset. 
  5. Now, xor all the elements of set 1. This will give us x. Similarly, XORing all the elements of set 2 will give us y.

Pseudocode

x = 0 // Missing Number
y = 0 // Repeating Number
for i = 1 to n:
	x = x ^ arr[i]
	y = y ^ i
z = x^y
last_set_bit = z ^ ~(z-1)
x = 0
y = 0
for i = 1 to n:
	if (last_set_bit & arr[i])
		x = x ^ arr[i]
	else
		y = y ^ arr[i]

Implementation

C++

#include "bits/stdc++.h"
using namespace std;


void solve()
{
    //Below is the array
    int arr[] = {1,2,4,4,3};


    //Defining the size of the arry
    int n = sizeof(arr)/sizeof(int);


    //Missing Number
    int miss = 0;
    
    //Repeating Number
    int rep = 0;


    int xor_ = 0;
    for(int i = 0;i<n;i+=1){
        xor_^=arr[i];
    }
    for(int i = 1;i<=n;i+=1){
        xor_^=i;
    }


    //xor here is xor of 2 numbers bitwise. These 2 numbers are missing and repeating numbers.
    //Now we will divide these array numbers into 2 sets. The xor of each of these sets will give us 2 numbers. These are 
    //Repeating and Missing Numbers.


    int a = 0;
    int b = 0;


    //Getting the last bit which is set
    int last_bit_set = xor_ & ~ (xor_ - 1);


    //Loop for dividing the array in 2 sets. one for missing elements,other for repeating.
    for(int i = 0;i<n;i+=1){
        if(last_bit_set & arr[i]){
            //If the last bit is set, go to the missing set.
            a^=arr[i];
        }else{
            // Else, this goes to the repeating set.
            b^=arr[i];
        }
    }
    for(int i = 1;i<=n;i+=1){
        if(last_bit_set & i){
            a^=i;
        }else{
            b^=i;
        }
    }
    miss=a;
    rep=b;
    cout<<"Missing Number: " << miss << '\n';
    cout << "Repeating Number: " << rep;
}
int main()
{
    solve();
    return 0;
}

 

Output

Missing Number:  5
Repeating Repeating: 4

 

Complexity Analysis

Time complexity: O(n)

As in the above approach, we use two loops of O(n) time complexity. First for computing the value of z, and the next for dividing the array into two sets as per the set bits. Therefore, the final time complexity is O(2*n), which is O(n)

Space complexity: O(1)

We are using the same array to mark negative elements, which means we haven’t used any extra space. Therefore, the space complexity for the above approach is O(1).

Frequently Asked Questions

What are the different sorting algorithms that can be used in the above approach?

Apart from Merge sort, we can use Quicksort in the above problem, as it also gives O(nlog(n)) as its average time complexity. But, if we’ve used Bubble sort, Insertion sort, or selection sort, our time complexity would have become O(n2).

What are bitwise operators?

Characters that perform operations to be done on single bits are called bitwise operators. By positionally matching the individual bits of two-bit patterns of equal length, a bitwise operation is performed: If the first bit is one and the second bit is 1, a logical AND (&) of each bit pair results in a 1.

What is the difference between bitwise xor and bitwise or?

In bitwise xor of 2 elements, when a particular bit is set in one and unset in another element, then only the corresponding bit is set in the resulting number. Though, if the bits in both numbers are set, the resultant bit will be unset as well. While, in bitwise or, if any one element has a bit set, the resulting number will have that bit as set.

Conclusion

This article discussed the problem of finding missing and repeating elements belonging to an array such that all elements are in the range of 1 to n. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

Recommended problems -

 

We hope that this blog has helped you increase your knowledge regarding such DSA problems, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

 

Previous article
Find common elements in three sorted arrays
Next article
Search in a Row wise and Column wise Sorted Matrix
Live masterclass