Open In App

Find the missing and repeating number

Last Updated : 13 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given an unsorted array of size n. Array elements are in the range of 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers.

Examples: 

Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array, 2 is missing and 3 occurs twice 

Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: Missing = 5, Repeating = 1

Below are various methods to solve the problems: 

Method 1 (Use count array)
Approach: 

  • Create a temp array temp[] of size n with all initial values as 0.
  • Traverse the input array arr[], and do the following for each arr[i] 
    • if(temp[arr[i]-1] == 0), set temp[arr[i]-1] = 1;
    • if(temp[arr[i]-1] == 1) output “arr[i]” //repeating number
  • Traverse temp[] and output ‘i+1’ corresponding to the element of array temp[] having value as 0. (This is the missing number)

Note that, we use ‘arr[i]-1’ as the corresponding element to the ‘arr[i]’ in temp[] array, as indexing in an array starts from 0 to n-1 and the input array arr[] has numbers from 1 to n.

C++
#include <bits/stdc++.h>
using namespace std;

void printTwoElements(int arr[], int n)
{
    int temp[n] = {}; // Creating temp array of size n with
                      // initial values as 0.
    int repeatingNumber=-1;
    int missingNumber=-1;
  
    for (int i = 0; i < n; i++) {
        temp[arr[i]-1]++;
        if (temp[arr[i] - 1] > 1) {
            repeatingNumber = arr[i];
        }
    }
    for (int i = 0; i < n; i++) {
        if (temp[i] == 0) {
            missingNumber = i + 1;
            break;
        }
    }
  
    cout << "The repeating number is " << repeatingNumber<<"."
         << endl;
    cout << "The missing number is " << missingNumber<<"."
         << endl;
  
}

int main()
{

    int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printTwoElements(arr, n);
    return 0;
}
//  This code is contributed by vivek1208
Java
import java.io.*;

class Main {

