Find the two repeating elements in a given array using Mathematics

The idea is to calculate the sum and product of elements that are repeating in the array and using those two equations find those repeating elements.

Follow the steps below to solve the problem:

To find the sum of repeating elements (let’s say X and Y) subtract the sum of the first N natural numbers from the total sum of the array i.e. X + Y = sum(arr) – N*(N + 1) / 2
Now, finding the product of repeating elements that is X*Y = P / N!, where P is the product of all elements in the array.
For X – Y = sqrt((X+Y)² – 4*XY)
By solving these two equations X and Y will be calculated.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
/* function to get factorial of n */
int fact(int n);
 
void printRepeating(int arr[], int size)
{
    int S = 0; /* S is for sum of elements in arr[] */
    int P = 1; /* P is for product of elements in arr[] */
    int x, y; /* x and y are two repeating elements */
    int D; /* D is for difference of x and y, i.e., x-y*/
    int n = size - 2, i;
 
    /* Calculate Sum and Product of all elements in arr[] */
    for (i = 0; i < size; i++) {
        S = S + arr[i];
        P = P * arr[i];
    }
 
    S = S - n * (n + 1) / 2; /* S is x + y now */
    P = P / fact(n); /* P is x*y now */
 
    D = sqrt(S * S - 4 * P); /* D is x - y now */
 
    x = (D + S) / 2;
    y = (S - D) / 2;
 
    cout << "Repeating elements are " << x << " " << y;
}
 
int fact(int n) { return (n == 0) ? 1 : n * fact(n - 1); }
 
// Driver code
int main()
{
    int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    printRepeating(arr, arr_size);
    return 0;
}
 
// This code is contributed by rathbhupendra

Java

import java.io.*;
 
class RepeatElement {
    void printRepeating(int arr[], int size)
    {
        /* S is for sum of elements in arr[] */
        int S = 0;
 
        /* P is for product of elements in arr[] */
        int P = 1;
 
        /* x and y are two repeating elements */
        int x, y;
 
        /* D is for difference of x and y, i.e., x-y*/
        int D;
 
        int n = size - 2, i;
 
        /* Calculate Sum and Product of all elements in
         * arr[] */
        for (i = 0; i < size; i++) {
            S = S + arr[i];
            P = P * arr[i];
        }
 
        /* S is x + y now */
        S = S - n * (n + 1) / 2;
 
        /* P is x*y now */
        P = P / fact(n);
 
        /* D is x - y now */
        D = (int)Math.sqrt(S * S - 4 * P);
 
        x = (D + S) / 2;
        y = (S - D) / 2;
 
        System.out.println(
            "The two repeating elements are :");
        System.out.print(x + " " + y);
    }
 
    int fact(int n)
    {
        return (n == 0) ? 1 : n * fact(n - 1);
    }
 
