Finding the unpaired element in an array

Given an integer array there are odd number of elements (each are between 1 and 100). Except for one all others have a duplicate in the array.

ex : [1, 3, 4, 5, 7, 6, 7, 5, 3, 1, 4]

in here only unpaired element is 6. Target is to find the unpaired element of this array.

We can use the Exclusive Or operation to solve this.

The property we are going to use is for an integer 'a' the vale a^a is zero and 0^a is 'a'. When we get the XOR of the given array elements altogether the answer will be the isolated element.

int notPaired(int[] n) {
    int ans = 0 ;
    for (int e:n)
        ans ^= e;
    return ans;
}

Read More

Bit Masking

Lightweight, small sets of Booleans (native support in C/C++/Java). An integer is stored in a computer’s memory as a sequence/string of bits.

" In computer science, a mask is data that are used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word (etc.) can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation " [Mask (computing)]

The binary representations can be used to hold information about subsets of a set.

Ex:  Consider the set/list A = {a, b, c, d, e, f} or set/list B = {10, 20, 25, 15, 30, 40}

We can represent the set B as {1, 1, 1, 1, 1, 1} (the sub set which has all the element)
Sub set {20, 15} of set B can be represent as {0, 1, 0, 1, 0, 0} (20 in decimal format)

• We can multiply/divide using bit shifting

int s = 34;         // 0100010
int a = 34 << 1;    // 1000100 ; this is equal to 34*2 ; 100010 << 1 => 1000100
int b = 34 >> 1;    // 0010001 ; this is equal to 34/2 ; 100010 >> 1 => 0010001
int c = 34 >> 2;    // 0001000 ;

//Notice that the truncation in the shift right operation automatically rounds the division-by-2 down

• Set/turn on the j-th item (0-based indexing) of the set. Use the bitwise OR operation S |= (1 << j)

// set = {a,b,c,d,e,f,g}
int s = 34;                 // 0100010 : sub-set = {b,f}
int j = 3;                  // the index we need to turn on , means include 'd', since 0-based
int newSet = s | (1 << j);  // 0101010 : sub-set = {b,d,f}

• Set/turn on the j-th item (0-based indexing) of the set. Use the bitwise OR operation S |= (1 << j)

// set = {a,b,c,d,e,f,g}
int s = 34;                 // 0100010 : sub-set = {b,f}
int j = 3;                  // the index we need to turn on , means include 'd', since 0-based
int newSet = s | (1 << j);  // 0101010 : sub-set = {b,d,f}

• To clear/turn off the j-th item of the set. Use bitwise AND operation S &= ~(1 << j)

int s = 38;  // 100110
int j = 2;  // 0-based index
int a = ~(1 << j);  // 111011
int res = s & a;  // 100010

• To check if the j-th item of the set is on, use the bitwise AND operation T = S & (1 << j)

int s = 38;   // 100110
// is 2nd item is on
int j = 2;
int a = (1 << j); // 000100
int t = s & a;  // 000100 , not zero, to be precise it is (t = a) so 2nd item is on
  
// is 3nd item is on
j = 3;
a = (1 << j);  // 001000
t = s & a;  // 000000 , zero , so 2nd item is off

• To toggle (flip the status of) the j-th item of the set, use the bitwise XOR operation S ^= (1 << j)

int s = 40;  // 101000
int j = 2;
int a = (1 << 2); // 000100
s = s ^ a;  // 101100 , turned on
s = s ^ a;  // 101000 , turned off

• To get the value of the least significant bit that is on (first from the right), use T = (S & (~S))

int s = 40;  // 00000000000000000000000000101000
int nS = -40; // 11111111111111111111111111011000 (two’s complement)
int t = s & nS; // 1000 , 8, 3rd bit from the right is on

• To turn on all bits in a set of size n, use S = (1 << n) - 1
• Iterate through all subsets of a set of size n

int n = 5;
for ( int x = 0; x < (1 << n); ++x ){
 // loop will go for (1 << n) turns
}

• Example of usage

 
for (int i = 0; i < (1 << n); ++i) {  // for each subset, O(2^n)
 for (int j = 0; j < n; ++j) {   // check membership, O(n)
  if ((i & (1 << j)) != 0) {   // test if bit ‘j’ is turned on in subset ‘i’ ?
   // if yes, process ‘j’
  }
 }
}

References : Competitive Programming books

Read More