    static void printTwoElements(int[] arr, int n)
    {
        int[] temp
            = new int[n]; // Creating temp array of size n
                          // with initial values as 0.
        int repeatingNumber = -1;
        int missingNumber = -1;

        for (int i = 0; i < n; i++) {
            temp[arr[i] - 1]++;
            if (temp[arr[i] - 1] > 1) {
                repeatingNumber = arr[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (temp[i] == 0) {
                missingNumber = i + 1;
                break;
            }
        }

        System.out.println("The repeating number is "
                           + repeatingNumber + ".");
        System.out.println("The missing number is "
                           + missingNumber + ".");
    }

    public static void main(String[] args)
    {
        int[] arr = { 7, 3, 4, 5, 5, 6, 2 };
        int n = arr.length;
        printTwoElements(arr, n);
    }
}

// This code is contributed by vivek1208
Python3
def printTwoElements(arr):
    n = len(arr)
    temp = [0] * n  # Creating temp array of size n with initial values as 0.
    repeatingNumber = -1
    missingNumber = -1

    for i in range(n):
        temp[arr[i] - 1] += 1
        if temp[arr[i] - 1] > 1:
            repeatingNumber = arr[i]
    for i in range(n):
        if temp[i] == 0:
            missingNumber = i + 1
            break

    print("The repeating number is", repeatingNumber, ".")
    print("The missing number is", missingNumber, ".")


arr = [7, 3, 4, 5, 5, 6, 2]
printTwoElements(arr)

# This code is contributed by vivek1208
C#
using System;

public class Program
{
    public static void printTwoElements(int[] arr, int n)
    {
        int[] temp = new int[n]; // Creating temp array of size n with initial values as 0.
        int repeatingNumber = -1;
        int missingNumber = -1;

        for (int i = 0; i < n; i++)
        {
            temp[arr[i] - 1]++;
            if (temp[arr[i] - 1] > 1)
            {
                repeatingNumber = arr[i];
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (temp[i] == 0)
            {
                missingNumber = i + 1;
                break;
            }
        }

        Console.WriteLine("The repeating number is " + repeatingNumber + ".");
        Console.WriteLine("The missing number is " + missingNumber + ".");
    }

    public static void Main()
    {
        int[] arr = { 7, 3, 4, 5, 5, 6, 2 };
        int n = arr.Length;
        printTwoElements(arr, n);
    }
}
Javascript
function printTwoElements(arr) {
    const n = arr.length;
    const temp = Array(n).fill(0); // Creating temp array of size n with initial values as 0.
    let repeatingNumber = -1;
    let missingNumber = -1;

    for (let i = 0; i < n; i++) {
        temp[arr[i] - 1]++;
        if (temp[arr[i] - 1] > 1) {
            repeatingNumber = arr[i];
        }
    }
    for (let i = 0; i < n; i++) {
        if (temp[i] === 0) {
            missingNumber = i + 1;
            break;
        }
    }

    console.log(`The repeating number is ${repeatingNumber}.`);
    console.log(`The missing number is ${missingNumber}.`);
}

const arr = [7, 3, 4, 5, 5, 6, 2];
printTwoElements(arr);

// This code is contributed by vivek1208

Output
The repeating number is 5.
The missing number is 1.



Time Complexity: O(n)
Auxiliary Space: O(n)

Method 2 (Use elements as Index and mark the visited places)
Approach: 
Traverse the array. While traversing, use the absolute value of every element as an index and make the value at this index negative to mark it visited. If something is already marked negative then this is the repeating element. To find the missing, traverse the array again and look for a positive value.

C++
// C++ program to Find the repeating
// and missing elements

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

void printTwoElements(int arr[], int size)
{
    int i;
    cout << "The repeating element is ";

    for (i = 0; i < size; i++) {
        if (arr[abs(arr[i]) - 1] > 0)
            arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
        else
            cout << abs(arr[i]) << "\n";
    }

    cout << "and the missing element is ";
    for (i = 0; i < size; i++) {
        if (arr[i] > 0)
            cout << (i + 1);
    }
}

/* Driver code */
int main()
{
    int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printTwoElements(arr, n);
}

// This code is contributed by Shivi_Aggarwal
C
// C program to Find the repeating
// and missing elements

#include <stdio.h>
#include <stdlib.h>

void printTwoElements(int arr[], int size)
{
    int i;
    printf("\nThe repeating element is ");

    for (i = 0; i < size; i++) {
        if (arr[abs(arr[i]) - 1] > 0)
            arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
        else
            printf(" %d ", abs(arr[i]));
    }

    printf("\nand the missing element is ");
    for (i = 0; i < size; i++) {
        if (arr[i] > 0)
            printf("%d", i + 1);
    }
}

// Driver code
int main()
{
    int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printTwoElements(arr, n);
    return 0;
}
Java
// Java program to Find the repeating
// and missing elements

import java.io.*;

class GFG {

    static void printTwoElements(int arr[], int size)
    {
        int i;
        System.out.print("The repeating element is ");

        for (i = 0; i < size; i++) {
            int abs_val = Math.abs(arr[i]);
            if (arr[abs_val - 1] > 0)
                arr[abs_val - 1] = -arr[abs_val - 1];
            else
                System.out.println(abs_val);
        }

        System.out.print("and the missing element is ");
        for (i = 0; i < size; i++) {
            if (arr[i] > 0)
                System.out.println(i + 1);
        }
    }

    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
        int n = arr.length;
        printTwoElements(arr, n);
    }
}

// This code is contributed by Gitanjali
Python3
# Python3 code to Find the repeating 
# and the missing elements

def printTwoElements( arr, size):
    for i in range(size):
        if arr[abs(arr[i])-1] > 0:
            arr[abs(arr[i])-1] = -arr[abs(arr[i])-1]
        else:
            print("The repeating element is ", abs(arr[i]))
            
    for i in range(size):
        if arr[i]>0:
            print("and the missing element is ", i + 1)

# Driver program to test above function */
arr = [7, 3, 4, 5, 5, 6, 2]
n = len(arr)
printTwoElements(arr, n)

# This code is contributed by "Abhishek Sharma 44"
C#
// C# program to Find the repeating
// and missing elements

using System;

class GFG {
    static void printTwoElements(int[] arr, int size)
    {
        int i;
        Console.Write("The repeating element is ");

        for (i = 0; i < size; i++) {
            int abs_val = Math.Abs(arr[i]);
            if (arr[abs_val - 1] > 0)
                arr[abs_val - 1] = -arr[abs_val - 1];
            else
                Console.WriteLine(abs_val);
        }

        Console.Write("and the missing element is ");
        for (i = 0; i < size; i++) {
            if (arr[i] > 0)
                Console.WriteLine(i + 1);
        }
    }

    // Driver program
    public static void Main()
    {
        int[] arr = { 7, 3, 4, 5, 5, 6, 2 };
        int n = arr.Length;
        printTwoElements(arr, n);
    }
}
// This code is contributed by Sam007
Javascript
<script>
// Program to Find the repeating
// and missing elements
 
    function  printTwoElements(arr,size)
   { 
    var i;
        document.write("The repeating element is ");
           
    for (i = 0; i < size; i++) 
    {
        var abs_value = Math.abs(arr[i]);
        if (arr[abs_value - 1] > 0)
            arr[abs_value - 1] = -arr[abs_value - 1];
        else
            document.write( abs_value);
    }
             
    document.write("<br> and the missing element is ");
    for (i = 0; i < size; i++) 
    {
        if (arr[i] > 0)
            document.write (i + 1);
    }
}
 
/* Driver code */
    arr = new Array ( 7, 3, 4, 5, 5, 6, 2 );
    n = arr.length;
    printTwoElements(arr, n);
    
    // This code is contributed by simranarora5sos
</script>
PHP
<?php
// PHP program to Find the repeating
// and missing elements

function printTwoElements($arr, $size)
{
    $i;
    echo "The repeating element is", " ";

    for($i = 0; $i < $size; $i++)
    {
        if($arr[abs($arr[$i]) - 1] > 0)
            $arr[abs($arr[$i]) - 1] = 
            - $arr[abs($arr[$i]) - 1];
        else
            echo ( abs($arr[$i]));
    }

    echo "\nand the missing element is ";
    for($i = 0; $i < $size; $i++)
    {
        if($arr[$i] > 0)
            echo($i + 1);
    }
}
    
    // Driver Code
    $arr = array(7, 3, 4, 5, 5, 6, 2);
    $n = count($arr);
    printTwoElements($arr, $n);

// This code is contributed by anuj_67.
?>

Output
The repeating element is 5
and the missing element is 1


Time Complexity: O(n)
Auxiliary Space: O(1) as it is using constant variables
Thanks to Manish Mishra for suggesting this method. 

Method 3 (Make two equations)
Approach:

  • Let x be the missing and y be the repeating element.
  • Get the sum of all numbers using formula S = n(n+1)/2 – x + y
  • Get product of all numbers using formula P = 1*2*3*…*n * y / x
  • The above two steps give us two equations, we can solve the equations and get the values of x and y.

Time Complexity: O(n)
Thanks to disappearedng for suggesting this solution. 

Note: This method can cause arithmetic overflow as we calculate the product and sum of all array elements.

Method 4 (Use XOR)

Approach:

  • Let x and y be the desired output elements.
  • Calculate the XOR of all the array elements.

xor1 = arr[0]^arr[1]^arr[2]…..arr[n-1]

  • XOR the result with all numbers from 1 to n

xor1 = xor1^1^2^…..^n

  • In the result xor1, all elements would nullify each other except x and y. All the bits that are set in xor1 will be set in either x or y. So if we take any set bit (We have chosen the rightmost set bit in code) of xor1 and divide the elements of the array in two sets – one set of elements with the same bit set and another set with the same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in the first set, we will get x, and by doing the same in the other set we will get y. 

Below is the implementation of the above approach: 

C++
// C program to Find the repeating
// and missing elements

#include <stdio.h>
#include <stdlib.h>

/* The output of this function is stored at
   *x and *y */
void getTwoElements(int arr[], int n, int* x, int* y)
{
    /* Will hold xor of all elements and numbers 
       from 1 to n */
    int xor1;

    /* Will have only single set bit of xor1 */
    int set_bit_no;

    int i;
    *x = 0;
    *y = 0;

    xor1 = arr[0];

    /* Get the xor of all array elements */
    for (i = 1; i < n; i++)
        xor1 = xor1 ^ arr[i];

    /* XOR the previous result with numbers 
       from 1 to n*/
    for (i = 1; i <= n; i++)
        xor1 = xor1 ^ i;

    /* Get the rightmost set bit in set_bit_no */
    set_bit_no = xor1 & ~(xor1 - 1);

    /* Now divide elements in two sets by comparing 
    rightmost set bit of xor1 with bit at same 
    position in each element. Also, get XORs of two 
    sets. The two XORs are the output elements. The
    following two for loops serve the purpose */
    for (i = 0; i < n; i++) {
        if (arr[i] & set_bit_no)
            /* arr[i] belongs to first set */
            *x = *x ^ arr[i];

        else
            /* arr[i] belongs to second set*/
            *y = *y ^ arr[i];
    }
    for (i = 1; i <= n; i++) {
        if (i & set_bit_no)
            /* i belongs to first set */
            *x = *x ^ i;

        else
            /* i belongs to second set*/
            *y = *y ^ i;
    }

    /* *x and *y hold the desired output elements */
}

/* Driver program to test above function */
int main()
{
    int arr[] = { 1, 3, 4, 5, 5, 6, 2 };
    int* x = (int*)malloc(sizeof(int));
    int* y = (int*)malloc(sizeof(int));
    int n = sizeof(arr) / sizeof(arr[0]);

    getTwoElements(arr, n, x, y);
    printf(" The missing element is %d"
           " and the repeating number"
           " is %d",
           *x, *y);
    getchar();
}
C
// C program to Find the repeating
// and missing elements

#include <stdio.h>
#include <stdlib.h>

/* The output of this function is stored at
   *x and *y */
void getTwoElements(int arr[], int n, int* x, int* y)
{
    /* Will hold xor of all elements and numbers 
       from 1 to n */
    int xor1;

    /* Will have only single set bit of xor1 */
    int set_bit_no;

    int i;
    *x = 0;
    *y = 0;

    xor1 = arr[0];

    /* Get the xor of all array elements */
    for (i = 1; i < n; i++)
        xor1 = xor1 ^ arr[i];

    /* XOR the previous result with numbers 
       from 1 to n*/
    for (i = 1; i <= n; i++)
        xor1 = xor1 ^ i;

    /* Get the rightmost set bit in set_bit_no */
    set_bit_no = xor1 & ~(xor1 - 1);

    /* Now divide elements in two sets by comparing 
    rightmost set bit of xor1 with bit at same 
    position in each element. Also, get XORs of two 
    sets. The two XORs are the output elements. The
    following two for loops serve the purpose */
    for (i = 0; i < n; i++) {
        if (arr[i] & set_bit_no)
            /* arr[i] belongs to first set */
            *x = *x ^ arr[i];

        else
            /* arr[i] belongs to second set*/
            *y = *y ^ arr[i];
    }
    for (i = 1; i <= n; i++) {
        if (i & set_bit_no)
            /* i belongs to first set */
            *x = *x ^ i;

        else
            /* i belongs to second set*/
            *y = *y ^ i;
    }

    /* *x and *y hold the desired output elements */
}

/* Driver program to test above function */
int main()
{
    int arr[] = { 1, 3, 4, 5, 5, 6, 2 };
    int* x = (int*)malloc(sizeof(int));
    int* y = (int*)malloc(sizeof(int));
    int n = sizeof(arr) / sizeof(arr[0]);

    getTwoElements(arr, n, x, y);
    printf(" The missing element is %d"
           " and the repeating number"
           " is %d",
           *x, *y);
    getchar();
}
Java
// Java program to Find the repeating
// and missing elements

import java.io.*;

class GFG {
    static int x, y;

    static void getTwoElements(int arr[], int n)
    {
        /* Will hold xor of all elements
       and numbers from 1 to n  */
        int xor1;

        /* Will have only single set bit of xor1 */
        int set_bit_no;

        int i;
        x = 0;
        y = 0;

        xor1 = arr[0];

        /* Get the xor of all array elements  */
        for (i = 1; i < n; i++)
            xor1 = xor1 ^ arr[i];

        /* XOR the previous result with numbers from 
       1 to n*/
        for (i = 1; i <= n; i++)
            xor1 = xor1 ^ i;

        /* Get the rightmost set bit in set_bit_no */
        set_bit_no = xor1 & ~(xor1 - 1);

        /* Now divide elements into two sets by comparing
    rightmost set bit of xor1 with the bit at the same 
    position in each element. Also, get XORs of two
    sets. The two XORs are the output elements. The 
    following two for loops serve the purpose */
        for (i = 0; i < n; i++) {
            if ((arr[i] & set_bit_no) != 0)
                /* arr[i] belongs to first set */
                x = x ^ arr[i];

            else
                /* arr[i] belongs to second set*/
                y = y ^ arr[i];
        }
        for (i = 1; i <= n; i++) {
            if ((i & set_bit_no) != 0)
                /* i belongs to first set */
                x = x ^ i;

            else
                /* i belongs to second set*/
                y = y ^ i;
        }

        /* *x and *y hold the desired output elements */
    }
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 4, 5, 5, 6, 2 };

        int n = arr.length;
        getTwoElements(arr, n);
        System.out.println(" The missing element is "
                           + x + " and the "
                           + "repeating number is "
                           + y);
    }
}

