Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Implementation in Python
2.3.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.3.
Implementation in Python
3.3.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the use of sizeof () function in C++?
4.2.
How does accumulate function work?
4.3.
What is the formula to calculate the sum of 'n' natural numbers?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find the only repetitive element between 1 to n-1

Author Anju Jaiswal
0 upvote

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 : 1

Brute 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

The problem to find the only repetitive element can be solved by subtracting the array sum from the sum of all integers from 1 to (N-1) to find the only repetitive element in the array.

Sn = n*(n-1)/2 is the sum of the first N-1 natural numbers.

Pseudocode

Set sum to 0.
While i < n, traverse the whole array.
     Sum = sum + arr [i].
Return sum-(n*(n-1))/2.

 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
  
int find_Repetitive_element(int arr[], int n)
{
  // Find array sum and subtract sum
  // first n-1 natural numbers from it
  // to find the result.
  int arrSum = 0;
  for(int i = 0; i < n; i++)
      arrSum += arr[i];
  int sn = (((n)*(n-1))/2);
  return arrSum - sn;
}
  
// 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):
      
    # Find array sum and subtract sum
    # first n-1 natural numbers from it
    # to find the result.
    return sum(arr) -(((n - 1) * n) // 2)
  
# 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)  only once we are traversing through the array to calculate the sum of the array and subtracting it with the sum from 1 to N-1 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.

Also read, Rabin Karp Algorithm

Frequently Asked Questions

What is the use of sizeof () function in C++?

The sizeof keyword is a compile-time operator for determining the size of a variable or data type in bytes.

Syntax: sizeof (data type)

How does accumulate function work?

This function returns the sum of all the values lying in a range between [first, last) with the variable sum.  

Syntax - accumulate(first, last, sum);

What is the formula to calculate the sum of 'n' natural numbers?

Sum of n terms of Arithmetic Progression(AP) = n/2[2a + (n – 1)d]

The first term of AP is denoted by 'a,' and the product of the difference between the second and first terms is denoted by 'd,' also known as common difference, and (n-1), where n is the number of terms to be added.

Conclusion

This article discussed the different approaches to find the only repetitive element between 1 to n-1, starting with the brute first approach and then efficient approach with examples and its C++  and Python code.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Binary Search in Sorted Vector of Pairs
Next article
Find the subarray with the least average
Live masterclass