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.
Table of Contents
Example
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
- Set “squareroot” to sqrt(n).
- Set range to (n / squareroot) + 1.
- Create an array of a size range.
- Count and store the frequency of each element with this (freqCount[(arr[i] – 1) / squareroot]++).
- Set “currentBlock” to range-1.
- While i < range-1.
- If freqCount[i] > squareroot, then do currentBlock = i and break.
- Declare a map.
- Traverse in a map to check for elements that belong to “currentBlock”.
- Then put the arr[i] and increase the value of the map’s key’s value.
- If a key’s value found greater than 1 then return arr[i].
- 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?
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].
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.
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).