// This code is contributed by Gitanjali.
Python3
# Python3 program to find the repeating 
# and missing elements 

# The output of this function is stored 
# at x and y 
def getTwoElements(arr, n):
    
    global x, y
    x = 0
    y = 0
    
    # Will hold xor of all elements 
    # and numbers from 1 to n 
    xor1 = arr[0]
    
    # Get the xor of all array elements
    for i in range(1, n):
        xor1 = xor1 ^ arr[i]
        
    # XOR the previous result with numbers 
    # from 1 to n
    for i in range(1, n + 1):
        xor1 = xor1 ^ i
    
    # Will have only single set bit of xor1
    set_bit_no = xor1 & ~(xor1 - 1)
    
    # Now divide elements into two 
    # sets by comparing a rightmost set 
    # bit of xor1 with the bit at the same 
    # position in each element. Also, 
    # get XORs of two sets. The two 
    # XORs are the output elements. 
    # The following two for loops 
    # serve the purpose
    for i in range(n):
        if (arr[i] & set_bit_no) != 0:
            
            # arr[i] belongs to first set
            x = x ^ arr[i]
        else:
            
            # arr[i] belongs to second set
            y = y ^ arr[i]
            
    for i in range(1, n + 1):
        if (i & set_bit_no) != 0:
            
            # i belongs to first set
            x = x ^ i
        else:
            
            # i belongs to second set
            y = y ^ i 
        
    # x and y hold the desired 
    # output elements 
    
