Difficulty: Medium, Asked-in: Google
Key takeaway: An excellent problem to learn time complexity optimization using the mathematical approach. Sometimes mathematical insights into the problem can help us to get efficient solutions.
In an array X[] of size 2n, there are n + 1 unique elements, and exactly one of these elements is repeated n times. Write a code to 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
Solution Idea
A simple approach would be to traverse the array and count the frequency of each element using a hash table. During the traversal, if we found an element with a count larger than 1, we return that element. Why are we returning the element with a count larger than 1? (Think!)
Solution Pseudocode
int repeatedNTimes(int X[], int n)
{
HashTable H
int repeatedElement
for(int i = 0; i < n; i = i + 1)
{
H[X[i]] = H[X[i]] + 1
if(H[X[i]] > 1)
{
repeatedElement = X[i]
break
}
}
return repeatedElement
}
Solution Analysis
Solution Idea
The idea behind the algorithm is: 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, there is an element “x” that appears n times in an array size 2n. How can we use this insight to solve this problem efficiently in O(1)? Let's think!
Suppose the indexes of all x’s in the array are X1, X2, ... Xn, where X1 < X2,…< Xn. Let calculate the average gap between all consecutive x’s:
As array size is 2n, so max possible value of Xn = 2n - 1, min possible value of X1 = 0. If we put the values of Xn and X1 in the above formula, we will get the max upper limit of the average gap.
Therefore, from the above analysis, there must exist at least two x’s in array X[] 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 size isn’t 2n. Think!
Solution Steps
Solution Pseudocode
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]
}
}
}
Solution Analysis
Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!
Given the root of a binary tree, write a program to check whether it is a valid binary search tree (BST) or not. A BST is valid if all nodes in the left subtree have values less than the node’s value, all nodes in the right subtree have values greater than the node’s value, and both left and right subtrees are also binary search trees.
A binary array X[] is given where elements are either 0 or 1. Write a program to find the maximum consecutive ones. The subarray with max continuous 1's can be present anywhere, starting from some index i and ending at some index j. This is an excellent problem to learn problem-solving using the sliding window and a single loop.
Given the root of a Binary Search Tree (BST), write a program to find the absolute minimum difference between the values of any two nodes in the tree. Here node values in the tree can be positive, negative, or zero. This is an excellent problem to learn problem-solving using in-order traversal in a BST.
Given an array, find the next greater element for every element in the array. The next greater element for an element is the first greater element on the right side of the array. This is one of the best problems to learn problem-solving using stack.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.