Find Duplicates of array using bit array | Java program to print all Duplicates in 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
import java . util . * ; import java . lang . * ; import java . io . * ; class BitArray { int [ ] arr ; public BitArray ( int n ) { arr = new int [ ( n >> 5 ) + 1 ] ; } boolean get ( int pos ) { int index = ( pos >> 5 ) ; int bitNo = ( pos & 0x1F ) ; return ( arr [ index ] & ( 1 << bitNo ) ) != 0 ; } void set ( int pos ) { int index = ( pos >> 5 ) ; int bitNo = ( pos & 0x1F ) ; arr [ index ] |= ( 1 << bitNo ) ; } static void checkDuplicates ( int [ ] arr ) { BitArray ba = new BitArray ( 320000 ) ; for ( int i = 0 ; i < arr . length ; i ++ ) { int num = arr [ i ] - 1 ; if ( ba . get ( num ) ) System . out . print ( num + " ▁ " ) ; else ba . set ( num ) ; } } public static void main ( String [ ] args ) throws java . lang . Exception { int [ ] arr = { 1 , 5 , 1 , 10 , 12 , 10 } ; checkDuplicates ( arr ) ; } }