# Driver code
arr = [ 1, 3, 4, 5, 5, 6, 2 ]
n = len(arr)
    
getTwoElements(arr, n)

print("The missing element is", x,
      "and the repeating number is", y)
    
# This code is contributed by stutipathak31jan
C#
// C# program to Find the repeating
// and missing elements

using System;

class GFG {
    static int x, y;

    static void getTwoElements(int[] arr, int n)
    {
        /* Will hold xor of all elements
        and numbers from 1 to n */
        int xor1;

        /* Will have only single set bit of xor1 */
        int set_bit_no;

        int i;
        x = 0;
        y = 0;

        xor1 = arr[0];

        /* Get the xor of all array elements */
        for (i = 1; i < n; i++)
            xor1 = xor1 ^ arr[i];

        /* XOR the previous result with numbers from 
        1 to n*/
        for (i = 1; i <= n; i++)
            xor1 = xor1 ^ i;

        /* Get the rightmost set bit in set_bit_no */
        set_bit_no = xor1 & ~(xor1 - 1);

        /* Now divide elements in two sets by comparing
        rightmost set bit of xor1 with bit at same 
        position in each element. Also, get XORs of two
        sets. The two XORs are the output elements.The 
        following two for loops serve the purpose */
        for (i = 0; i < n; i++) {
            if ((arr[i] & set_bit_no) != 0)

                /* arr[i] belongs to first set */
                x = x ^ arr[i];

            else

                /* arr[i] belongs to second set*/
                y = y ^ arr[i];
        }
        for (i = 1; i <= n; i++) {
            if ((i & set_bit_no) != 0)

                /* i belongs to first set */
                x = x ^ i;

            else

                /* i belongs to second set*/
                y = y ^ i;
        }

        /* *x and *y hold the desired output elements */
    }

