Find Duplicates of array using bit array | A class to represent array of bits using array of integers ; Constructor ; Divide by 32. To store n bits , we need n / 32 + 1 integers ( Assuming int is stored using 32 bits ) ; Get value of a bit at given position ; Divide by 32 to find position of integer . ; Now find bit number in arr [ index ] ; Find value of given bit number in arr [ index ] ; Sets a bit at given position ; Find index of bit position ; Set bit number in arr [ index ] ; Main function to print all Duplicates ; create a bit with 32000 bits ; Traverse array elements ; Index in bit array ; If num is already present in bit array ; Else insert num ; Driver Code
class BitArray : NEW_LINE INDENT def __init__ ( self , n ) : NEW_LINE INDENT self . arr = [ 0 ] * ( ( n >> 5 ) + 1 ) NEW_LINE DEDENT def get ( self , pos ) : NEW_LINE INDENT self . index = pos >> 5 NEW_LINE self . bitNo = pos & 0x1F NEW_LINE return ( self . arr [ self . index ] & ( 1 << self . bitNo ) ) != 0 NEW_LINE DEDENT def set ( self , pos ) : NEW_LINE INDENT self . index = pos >> 5 NEW_LINE self . bitNo = pos & 0x1F NEW_LINE self . arr [ self . index ] |= ( 1 << self . bitNo ) NEW_LINE DEDENT DEDENT def checkDuplicates ( arr ) : NEW_LINE INDENT ba = BitArray ( 320000 ) NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT num = arr [ i ] NEW_LINE if ba . get ( num ) : NEW_LINE INDENT print ( num , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT ba . set ( num ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 5 , 1 , 10 , 12 , 10 ] NEW_LINE checkDuplicates ( arr ) NEW_LINE DEDENT