Find any one of the multiple repeating elements in read only array | Python 3 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 Code ; read only array , not to be modified ; array of size 6 ( n + 1 ) having elements between 1 and 5
from math import sqrt NEW_LINE def findRepeatingNumber ( arr , n ) : NEW_LINE INDENT sq = sqrt ( n ) NEW_LINE range__ = int ( ( n / sq ) + 1 ) NEW_LINE count = [ 0 for i in range ( range__ ) ] NEW_LINE for i in range ( 0 , n + 1 , 1 ) : NEW_LINE INDENT count [ int ( ( arr [ i ] - 1 ) / sq ) ] += 1 NEW_LINE DEDENT selected_block = range__ - 1 NEW_LINE for i in range ( 0 , range__ - 1 , 1 ) : NEW_LINE INDENT if ( count [ i ] > sq ) : NEW_LINE INDENT selected_block = i NEW_LINE break NEW_LINE DEDENT DEDENT m = { i : 0 for i in range ( n ) } NEW_LINE for i in range ( 0 , n + 1 , 1 ) : NEW_LINE INDENT if ( ( ( selected_block * sq ) < arr [ i ] ) and ( arr [ i ] <= ( ( selected_block + 1 ) * sq ) ) ) : NEW_LINE INDENT m [ arr [ i ] ] += 1 NEW_LINE if ( m [ arr [ i ] ] > 1 ) : NEW_LINE INDENT return arr [ i ] NEW_LINE DEDENT DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 1 , 2 , 3 , 5 , 4 ] NEW_LINE n = 5 NEW_LINE print ( " One ▁ of ▁ the ▁ numbers ▁ repeated ▁ in ▁ the ▁ array ▁ is : " , findRepeatingNumber ( arr , n ) ) NEW_LINE DEDENT