    // Driver program
    public static void Main()
    {
        int[] arr = { 1, 3, 4, 5, 5, 6, 2 };

        int n = arr.Length;
        getTwoElements(arr, n);
        Console.Write(" The missing element is "
                      + x + " and the "
                      + "repeating number is "
                      + y);
    }
}

// This code is contributed by Sam007
Javascript
// Javascript program to Find the repeating
// and missing elements
let x, y;

    function getTwoElements(arr, n)
    {
        /* Will hold xor of all elements
       and numbers from 1 to n  */
        let xor1;

        /* Will have only single set bit of xor1 */
        let set_bit_no;

        let i;
        x = 0;
        y = 0;

        xor1 = arr[0];

        /* Get the xor of all array elements  */
        for (i = 1; i < n; i++)
            xor1 = xor1 ^ arr[i];

        /* XOR the previous result with numbers from 
       1 to n*/
        for (i = 1; i <= n; i++)
            xor1 = xor1 ^ i;

        /* Get the rightmost set bit in set_bit_no */
        set_bit_no = xor1 & ~(xor1 - 1);

        /* Now divide elements into two sets by comparing
    rightmost set bit of xor1 with the bit at the same 
    position in each element. Also, get XORs of two
    sets. The two XORs are the output elements. The 
    following two for loops serve the purpose */
        for (i = 0; i < n; i++) {
            if ((arr[i] & set_bit_no) != 0)
                /* arr[i] belongs to first set */
                x = x ^ arr[i];

            else
                /* arr[i] belongs to second set*/
                y = y ^ arr[i];
        }
        for (i = 1; i <= n; i++) {
            if ((i & set_bit_no) != 0)
                /* i belongs to first set */
                x = x ^ i;

            else
                /* i belongs to second set*/
                y = y ^ i;
        }

        /* *x and *y hold the desired output elements */
    }
   
        let arr = [ 1, 3, 4, 5, 5, 6, 2 ];

        let n = arr.length;
        getTwoElements(arr, n);
        console.log(" The missing element is  "
                           + x + " and the "
                           + "repeating number is "
                           + y);
    
    // This code is contributed by garg28harsh.
PHP
<?php
// PHP program to Find the repeating
// and missing elements

function getTwoElements(&$arr, $n)
{

    /* Will hold xor of all elements
    and numbers from 1 to n */
    $xor1;

    /* Will have only single set bit of xor1 */
    $set_bit_no;

    $i;
    $x = 0;
    $y = 0;

    $xor1 = $arr[0];

    /* Get the xor of all array elements */
    for ($i = 1; $i < $n; $i++)
        $xor1 = $xor1 ^ $arr[$i];

    /* XOR the previous result with numbers 
    from 1 to n*/
    for ($i = 1; $i <= $n; $i++)
        $xor1 = $xor1 ^ $i;

    /* Get the rightmost set bit in set_bit_no */
    $set_bit_no = $xor1 & ~($xor1 - 1);

    /* Now divide elements in two sets by comparing
    rightmost set bit of xor1 with bit at same 
    position in each element. Also, get XORs of two
    sets. The two XORs are the output elements.The 
    following two for loops serve the purpose */
    for ($i = 0; $i < $n; $i++) 
    {
        if (($arr[$i] & $set_bit_no) != 0)
        
            /* arr[i] belongs to first set */
            $x = $x ^ $arr[$i];

        else
        
            /* arr[i] belongs to second set*/
            $y = $y ^ $arr[$i];
    }
    
    for ($i = 1; $i <= $n; $i++)
    {
        if (($i & $set_bit_no) != 0)
        
            /* i belongs to first set */
            $x = $x ^ $i;

        else
        
            /* i belongs to second set*/
            $y = $y ^ $i;
    }

    /* *x and *y hold the desired output elements */
    echo("The missing element is " . $x . 
         " and the repeating number is " . $y);
}

