Home » Technical Interview Questions » Hashing Interview Questions » Find any one of the multiple repeating elements in read only array

Find any one of the multiple repeating elements in read only array


the problem “Find any one of the multiple repeating elements in read only array” states that suppose you are given a read-only array of size (n+1). An array is containing the integers from 1 to n. Your task is to find out any one of the repeated elements in the read-only array.

Example

Find any one of the multiple repeating elements in read only array

n = 5
arr[] = [1,2,4,2,3,5]
2

Explanation

This is the only repeated element in the read-only array.

n = 9
arr[] = [1,2,4,6,3,5,7,8,9,9]
9

Explanation

This is the only repeated element in the read-only array.

Algorithm

  1. Set “squareroot” to sqrt(n).
  2. Set range to (n / squareroot) + 1.
  3. Create an array of a size range.
  4. Count and store the frequency of each element with this (freqCount[(arr[i] – 1) / squareroot]++).
  5. Set “currentBlock” to range-1.
  6. While i < range-1.
    1. If freqCount[i] > squareroot, then do currentBlock = i and break.
  7. Declare a map.
  8. Traverse in a map to check for elements that belong to “currentBlock”.
    1. Then put the arr[i] and increase the value of the map’s key’s value.
    2. If a key’s value found greater than 1 then return arr[i].
  9. Else return -1(no element found).

Explanation

We have given a question to find out the repeated element present in an array in which all the integers range from 1 to n and the size of an array is n+1. Since it shows the presence of one repeated element that’s why it has a size of n+1.

A simple solution is to create a HashMap and keep the frequency count of each of the elements. But this solution requires O(N) time and O(N) space. Can we do better than this?

READ  K-th Distinct Element in an Array

We can use an approach that is similar to that of square root decomposition. This approach will reduce our space complexity to O(sqrt(N)). We create an array of size sqrt(N) + 1. And keep increment the indices corresponding to the values as per the formula arr(i-1)/sqrt(n). After doing this, we will surely find out an index that has a frequency greater than sqrt(N). Now we will use the previous method but only for the elements belonging to this range.

Hashing and some basic mathematics are used in the solution to the problem. To find out the repeated element we will pass an array and a value 1 less than the size of the array. Let’s take an example to solve this:

Array[]= {6 ,1 , 2, 3, 5, 4, 6}, n=6

If the size is n+1 then we will pass n to it. Now we have to find out the square root of n and store it to some variable say squareroot=2. Now we have to find out the range of the array. We are going to create an array say freqCount of size ‘range=4’, we will find the range by (n/squareroot) + 1.

We will count the frequencies of each element within the range of array that we created by traversing. Every time we traverse we will follow freCount[(arr(i)-1)/squareroot]++ .

We will end up having the following values in our freqCount array.

freqCount: [2,2,3,0]

Setting up currentBlock to range -1 that is 3. We will traverse the freqCount array. If we find the value greater than squareroot in the array. We find that at 2nd index of freqCount and set currentBlock to i and break. We will declare a hashmap and traverse each element of the input array and check out if any of the element belongs to the currentBlock and sqaureroot, if yes then we put it in a map and return that value of arr[i].

READ  Print all subarrays with 0 sum

Our output will be: 6

C++ code to Find any one of the multiple repeating elements in read only array

#include <unordered_map>
#include<iostream>
#include<math.h>
using namespace std;

int getRepeatedNumber(int arr[], int len)
{
    int squareroot = sqrt(len);
    int range = (len / squareroot) + 1;
    int count[range] = {0};

    for (int i = 0; i <= len; i++)
    {
        count[(arr[i] - 1) / squareroot]++;
    }
    int currentBlock = range - 1;
    for (int i = 0; i < range - 1; i++)
    {
        if (count[i] > squareroot)
        {
            currentBlock = i;
            break;
        }
    }
    unordered_map<int, int> m;
    for (int i = 0; i <= len; i++)
    {
        if ( ((currentBlock * squareroot) < arr[i]) && (arr[i] <= ((currentBlock + 1) * squareroot)))
        {
            m[arr[i]]++;
            if (m[arr[i]] > 1)
                return arr[i];
        }
    }
    return -1;
}
int main()
{
    int arr[] = { 6,1,2, 3, 5, 4, 6 };
    int n = 6;

    cout << "Repeated number(s) in the array is:"<< getRepeatedNumber(arr, n) << endl;
}
Repeated number(s) in the array is:6

Java code to Find any one of the multiple repeating elements in read only array

import java.util.*;
class arrayRepeatedElements
{
    public static int getRepeatedNumber(int[] arr, int len)
    {
        int squareroot = (int) Math.sqrt(len);
        int range = (len / squareroot) + 1;
        int freqCount[] = new int[range];
        for (int i = 0; i <= len; i++)
        {
            freqCount[(arr[i] - 1) / squareroot]++;
        }
        int currentBlock = range - 1;
        for (int i = 0; i < range - 1; i++)
        {
            if (freqCount[i] > squareroot)
            {
                currentBlock = i;
                break;
            }
        }
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i <= len; i++)
        {
            if ( ((currentBlock * squareroot ) < arr[i]) && ( arr[i] <= ((currentBlock + 1) * squareroot)))
            {
                freq.put(arr[i], 1);
                if (freq.get(arr[i])== 1)
                    return arr[i];
            }
        }
        return -1;
    }
    public static void main(String args[])
    {
        int[] arr = { 6,1, 2, 3, 5, 4, 6 };
        int n = 6;
        System.out.println("Repeated number(s) in the array is:"+getRepeatedNumber(arr, n));
    }
}
Repeated number(s) in the array is:6

Complexity Analysis

Time Complexity

O(N) where “N” is the (length of array – 1) i.e., n – 1. Because we have to traverse all the elements.

READ  Cumulative Frequency of Count of Each Element in an Unsorted Array

Space Complexity

sqrt(N) where “N” is the (length of array – 1) i.e., n-1. Because of the nature of the algorithm. First, we did computation for sections equal to the size of sqrt(N).

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup