n-Repeated element in size 2n Array

n-repeated element in size 2n array

Difficulty: Medium

Asked In: Google

Discussed Solution Approaches

• Brute force approach using a Hash Table
• Efficient approach using pigeon hole principle

Key takeaway from this coding problem

This is a good interview problem to learn optimization using the mathematical approach. Sometimes interesting mathematical insights into the problem can help us to get efficient solutions.

Let’s understand the problem

In an array X[] of size 2n, there are n+1 unique elements, and exactly one of these elements is repeated n times. Return the element repeated n times.

Examples:

Input: X[] = [1,2,2,3]
Output: 2
Input: X[] = [2,1,2,5,3,2,2,4] 
Output: 2
Input: X[] = [5,1,5,2,5,3,5,4,6,5]
Output: 5

Brute force approach using a Hash Table

A simple approach would be — Traverse the array and count the frequency of each element using the extra array or using the hash table. During the traversal, if we found the element with a count larger than 1, we return that element. Why are we returning the element with a count larger than 1? (Think!)

Algorithm Pseudo Code

int repeatedNTimes(int X[], int n)
{
    Hash Table H
    int repeated_element
    for(int i = 0; i < n; i = i + 1)
    {
        H[X[i]] = H[X[i]] + 1
        if(H[X[i]] > 1)
        {
            repeated_element = X[i]
                break
        } 
   }
   return repeated_element
}

Time and Space Complexity Analysis

The traversal of the array takes time proportional to the number of elements in the array. At each iteration, we are doing constant operations because inserting and searching in hash table takes O(1) time. Hence, Time Complexity = O(n). We are using O(n) extra space to store the frequency of elements in the hash table. Hence, Space Complexity = O(n).

Efficient approach using pigeon hole principle

Algorithm Idea

The idea behind the algorithm is simple — if an element is repeated, then it must be the element that has been repeated n times because all other elements are unique! So, as given in the problem, we know there is an element “x” that appears n times in an array of size 2n.

Average gap = [(a2 — a1) + (a3 — a2) +…(an — a(n-1))]/(n-1).
Here a2, a3,…a(n-1) cancel out each other.
Hence, Average gap = (an — a1)/(n-1)

As array size is 2n, max possible value of an = 2n — 1, min possible value of a1 = 0. If we put values of an and a1 in the above formula, we can get the maximum uppar limit of the average gap.

Average gap <= (2n - 1)/(n-1)
The value of (2n - 1)/(n-1) <= 3
- Equality holds when n = 2
- for all n > 2, it is less than 3
So, Average gap <= 3

Therefore, from the above analysis there must exist atleast two x’s such that their gap is at most 3. Simply stating: If half the array is repeated, it doesn’t matter how we shuffle it; for one of the repeated elements, there has to be another repeated element at least three positions away; otherwise, the array isn’t 2n.

Algorithm Steps

• Create three windows of gap lengths 1, 2, and 3.
• For each window, traverse the array and compare the first and last elements of the window.
• If equality holds then, this must be our repeated element.

Algorithm Pseudo Code

int repeatedNTimes(int X[], int n)
{
    for(int k = 1; k <= 3; k = k + 1)
    {
        for(int i = 0; i < n - k; i = i + 1)
        {
            if(X[i] == X[i + k])
                return X[i]
        }
   }
}

Time and Space Complexity Analysis

We are using two nested loops where the outer loop is running constant time, i.e., three times only. We are doing one comparison operation at each iteration of the inner loop, i.e., the constant number of operations. So in the worst case, the outer loop runs three times, and we need to traverse each element via the inner loop. Time complexity = Time complexity of the outer loop * Time complexity of the inner loop = O(1)*O(n) = O(n).

We are not using any extra space. Hence, Space Complexity = O(1)

Possible questions by the Interviewer: Ideas to Think!

• What is the pigeonhole principle? How can we use it in problem-solving?
• Can we solve this problem by sorting the input? If yes, then what would be the time and space complexity for this approach?
• Can we solve this problem efficiently using some other approach?
• What would be the worst and best case input for both approaches?
• Can we further optimize the above approach? Is it sufficient to compare each element with its two right neighbors instead of 3?
• Let’s design a randomized algorithm — randomly pick two array elements and check whether they come from different cells and have the same value. If they do, then return true. So after how many numbers of repetition algorithm succeeds with probability 1–1/n? Out of n² possible combinations of picking two elements, how many will result in success?

Comparisons of Time and Space Complexities

• Brute force approach: Time = O(n), Space = O(n)
• Using pigeon hole principle : Time = O(n), Space = O(1)

Problems for practice using a single scan

• Valid Mountain
• Remove duplicates from sorted array
• A Product Array Puzzle
• Chocolate Distribution Problem
• Best Time to Buy and Sell Stock
• Sort an array in the waveform
• Number of jumps for a thief to cross walls
• Find the number of subarrays with even sum
• Double the first element and move zero to end

Reviewer: Shubham Gautam (https://shubhamsuper30.medium.com)

If you have any ideas/queries/doubts/feedback, please comment below or write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!