Find Duplicates of array using bit array | C ++ program to print all Duplicates in array ; A class to represent an 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; class BitArray { int * arr ; public : BitArray ( ) { } BitArray ( int n ) { arr = new int [ ( n >> 5 ) + 1 ] ; } bool 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 ) ; } void checkDuplicates ( int arr [ ] , int n ) { BitArray ba = BitArray ( 320000 ) ; for ( int i = 0 ; i < n ; i ++ ) { int num = arr [ i ] ; if ( ba . get ( num ) ) cout << num << " ▁ " ; else ba . set ( num ) ; } } } ; int main ( ) { int arr [ ] = { 1 , 5 , 1 , 10 , 12 , 10 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; BitArray obj = BitArray ( ) ; obj . checkDuplicates ( arr , n ) ; return 0 ; }