Find any one of the multiple repeating elements in read only array | C ++ program to find one of the repeating elements in a read only array ; Function to find one of the repeating elements ; Size of blocks except the last block is sq ; Number of blocks to incorporate 1 to n values blocks are numbered from 0 to range - 1 ( both included ) ; Count array maintains the count for all blocks ; Traversing the read only array and updating count ; arr [ i ] belongs to block number ( arr [ i ] - 1 ) / sq i is considered to start from 0 ; The selected_block is set to last block by default . Rest of the blocks are checked ; after finding block with size > sq method of hashing is used to find the element repeating in this block ; checks if the element belongs to the selected_block ; repeating element found ; return - 1 if no repeating element exists ; Driver Program ; read only array , not to be modified ; array of size 6 ( n + 1 ) having elements between 1 and 5
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findRepeatingNumber ( const int arr [ ] , int n ) { int sq = sqrt ( n ) ; int range = ( n / sq ) + 1 ; int count [ range ] = { 0 } ; for ( int i = 0 ; i <= n ; i ++ ) { count [ ( arr [ i ] - 1 ) / sq ] ++ ; } int selected_block = range - 1 ; for ( int i = 0 ; i < range - 1 ; i ++ ) { if ( count [ i ] > sq ) { selected_block = i ; break ; } } unordered_map < int , int > m ; for ( int i = 0 ; i <= n ; i ++ ) { if ( ( ( selected_block * sq ) < arr [ i ] ) && ( arr [ i ] <= ( ( selected_block + 1 ) * sq ) ) ) { m [ arr [ i ] ] ++ ; if ( m [ arr [ i ] ] > 1 ) return arr [ i ] ; } } return -1 ; } int main ( ) { const int arr [ ] = { 1 , 1 , 2 , 3 , 5 , 4 } ; int n = 5 ; cout << " One ▁ of ▁ the ▁ numbers ▁ repeated ▁ in " " ▁ the ▁ array ▁ is : ▁ " << findRepeatingNumber ( arr , n ) << endl ; }