    public static void main(String[] args)
    {
        RepeatElement repeat = new RepeatElement();
        int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 code for Find the two repeating
# elements in a given array
import math
 
 
def printRepeating(arr, size):
 
    # S is for sum of elements in arr[]
    S = 0
 
    # P is for product of elements in arr[]
    P = 1
 
    n = size - 2
 
    # Calculate Sum and Product
    # of all elements in arr[]
    for i in range(0, size):
        S = S + arr[i]
        P = P * arr[i]
 
    # S is x + y now
    S = S - n * (n + 1) // 2
 
    # P is x*y now
    P = P // fact(n)
 
    # D is x - y now
    D = math.sqrt(S * S - 4 * P)
 
    x = (D + S) // 2
    y = (S - D) // 2
 
    print("Repeating elements are ",
          (int)(x), " ", (int)(y))
 
 
def fact(n):
    if(n == 0):
        return 1
    else:
        return(n * fact(n - 1))
 
 
# Driver code
arr = [4, 2, 4, 5, 2, 3, 1]
arr_size = len(arr)
printRepeating(arr, arr_size)
 
 
# This code is contributed by Nikita Tiwari.

C#

using System;
 
class GFG {
 
    static void printRepeating(int[] arr, int size)
    {
        /* S is for sum of elements in arr[] */
        int S = 0;
 
        /* P is for product of elements in arr[] */
        int P = 1;
 
        /* x and y are two repeating elements */
        int x, y;
 
        /* D is for difference of x and y, i.e., x-y*/
        int D;
 
        int n = size - 2, i;
 
        /* Calculate Sum and Product
         of all elements in arr[] */
        for (i = 0; i < size; i++) {
            S = S + arr[i];
            P = P * arr[i];
        }
 
        /* S is x + y now */
        S = S - n * (n + 1) / 2;
 
        /* P is x*y now */
        P = P / fact(n);
 
        /* D is x - y now */
        D = (int)Math.Sqrt(S * S - 4 * P);
 
        x = (D + S) / 2;
        y = (S - D) / 2;
 
        Console.Write("Repeating elements are ");
        Console.Write(x + " " + y);
    }
 
    static int fact(int n)
    {
        return (n == 0) ? 1 : n * fact(n - 1);
    }
 
    // driver code
    public static void Main()
    {
        int[] arr = { 4, 2, 4, 5, 2, 3, 1 };
        int arr_size = arr.Length;
 
        printRepeating(arr, arr_size);
    }
}
// This code is contributed by Sam007

PHP

<?php
 
/* function to get factorial of n */
function fact($n){
   
return ($n == 0)? 1 : $n*fact($n-1);
}
 
function printRepeating($arr, $size)
{
 $S = 0; /* S is for sum of elements in arr[] */
 $P = 1; /* P is for product of elements in arr[] */
 $x; $y; /* x and y are two repeating elements */
 $D;     /* D is for difference of x and y, i.e., x-y*/
 $n = $size - 2;
  
 
/* Calculate Sum and Product of all elements in arr[] */
for($i = 0; $i < $size; $i++)
{
    $S = $S + $arr[$i];
    $P = $P*$arr[$i];
}     
 
$S = $S - $n*($n+1)/2; /* S is x + y now */
$P = $P/fact($n);         /* P is x*y now */
 
$D = sqrt($S*$S - 4*$P); /* D is x - y now */
 
$x = ($D + $S)/2;
$y = ($S - $D)/2;
 
echo "Repeating elements are ".$x." ".$y;
}     
 
 
 
$arr = array(4, 2, 4, 5, 2, 3, 1);
$arr_size = count($arr); 
printRepeating($arr, $arr_size);
?>

Javascript

<script>
 
    function printRepeating(arr , size) 
    {
        /* S is for sum of elements in arr */
        var S = 0;
         
        /* P is for product of elements in arr */
        var P = 1;
         
        /* x and y are two repeating elements */
        var x, y;
         
        /* D is for difference of x and y, i.e., x-y*/
        var D;
         
        var n = size - 2, i;
 
        /* Calculate Sum and Product of all elements in arr */
        for (i = 0; i < size; i++) 
        {
            S = S + arr[i];
            P = P * arr[i];
        }
 
        /* S is x + y now */
        S = S - n * parseInt((n + 1) / 2);
         
        /* P is x*y now */
        P = parseInt(P / fact(n));
        
        /* D is x - y now */
        D = parseInt( Math.sqrt(S * S - 4 * P));
         
 
        x = parseInt((D + S) / 2);
        y = parseInt((S - D) / 2);
 
        document.write("Repeating elements are " + x + " " + y);
    }
 
    function fact(n) 
    {    var ans = false;
        if(n == 0)
            return 1;
        else
            return(n * fact(n - 1));
    }
 
     
    var arr = [4, 2, 4, 5, 2, 3, 1];
    var arr_size = arr.length;
    printRepeating(arr, arr_size);
 
// This code is contributed by 29AjayKumar 
 
</script>

Output

Repeating elements are 4 2

Time Complexity: O(N), Traversing over the array of size N to find the sum and product of the array
Auxiliary Space: O(1)

Find the two repeating elements in a given array

Given an array arr[] of N+2 elements. All elements of the array are in the range of 1 to N. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

Examples:

Input: arr = [4, 2, 4, 5, 2, 3, 1], N = 5
Output: 4 2
Explanation: The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

Input: arr = [2, 1, 2, 1, 3], N = 3
Output: 1 2
Explanation: The above array has n + 2 = 5 elements with all elements occurring once except 1 and 2 which occur twice. So the output should be 1 2.

Naive Approach:

The idea is to use two loops.

Follow the steps below to solve the problem:

In the outer loop, pick elements one by one and count the number of occurrences of the picked element using a nested loop.
Whenever an element is found to be equal to the picked element in nested then print that element.

Below is the implementation of the above approach.

C++

// C++ program to Find the two repeating
// elements in a given array
#include <bits/stdc++.h>
using namespace std;
 
void printTwoRepeatNumber(int arr[], int size)
{
    int i, j;
    cout << "Repeating elements are ";
    for (i = 0; i < size; i++) {
        for (j = i + 1; j < size; j++) {
            if (arr[i] == arr[j]) {
                cout << arr[i] << " ";
                break;
            }
        }
    }
}
 
int main()
{
    int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
   
    printTwoRepeatNumber(arr, arr_size);
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
void printRepeating(int arr[], int size)
{
    int i, j;
    printf(" Repeating elements are ");
    for (i = 0; i < size - 1; i++)
        for (j = i + 1; j < size; j++)
            if (arr[i] == arr[j])
                printf("%d ", arr[i]);
}
 
int main()
{
    int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    printRepeating(arr, arr_size);
    getchar();
    return 0;
}

Java

// Java code to implement the approach
 
import java.io.*;
 
class RepeatElement {
    void printRepeating(int arr[], int size)
    {
        int i, j;
        System.out.print("Repeating Elements are ");
        for (i = 0; i < size - 1; i++) {
            for (j = i + 1; j < size; j++) {
                if (arr[i] == arr[j])
                    System.out.print(arr[i] + " ");
            }
        }
    }
 
    public static void main(String[] args)
    {
        RepeatElement repeat = new RepeatElement();
        int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}

Python3

# Python3 program to Find the two
# repeating elements in a given array
 
 
def printRepeating(arr, size):
 
    print("Repeating elements are", end=' ')
    for i in range(0, size-1):
        for j in range(i + 1, size):
            if arr[i] == arr[j]:
                print(arr[i], end=' ')
 
 
# Driver code
arr = [4, 2, 4, 5, 2, 3, 1]
arr_size = len(arr)
printRepeating(arr, arr_size)
 
# This code is contributed by Smitha Dinesh Semwal

C#

using System;
 
class GFG {
 
    static void printRepeating(int[] arr, int size)
    {
        int i, j;
 
        Console.Write("Repeating Elements are ");
        for (i = 0; i < size - 1; i++) {
            for (j = i + 1; j < size; j++) {
                if (arr[i] == arr[j])
                    Console.Write(arr[i] + " ");
            }
        }
    }
    // driver code
    public static void Main()
    {
        int[] arr = { 4, 2, 4, 5, 2, 3, 1 };
        int arr_size = arr.Length;
 
        printRepeating(arr, arr_size);
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program to Find the two 
// repeating elements in 
// a given array
 
function printRepeating($arr, $size)
{
    $i;
    $j;
    echo " Repeating elements are ";
 
    for($i = 0; $i < $size-1; $i++)
        for($j = $i + 1; $j < $size; $j++)
            if($arr[$i] == $arr[$j])
                echo $arr[$i], " ";
} 
 
// Driver Code
$arr = array(4, 2, 4, 5, 2, 3, 1);
$arr_size = sizeof($arr, 0);
printRepeating($arr, $arr_size);
 
// This code is contributed by Ajit
?>

Javascript

<script>
    function printRepeating(arr , size) 
    {
        var i, j;
        document.write("Repeating Elements are ");
        for (i = 0; i < size-1; i++) 
        {
            for (j = i + 1; j < size; j++) 
            {
                if (arr[i] == arr[j]) 
                    document.write(arr[i] + " ");
            }
        }
    }
 
var arr = [4, 2, 4, 5, 2, 3, 1];
var arr_size = arr.length;
printRepeating(arr, arr_size);
 
// This code is contributed by 29AjayKumar
</script>

Output

Repeating elements are 4 2

Time Complexity: O(N*N), Iterating over the array of size N for all the N elements.
Auxiliary Space: O(1)

Find the two repeating elements in a given array using Mathematics

C++

Java

Python3

C#

PHP

Javascript

Find the two repeating elements in a given array

C++

C

Java

Python3

C#

PHP

Javascript

Categories

Contact US

Find the two repeating elements in a given array using Mathematics

C++

Java

Python3

C#

PHP

Javascript

Find the two repeating elements in a given array

C++

C

Java

Python3

C#

PHP

Javascript

Similar Reads

Categories

Contact US