Given a read-only array of N integers with values also in the range [1, N] both inclusive. Each integer appears exactly once except A which appears twice and B which is missing. The task is to find the repeating and missing numbers A and B where A repeats twice and B is missing.
Brute force Approach
In the ideal scenario, where the array contains 1 to n elements, we check the count of each element within this range. If the count is 2, we declare it as a repetitive element, and if the count is 0, we mark it as a missing element.
public class Solution {
public static int[] findMissingRepeatingNumbers(int []a) {
int rep = -1;
int mis = -1;
for(int i=1; i<=a.length; i++){
int count = 0;
for(int j=0; j<a.length; j++){
if(a[j]==i) count+=1;
}
if(count==2) rep = i;
if(count==0) mis = i;
}
return new int[]{rep,mis};
}
}
Time Complexity - O(n^2)
Space Complexity - O(1)
Hashing Approach
Whenever we are dealing with counting or frequency, our preferred approach involves using hashmaps or dictionaries. This method calculates the frequency of all the elements at once.
public class Solution {
public static int[] findMissingRepeatingNumbers(int []a) {
int rep = -1;
int mis = -1;
Map<Integer,Integer> dict = new HashMap<>();
for(int element: a){
if(!dict.containsKey(element)){
dict.put(element,0);
}
int currentFrequency = dict.get(element);
dict.put(element,currentFrequency+1);
}
for(int i=0; i<a.length; i++){
int key = i+1;
if(dict.containsKey(key)){
int frequency = dict.get(key);
if(frequency==2){
rep = key;
}
}
else{
mis = key;
}
}
return new int[]{rep,mis};
}
}
Time Complexity - O(n)
Space Complexity - O(n)
Mathematical approach
Sum of n natural numbers = n(n+1)/2
Sum of squares of n natural numbers = n(n+1)(2n+1)/6
Subtract the sum of the array from the sum of the first n natural numbers. This will give you the difference between the missing number and the repeating difference. This is the first equation that has two unknowns.
sn - s = missing_number - repeating_number
For the second equation, we need to do the subtraction between individual squares.
sn^2 - s^2 = missing_number^2 - repeating_number^2
missing_number + repeating_number = (sn^2 - s^2)/(sn-s)
From these two equations, we can easily find out the 2 unknowns.
Note: Use BigInteger for storing sums.
class Solve {
BigInteger bigValue(int val){
// return new BigInteger(Integer.toString(val));
return BigInteger.valueOf(val);
}
int[] findTwoElement(int a[], int n) {
// System.out.println("n="+n+" length=" + a.length);
// BigInteger sn = bigValue((n*(n+1))/2);
// BigInteger s2n = bigValue((n*(n+1)*(2*n+1))/6);
BigInteger z = bigValue(n);
BigInteger sn = z.multiply(z.add(bigValue(1))).divide(bigValue(2));
BigInteger s2n = sn.multiply(z.multiply(bigValue(2)).add(bigValue(1))).divide(bigValue(3));
// System.out.println("sn="+sn+" s2n=" + s2n);
BigInteger s = bigValue(0);
BigInteger s2 = bigValue(0);
for(int val: a){
BigInteger temp = bigValue(val);
s= s.add(temp);
s2 = s2.add(temp.multiply(temp));
}
// System.out.println("s="+s+" s2=" + s2);
BigInteger val1 = sn.subtract(s);
BigInteger val2 = s2n.subtract(s2);
// System.out.println("val1="+val1+" val2=" + val2);
val2 = val2.divide(val1);
// System.out.println("val1="+val1+" val2=" + val2);
BigInteger mis = val1.add(val2).divide(bigValue(2));
BigInteger rep = mis.subtract(val1);
// System.out.println("mis="+mis+" rep=" + rep);
return new int[]{rep.intValue(),mis.intValue()};
}
}
Time Complexity - O(n)
Space Complexity - O(1)
Bit Manipulation Approach (Xor)
a ^ a = 0
Do the XOR operation on the given array with an array that contains all numbers from 1 to n. When you XOR these two arrays, all elements with duplicates will cancel out, leaving only two elements: one repeating and one missing.
Now we have the XOR value for the repeating and missing numbers
Differentiating Position
The position at which the bits differ from the rightmost end for the given two numbers is called the differentiating position. This is also known as the differentiating bit
This position helps us group the 2 arrays into 2 groups. One group will have 1 in the differentiating position, and the other group will have 0. If we perform XOR on each group, the resultant numbers from these groups will be the missing number and the repeating number. Now, our task is to identify which number is repeating and which one is missing from the results. This can be easily determined by iterating through the given array again.
How to find a differentiating bit
From the resultant XOR, we need to find the differentiating bit. This bit will be the first '1' from the rightmost end because, according to the properties of XOR, if two bits are the same, the value will be '0'; otherwise, it will be '1'.
From a code perspective, the first '1' can be found using two methods:
Do a bitwise AND with each position bit, such as 1, 2, 4, 8, etc., and whichever position yields a non-zero result is the correct differentiating position.
Use a simple operation:
res & ~(res-1). This operation is explained in detail in the additional information section.
Code
public class Solution {
public static int[] findMissingRepeatingNumbers(int []a) {
// Write your code here
int resXor = 0;
for(int i=0; i<a.length; i++){
resXor = resXor ^ a[i];
resXor = resXor ^ (i+1);
}
int difBit = -1;
while(true){
difBit+=1;
if((resXor & (1<<difBit))!=0) {
break;
}
}
int zero = 0;
int one = 0;
for(int i=0; i<a.length; i++){
if((a[i] & (1<<difBit))!=0){
one = one ^ a[i];
}
else{
zero = zero ^ a[i];
}
}
for(int i=1; i<a.length+1; i++){
if((i & (1<<difBit))!=0){
one = one ^ i;
}
else{
zero = zero ^ i;
}
}
int count = 0;
for(int i=0; i<a.length; i++){
if(one==a[i]) count+=1;
}
if(count==2) return new int[]{one,zero};
return new int[]{zero, one};
}
}
Time Complexity - O(n)
Space Complexity - O(1)
Additional Information
xr & ~(xr-1)
xr - 1, complements all the bits from the right side till the first occurrence of 1.
~(xr-1), It will flip all the bits. This operation mainly flips all the left side of the differentiating bit and keeps the same bits on the left side when compared to the original xr.
Now if we do bit-wise
&with xr then the rightmost side of the diff bit will get canceled because they are different.