Introduction
Today's problem, i.e., –"Find the only repetitive element between 1 to n-1," is highly asked in product-based companies. We'll go over all options, including brute force and the most efficient solution.
Let's get started with the problem statement without further ado.
Problem Statement
We are given an unsorted array arr[] of size N containing values ranging from 1 to N-1, with one value appearing twice in the array. Our goal is to find the only repetitive element between 1 to N-1.
Example
Input : a[] = {2, 1, 2, 4, 3}
Output : 2
Input : a[] = {5, 1, 1, 2, 3, 4}
Output : 1Brute Force Approach
This is the naive approach to find the only repetitive element between 1 to N-1.
Two nested loops are used. The outside loop iterates through all elements, while the inner loop checks whether the element chosen by the outer loop appears elsewhere.
Pseudocode
For index = 0,index <= size of array, index+=1{
For j = index+1, j<= size of array , j+=1{
If array[index] is equal to array[j]
Return the element array[index]
}
} Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int find_Repetitive_element(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 code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << find_Repetitive_element(arr, n);
return 0;
}
Implementation in Python
def find_Repetitive_element(arr, n):
for i in range(0,n):
for j in range(i+1,n):
if arr[i]==arr[j]:
return arr[i]
# Driver Code
arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]
n = len(arr)
print(find_Repetitive_element(arr, n))
Output:
8
Complexity Analysis
Time Complexity: O(n*n) because we are traversing the array twice, the inner loop checks whether the element chosen by the outer loop appears elsewhere to find the only repetitive element where 'n' is the array's total number of elements
Space Complexity: O(1) because the variables used are of constant space, and no additional space is used here.
117+ registered 