// Driver Code
$arr = array( 1, 3, 4, 5, 5, 6, 2 );
$n = sizeof($arr);
getTwoElements($arr, $n);

// This code is contributed by Code_Mech

Output
 The missing element is 7 and the repeating number is 5


Time Complexity: O(n)
Auxiliary Space: O(1) as it is using constant space if the input array is excluded
This method doesn’t cause overflow, but it doesn’t tell which one occurs twice and which one is missing. We can add one more step that checks which one is missing and which one is repeating. This can be easily done in O(n) time.

Method 5 (Use a Map)
Approach: 
This method involves creating a Hashtable with the help of Map. In this, the elements are mapped to their natural index. In this process, if an element is mapped twice, then it is the repeating element. And if an element’s mapping is not there, then it is the missing element.

Below is the implementation of the above approach: 

C++
// C++ program to find the repeating
// and missing elements using Maps 
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    int arr[] = { 4, 3, 6, 2, 1, 1 };
    int n = 6;
    
    unordered_map<int, bool> numberMap;
    
    for(int i : arr) 
    {
        if (numberMap.find(i) == 
            numberMap.end())
        {
            numberMap[i] = true;
        }
        else
        {
            cout << "Repeating = " << i;
              break;
        }
    }
    cout << endl;
    
    for(int i = 1; i <= n; i++)
    {
        if (numberMap.find(i) == 
            numberMap.end()) 
        {
            cout << "Missing = " << i;
              break;
        }
    }
    return 0;
}

// This code is contributed by RohitOberoi
Java
// Java program to find the
// repeating and missing elements
// using Maps

import java.util.*;

public class Test1 {

    public static void main(String[] args)
    {

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

        Map<Integer, Boolean> numberMap
            = new HashMap<>();

        int max = arr.length;

        for (Integer i : arr) {

            if (numberMap.get(i) == null) {
                numberMap.put(i, true);
            }
            else {
                System.out.println("Repeating = " + i);
            }
        }
        for (int i = 1; i <= max; i++) {
            if (numberMap.get(i) == null) {
                System.out.println("Missing = " + i);
            }
        }
    }
}
Python3
# Python3 program to find the 
# repeating and missing elements 
# using Maps
def main():
    
    arr = [ 4, 3, 6, 2, 1, 1 ]
    
    numberMap = {}
    
    max = len(arr)
    for i in arr:
        if not i in numberMap:
            numberMap[i] = True
            
        else:
            print("Repeating =", i)
    
    for i in range(1, max + 1):
        if not i in numberMap:
            print("Missing =", i)
main()

# This code is contributed by stutipathak31jan
C#
// C# program to find the
// repeating and missing elements
// using Maps
using System;
using System.Collections.Generic;

class GFG
{
    public static void Main(String[] args)
    {
        int[] arr = { 4, 3, 6, 2, 1, 1 };

        Dictionary<int, Boolean> numberMap =
                   new Dictionary<int, Boolean>();

        int max = arr.Length;

        foreach (int i in arr) 
        {
            if (!numberMap.ContainsKey(i)) 
            {
                numberMap.Add(i, true);
            }
            else 
            {
                Console.WriteLine("Repeating = " + i);
            }
        }
        for (int i = 1; i <= max; i++) 
        {
            if (!numberMap.ContainsKey(i)) 
            {
                Console.WriteLine("Missing = " + i);
            }
        }
    }
}

// This code is contributed by PrinciRaj1992
Javascript
<script>

// JavaScript program to find the repeating
// and missing elements using Maps 

// driver program
let arr = [ 4, 3, 6, 2, 1, 1 ];
let n = 6;
    
let numberMap = new Map();
    
for(let i of arr) 
{
    if (numberMap.has(i) == false) {
        numberMap.set(i,true);
    }
    else
    {
       document.write("Repeating = ",i);
    }
}
   document.write("</br>");
    
for(let i = 1; i <= n; i++)
{
    if (numberMap.has(i) == false) {
       document.write("Missing = " ,i);
    }
}

// This code is contributed by Shinjanpatra
</script>

Output
Repeating = 1
Missing = 5


Time Complexity: O(N)
Auxiliary Space: O(N)

Method 6 (Make two equations using sum and sum of squares)
Approach:

  • Let x be the missing and y be the repeating element.
  • Let N is the size of the array.
  • Get the sum of all numbers using the formula S = N(N+1)/2
  • Get the sum of square of all numbers using formula Sum_Sq = N(N+1)(2N+1)/6
  • Iterate through a loop from i=1….N
  • S -= A[i]
  • Sum_Sq -= (A[i]*A[i])
  • It will give two equations 
    x-y = S – (1) 
    x^2 – y^2 = Sum_sq 
    x+ y = (Sum_sq/S) – (2) 
