Encuentre el elemento repetido en una array de tamaño N que consta de primeros M números naturales

Dada una array arr[] de tamaño N , que contiene una permutación de números del 1 al M , así como un elemento que se repite (una o más veces), la tarea es encontrar el elemento que se repite.

Ejemplos:

Entrada: arr[]={2, 6, 4, 3, 1, 5, 2}, N=7
Salida:
2
Explicación: En arr[], todos los elementos del 0 al 6 aparecen una vez, excepto el 2, que se repite una vez .

Entrada: arr[]={2, 1, 3, 1, 1, 1}, N=6
Salida:
1

Enfoque ingenuo: el enfoque ingenuo sería ordenar la array y buscar elementos adyacentes que sean iguales.

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)

Enfoque: siga los pasos a continuación para resolver el problema:

1. Inicialice dos variables M y suma para almacenar el elemento máximo y la suma de la array respectivamente.
2. Atraviese array arr y haga lo siguiente:
   1. Agregar el elemento actual a la suma
   2. Compare el elemento actual con M para calcular el elemento máximo .
3. Almacene la suma de la permutación de 1 a M en una variable, digamos, sum1 , usando la fórmula:

Sum of elements from 1 to X= X*(X+1)/2

1. Calcule la respuesta como la diferencia entre sum y sum1 dividida por el número de caracteres adicionales, es decir, (sum-sum1)/(NM) .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the repeating character in a given
// permutation
int repeatingElement(int arr[], int N)
{
    // variables to store maximum element and sum of the
    // array respectively.
    int M = 0, sum = 0;
    for (int i = 0; i < N; i++) {
 
        // calculate sum of array
        sum += arr[i];
 
        // calculate maximum element in the array
        M = max(M, arr[i]);
    }
 
    // calculating sum of permutation
    int sum1 = M * (M + 1) / 2;
 
    // calculate required answer
    int ans = (sum - sum1) / (N - M);
    return ans;
}
// Driver code
int main()
{
    // Input
    int arr[] = { 2, 6, 4, 3, 1, 5, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << repeatingElement(arr, N) << endl;
    return 0;
}

// Java Program for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to calculate the repeating character in a given
  // permutation
  public static int repeatingElement(int arr[], int N)
  {
     
    // variables to store maximum element and sum of the
    // array respectively.
    int M = 0, sum = 0;
    for (int i = 0; i < N; i++) {
 
      // calculate sum of array
      sum += arr[i];
 
      // calculate maximum element in the array
      M = Math.max(M, arr[i]);
    }
 
    // calculating sum of permutation
    int sum1 = M * (M + 1) / 2;
 
    // calculate required answer
    int ans = (sum - sum1) / (N - M);
    return ans;
  }
 
  // Driver code
  public static void main (String[] args)
  {
     
    // Input
    int arr[] = { 2, 6, 4, 3, 1, 5, 2 };
    int N = arr.length;
 
    // Function call
    System.out.println(repeatingElement(arr, N));
  }
}
 
// This code is contributed by lokeshpotta20

# Python 3 program for the above approach
 
# Function to calculate the repeating character in a given
# permutation
def repeatingElement(arr, N):
   
    # variables to store maximum element and sum of the
    # array respectively.
    M = 0
    sum = 0
    for i in range(N):
       
        # calculate sum of array
        sum += arr[i]
 
        # calculate maximum element in the array
        M = max(M, arr[i])
 
    # calculating sum of permutation
    sum1 = M * (M + 1) // 2
 
    # calculate required answer
    ans = (sum - sum1) // (N - M)
    return ans
 
# Driver code
if __name__ == '__main__':
   
    # Input
    arr = [2, 6, 4, 3, 1, 5, 2]
    N = len(arr)
 
    # Function call
    print(repeatingElement(arr, N))
     
    # This code is contributed by SURENDRA_GANGWAR.

// C++ program for the above approach
using System;
 
// Function to calculate the repeating character in a given
// permutation
public class GFG
{
    public static int repeatingElement(int[] arr, int N)
    {
       
        // variables to store maximum element and sum of the
        // array respectively.
        int M = 0, sum = 0;
        for (int i = 0; i < N; i++) {
 
            // calculate sum of array
            sum += arr[i];
 
            // calculate maximum element in the array
            M = Math.Max(M, arr[i]);
        }
 
        // calculating sum of permutation
        int sum1 = M * (M + 1) / 2;
 
        // calculate required answer
        int ans = (sum - sum1) / (N - M);
        return ans;
    }
   
    // Driver code
    public static void Main()
    {
        // Input
        int[] arr = { 2, 6, 4, 3, 1, 5, 2 };
        int N = 7;
 
        // Function call
        Console.WriteLine(repeatingElement(arr, N));
    }
}
 
// This code is contributed by Sohom Das

// JavaScript program for the above approach
 
        // Function to calculate the repeating character in a given
        // permutation
        function repeatingElement(arr, N)
        {
         
            // variables to store maximum element and sum of the
            // array respectively.
            let M = 0, sum = 0;
            for (let i = 0; i < N; i++) {
 
                // calculate sum of array
                sum += arr[i];
 
                // calculate maximum element in the array
                M = Math.max(M, arr[i]);
            }
 
            // calculating sum of permutation
            let sum1 = parseInt(M * (M + 1) / 2);
 
            // calculate required answer
            let ans = parseInt((sum - sum1) / (N - M));
            return ans;
        }
        // Driver code
 
        // Input
        let arr = [2, 6, 4, 3, 1, 5, 2];
        let N = arr.length;
 
        // Function call
        document.write(repeatingElement(arr, N));
 
  // This code is contributed by Potta Lokesh
    </script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)