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:
- Traverse the array and increment count[arr[i]] as we get on arr[i].
- After noting the count of each arr[i], traverse the count array.
- If the count[i] > 1 for some i, then it is the repeating element.
- 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:
- 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.
- 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.
- 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:
- x^y = y^x
- x^x = 0
- 0^x = x
Below is the required solution:
- Compute the bitwise xor of all the elements of the given array. Let this be x.
- Compute the bitwise xor of all elements from 1 to n. Let this be z.
- Now, let z equals xor of x and y. i.e z = x^y.
- 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.
- 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;
}
You can also try this code with Online C++ Compiler
Output
Missing Number: 5
Repeating Repeating: 4
You can also try this code with Online C Compiler
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!"
34+ registered 