C++
#include <bits/stdc++.h> 

using namespace std;

vector<int>repeatedNumber(const vector<int> &A) {
    long long int len = A.size();
    long long int Sum_N = (len * (len+1) ) /2, Sum_NSq = (len * (len +1) *(2*len +1) )/6;
    long long int missingNumber=0, repeating=0;
    
    for(int i=0;i<A.size(); i++){
       Sum_N -= (long long int)A[i];
       Sum_NSq -= (long long int)A[i]*(long long int)A[i];
    }
    
    missingNumber = (Sum_N + Sum_NSq/Sum_N)/2;
    repeating= missingNumber - Sum_N;
    vector <int> ans;
    ans.push_back(repeating);
    ans.push_back(missingNumber);
    return ans;
    
}


int main(void){
        std::vector<int> v = {4, 3, 6, 2, 1, 6,7};
    vector<int> res = repeatedNumber(v);
    for(int x: res){
        cout<< x<<"  ";
    }
    cout<<endl;
}
Java
import java.util.*;
import java.math.BigInteger;
class GFG 
{
    static Vector<Integer> repeatedNumber(int[] a) 
    {
       
        BigInteger n=BigInteger.valueOf(a.length);
  
        BigInteger s=BigInteger.valueOf(0);
        BigInteger ss=BigInteger.valueOf(0);

        for(int x : a)
        {
            s=  s.add(BigInteger.valueOf(x));
            ss= ss.add(BigInteger.valueOf(x).multiply(BigInteger.valueOf(x))); 
        }

        BigInteger as= n.multiply(n.add(BigInteger.valueOf(1))).divide(BigInteger.valueOf(2));
        BigInteger ass= as.multiply(BigInteger.valueOf(2).multiply(n).add(BigInteger.valueOf(1))).divide(BigInteger.valueOf(3));

        BigInteger sub=as.subtract(s);
        BigInteger add=(ass.subtract(ss)).divide(sub);
        //(ass-ss)/sub;

        int b = sub.add(add).divide(BigInteger.valueOf(2)).intValue();
        //(sub+add)/2;
        int A = BigInteger.valueOf(b).subtract(sub).intValue();
        Vector<Integer> ans = new Vector<>();
        ans.add(A);
        ans.add(b);
        return ans;
    }

    // Driver Code
    public static void main(String[] args) 
    {
        int[] v = { 4, 3, 6, 2, 1, 6, 7 };
        Vector<Integer> res = repeatedNumber(v);
        for (int x : res) 
        {
            System.out.print(x + " ");
        }
    }
}

