Find the only repetitive element using sorting

Sort the given input array. Traverse the array and if value of the ith element is not equal to i+1, then the current element is repetitive as value of elements is between 1 and N-1 and every element appears only once except one element.

Follow the below steps to solve the problem:

Sort the given array.
Traverse the array and compare the array elements with its index
- if arr[i] != i+1, it means that arr[i] is repetitive, So Just return arr[i].
Otherwise, the array does not contain duplicates from 1 to n-1, In this case, return -1

Below is the implementation of the above approach:

C++

// CPP program to find the only repeating
// element in an array where elements are
// from 1 to N-1.
#include <bits/stdc++.h>
using namespace std;
 
int findRepeating(int arr[], int N)
{
    sort(arr, arr + N); // sort array
 
    for (int i = 0; i < N; i++) {
 
        // compare array element with its index
        if (arr[i] != i + 1) {
            return arr[i];
        }
    }
    return -1;
}
 
// driver's code
int main()
{
    int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << findRepeating(arr, N);
    return 0;
}
// this code is contributed by devendra solunke

Java

// Java program to find the only repeating
// element in an array where elements are
// from 1 to N-1.
 
import java.util.Arrays;
 
public class GFG {
    static int findRepeating(int[] arr, int N)
    {
        Arrays.sort(arr); // sort array
       
        for (int i = 0; i < N; i++) {
           
            // compare array element with its index
            if (arr[i] != i + 1) {
                return arr[i];
            }
        }
        return -1;
    }
 
    // Driver's code
    static public void main(String[] args)
    {
        int[] arr
            = new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
        int N = arr.length;
       
          // Function call
        int repeatingNum = findRepeating(arr, N);
        System.out.println(repeatingNum);
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Python3

# Python3 program to find the only
# repeating element in an array where
# elements are from 1 to N-1.
 
 
def findRepeating(arr, N):
    arr.sort()
    for i in range(1, N):
        if(arr[i] != i+1):
            return arr[i]
 
 
# Driver's Code
if __name__ == "__main__":
  arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
  N = len(arr)
 
  # Function call
  print(findRepeating(arr, N))
 
# This code is contributed by Arpit Jain

C#

// C# program to find the only repeating element in an array
// where elements are from 1 to N-1.
 
using System;
 
public class GFG {
 
    static int findRepeating(int[] arr, int N)
    {
        Array.Sort(arr); // sort array
        for (int i = 0; i < N; i++) {
            // compare array element with its index
            if (arr[i] != i + 1) {
                return arr[i];
            }
        }
        return -1;
    }
 
      // Driver's code
    static public void Main()
    {
        int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
        int N = arr.Length;
       
          // Function call
        int repeatingNum = findRepeating(arr, N);
        Console.WriteLine(repeatingNum);
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

Javascript

<script>
//Javascript program to find the only repeating
// element in an array where elements are
// from 1 to N-1.
function findRepeating(arr, N){
    arr.sort();
    for (let i = 0; i < N; i++) {
           
    // compare array element with its index
        if (arr[i] != i + 1) {
              return arr[i];
            }
        }
        return -1;
}
           // Driver code
let arr= [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let N = arr.length;
 
// Function call
console.log(findRepeating(arr, N));
      
// This code is contributed by aarohirai2616.
</script>

Output

Time complexity: O(N * log N)
Auxiliary Space: O(1)

Find the only repetitive element between 1 to N-1

Given an array of size N filled with numbers from 1 to N-1 in random order. The array has only one repetitive element. The task is to find the repetitive element.

Examples:

Input: a[] = {1, 3, 2, 3, 4}
Output: 3
Explanation: The number 3 is the only repeating element.

Input: a[] = {1, 5, 1, 2, 3, 4}
Output: 1

Naive Approach: To solve the problem follow the below idea:

Use two nested loops. The outer loop traverses through all elements and the inner loop check if the element picked by the outer loop appears anywhere else.

Below is the implementation of the above approach:

C++

// C++ program to find the only repeating
// element in an array where elements are
// from 1 to N-1.
#include <bits/stdc++.h>
using namespace std;
 
int findRepeating(int arr[], int N)
{
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (arr[i] == arr[j])
                return arr[i];
        }
    }
}
 
// Driver's code
int main()
{
    int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << findRepeating(arr, N);
    return 0;
}
// This code is added by Arpit Jain

Java

// Java program to find the only repeating
// element in an array where elements are
// from 1 to N-1.using System;
public class GFG {
    static int findRepeating(int[] arr)
    {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j])
                    return arr[i];
            }
        }
        return -1;
    }
 
    // Driver's code
    static public void main(String[] args)
    {
 
        // Code
        int[] arr
            = new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
        int repeatingNum = findRepeating(arr);
 
        // Function call
        System.out.println(repeatingNum);
    }
}
 
// This code is contributed by phasing17

Python3

# Python3 program to find the only
# repeating element in an array where
# elements are from 1 to N-1.
 
 
def findRepeating(arr, N):
    for i in range(N):
        for j in range(i + 1, N):
            if (arr[i] == arr[j]):
                return arr[i]
 
 
# Driver's Code
if __name__ == "__main__":
  arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
  N = len(arr)
 
  # Function call
  print(findRepeating(arr, N))
 
# This code is contributed by Arpit Jain

C#

// C# program to find the only repeating
// element in an array where elements are
// from 1 to N-1.
using System;
 
public class GFG {
    static int findRepeating(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++) {
            for (int j = i + 1; j < arr.Length; j++) {
                if (arr[i] == arr[j])
                    return arr[i];
            }
        }
        return -1;
    }
 
    // Driver's code
    static public void Main()
    {
        int[] arr
            = new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
       
          // Function call
        int repeatingNum = findRepeating(arr);
        Console.WriteLine(repeatingNum);
    }
}
 
// This code is contributed by Mohd Nizam

Javascript

<script>
//Javascript program to find the only repeating
// element in an array where elements are
// from 1 to N-1.
function findRepeating(arr, N){
    for (let i = 0; i <N; i++) {
            for (let j = i + 1; j < N; j++) {
                if (arr[i] == arr[j])
                    return arr[i];
            }
}
}
             // Driver code
let arr= [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let N = arr.length;
 
// Function call
console.log(findRepeating(arr, N));
 
// This code is contributed by aarohirai2616.
</script>        

Output

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

Find the only repetitive element using sorting

C++

Java

Python3

C#

Javascript

Find the only repetitive element between 1 to N-1

C++

Java

Python3

C#

Javascript

Categories

Contact US

Find the only repetitive element using sorting

C++

Java

Python3

C#

Javascript

Find the only repetitive element between 1 to N-1

C++

Java

Python3

C#

Javascript

Similar Reads

Categories

Contact US