Find the Only Repetitive Element Between 1 to N-1

Difficulty Level Easy
Frequently asked in CouponDunia Delhivery GreyOrange Info Edge LinkedIn Nagarro SAP Labs
Array Hash SearchingViews 1872

In finding the only repetitive element between 1 to N-1 problem we have given an array of random integers within a range from 1 to n-1. There will be one number that is repeated. Your task is to find that number.

Example

Input

[2,3,4,5,2,1]A

Output

2

Explanation

2 is the element which comes twice in an array.

 

Algorithm for find the Only Repetitive Element Between 1 to N-1

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

Explanation for find the Only Repetitive Element Between 1 to N-1

We have given a problem( Find the Only Repetitive Element Between 1 to N-1 ) statement that asks to find out that number which is repeated in an array. We are going to simply use Sum Formula. Using Sum Formula, we can easily identify the repeated element. As by the name we get to know that Sum Formula means simply sum up the values.

We, here in the loop start to traverse the array from the 0th position to the end of the loop until we visit the last array element. With every iteration and for each value of array[i] we are going to add it with sum and store it to the sum so that when we iterate over it next time we will get the summed up value and not the initialized value of sum as 0. So, by every iteration, we have some values in it stored as a sum.

We just need to make a formula that gives a repeated element or we can say it just returns an extra element that comes in the series. Suppose we have a series given from 1 to 5 contiguously, when we add all the numbers it gives the sum of all numbers and without having any repeated element in the series. And we return the difference of sum – (n*(n-1))/2, which is our sum formula.

Let us consider an example:

arr=[2,3,4,5,2,1], sum=0

Starting from 0, we can traverse the whole loop visiting each element –>

i=0 ;

sum=sum+arr[i] => sum=2

i=1 ;

sum=sum+arr[i] => sum=5

i=2 ;

sum=sum+arr[i] => sum=9

i=3 ;

sum=sum+arr[i] => sum=14

i=4 ;

sum=sum+arr[i] => sum=16

i=5 ;

sum=sum+arr[i] => sum=17

and we just return sum-(n * (n-1))/2 that is 17- (6*(6-1))/2.

17 – 15 = 2, which is our required output.

 

Find the Only Repetitive Element Between 1 to N-1

Implementation to find the Only Repetitive Element Between 1 to N-1

C++ Program

#include<iostream>
using namespace std;
int getRepeatedElement(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = sum + arr[i];
    }
    return sum-(((n - 1) * n)/2);
}
int main()
{
    int arr[] = {1,5,3,2,6,4,7,8,4};
    int len = sizeof(arr)/sizeof(arr[0]);
    cout<<(getRepeatedElement(arr, len));
    return 0;
}

4

Java Program

class repetitiveElement
{
    public static int getRepeatedElement(int[] arr, int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum = sum + arr[i];
        }
        return sum-(((n - 1) * n)/2);
    }
    public static void main(String args[])
    {
        int[] arr = {1,5,3,2,6,4,7,8,4};
        int len = arr.length;
        System.out.println(getRepeatedElement(arr, len));
    }
}

4

Complexity Analysis for find the Only Repetitive Element Between 1 to N-1

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(1) because we don’t use any auxiliary space here.

References

Translate »