// This code is contributed by Rajput-Ji
Python3
def repeatedNumber(A):
    
    length = len(A)
    Sum_N = (length * (length + 1)) // 2
    Sum_NSq = ((length * (length + 1) * 
                     (2 * length + 1)) // 6)
    
    missingNumber, repeating = 0, 0
    
    for i in range(len(A)):
        Sum_N -= A[i]
        Sum_NSq -= A[i] * A[i]
        
    missingNumber = (Sum_N + Sum_NSq // 
                             Sum_N) // 2
    repeating = missingNumber - Sum_N
    
    ans = []
    ans.append(repeating)
    ans.append(missingNumber)
    
    return ans

# Driver code
v = [ 4, 3, 6, 2, 1, 6, 7 ]
res = repeatedNumber(v)

for i in res:
    print(i, end = " ")

# This code is contributed by stutipathak31jan 
C#
using System;
using System.Collections.Generic;

class GFG 
{
    static List<int> repeatedNumber(int[] A) 
    {
        int len = A.Length;
        int Sum_N = (len * (len + 1)) / 2;
        int Sum_NSq = (len * (len + 1) * 
                        (2 * len + 1)) / 6;
        int missingNumber = 0, repeating = 0;

        for (int i = 0; i < A.Length; i++) 
        {
            Sum_N -= A[i];
            Sum_NSq -= A[i] * A[i];
        }

        missingNumber = (Sum_N + Sum_NSq / 
                                 Sum_N) / 2;
        repeating = missingNumber - Sum_N;
        List<int> ans = new List<int>();
        ans.Add(repeating);
        ans.Add(missingNumber);
        return ans;
    }

    // Driver Code
    public static void Main(String[] args) 
    {
        int[] v = { 4, 3, 6, 2, 1, 6, 7 };
        List<int> res = repeatedNumber(v);
        foreach (int x in res) 
        {
            Console.Write(x + " ");
        }
    }
}

// This code is contributed by PrinciRaj1992
Javascript
<script>

function repeatedNumber(A){
    
    let length = A.length
    let Sum_N = Math.floor((length * (length + 1)) / 2)
    let Sum_NSq = Math.floor((length * (length + 1) * (2 * length + 1))/6)

    let missingNumber = 0 
    let repeating = 0

    for(let i=0;i<A.length;i++){
        Sum_N -= A[i]
        Sum_NSq -= A[i] * A[i]
    }
    
    missingNumber = Math.floor(Math.floor(Sum_N + Sum_NSq / Sum_N) / 2)
    repeating = missingNumber - Sum_N

    let ans = []
    ans.push(repeating)
    ans.push(missingNumber)

return ans

}

// Driver code
let v = [ 4, 3, 6, 2, 1, 6, 7 ]
let res = repeatedNumber(v)

for(let i of res)
    document.write(i," ")

// This code is contributed by shinjanpatra

</script>

Output
6  5  



Time Complexity: O(n) 
Auxiliary Space: O(1)



Previous Article
Next Article

Similar Reads

Find the repeating and the missing number using two equations
Given an array arr[] of size N, each integer from the range [1, N] appears exactly once except A which appears twice and B which is missing. The task is to find the numbers A and B.Examples: Input: arr[] = {1, 2, 2, 3, 4} Output: A = 2 B = 5Input: arr[] = {5, 3, 4, 1, 1} Output: A = 1 B = 2 Approach: From the sum of first N natural numbers, SumN =
7 min read
Find the two non-repeating elements in an array of repeating elements/ Unique Numbers 2
Given an array arr[] containing 2*N+2 positive numbers, out of which 2*N numbers exist in pairs whereas the other two number occur exactly once and are distinct. Find the other two numbers. Return in increasing order. Example: Input: N = 2, arr[] = {1, 2, 3, 2, 1, 4}Output:3 4 Explanation: 3 and 4 occur exactly once. Input: N = 1, arr[] = {2, 1, 3,
9 min read
Make String repeating after every K characters by replacing characters at missing place
Given an string S and integer K and there are also some missing character i.e. ( _ ), the task is make the string S repeating after every K characters by replacing the appropriate character at missing place i.e. ( _ ). If it is not possible then print -1. Note: If there are multiple possible strings, then print the smallest lexicographically string
7 min read
Find the maximum repeating number in O(n) time and O(1) extra space
Given an array of size n, the array contains numbers in the range from 0 to k-1 where k is a positive integer and k &lt;= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. The expected time complexity is O(n) an
8 min read
Find the smallest missing number
Given a sorted array of n distinct integers where each integer is in the range from 0 to m-1 and m &gt; n. Find the smallest number that is missing from the array. Examples: Input: {0, 1, 2, 6, 9}, n = 5, m = 10 Output: 3 Input: {4, 5, 10, 11}, n = 4, m = 12 Output: 0 Input: {0, 1, 2, 3}, n = 4, m = 5 Output: 4 Input: {0, 1, 2, 3, 4, 5, 6, 7, 10},
15 min read
Find the one missing number in range
Given an array of size n. It is also given that range of numbers is from smallestNumber to smallestNumber + n where smallestNumber is the smallest number in array. The array contains number in this range but one number is missing so the task is to find this missing number. Examples: Input: arr[] = {13, 12, 11, 15}Output: 14 Input: arr[] = {33, 36,
9 min read
Find the smallest positive number missing from an unsorted array : Hashing Implementation
Given an unsorted array with both positive and negative elements including 0. The task is to find the smallest positive number missing from the array in O(N) time. Examples: Input: arr[] = {-5, 2, 0, -1, -10, 15} Output: 1 Input: arr[] = {0, 1, 2, 3, 4, 5} Output: 6 Input: arr[] = {1, 1, 1, 0, -1, -2} Output: 2 We can use hashing to solve this prob
5 min read
Find the smallest positive number missing from an unsorted array | Set 3
Given an unsorted array with both positive and negative elements. The task is to find the smallest positive number missing from the array. Examples: Input: arr[] = {2, 3, 7, 6, 8, -1, -10, 15} Output: 1 Input: arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 } Output: 4 Input: arr[] = {1, 1, 0, -1, -2} Output: 2 Approach : We have already discussed some of the
6 min read
Find the last two missing digits of the given phone number
Given eight digits of a phone number as an integer N, the task is to find the missing last two digits and print the complete number when the last two digits are the sum of given eight digits.Examples: Input: N = 98765432 Output: 9876543244Input: N = 10000000 Output: 1000000001 Approach: Get the eight digits of the phone number from N one by one usi
5 min read
Find the missing number in unordered Arithmetic Progression
Given an unsorted array arr[] of N integers that are in Arithmetic Progression, the task is to print the missing element from the given series. Examples: Input: arr[] = {12, 3, 6, 15, 18} Output: 9 Explanation: The elements given in order are: 3, 6, 12, 15, 18. Hence missing element is 9. Input: arr[] = {2, 8, 6, 10} Output: 4 Explanation: The elem
13 min read
three90RightbarBannerImg