## Sub-sequences (ICPC 2011 Amritapuri Online Contest)

*Problem Statement:*Β You are given a sequence of N numbers A[1..N]. Consider a sub-sequence (of continuous or non-continuous elements in the same order as given) such that the bitwise AND of all the numbers of the sub-sequence is equal to the bitwise OR of all the numbers of the sub-sequence. Amongst all such sub-sequences, find the sub-sequence that has the maximum sum of the numbers, and print this maximum sum.

Limits: 1<=A[i]<=10000

Hmm. So what are your first thoughts? You want to traverse over all the sub-sequences? Wrong! That would take hell lot of time. We’ll do it in O(n). All you need to do is pay attention to the properties of the bitwise AND and bitwise OR operator. These are two mutually exclusive operators. By using this term here, I mean to specify that *no two different numbers can have the same result after their OR or AND*. You can prove this by taking a few examples (Exercise left to you π )

So the only AND and OR operations to satisfy the equality conditions can be performed on the same number itself. Your subsequences are thus reduced to those having the same number (and its duplicates). Hence, you can simply do the following :

1. Find number of occurrences of each element in the array, store it is OCCURRENCE[i] (corresponding to number i )

2. Find the maximum value of OCCURRENCE[i]*i by scanning through all the array positions.

This maximum value is your answer! π Once again, note why sub-sequences of duplicates are being made. It is because of the condition that AND of the subsequence should be equal to their OR.

It was an easy one but showed a nice Bit Manipulation property. π

## Counting number of valid zeros in binary representation of a number

This one is actually a question suggested by a dear friend. And a pretty neat one. What we need is to find out the number of *valid*Β zeros in the binary representation of Β a number. Valid zeros would be those who have atleast one 1 to their left.

For example, 000010101 (13 in decimal) has only 2 valid zeros. People might go on to solve this in different ways. Some might find the binary representation of the number and literally count the valid 0s. They might use comparitively complex things such as bitset (STL) for this or even strings.

However, the correct (read best) way to solving this is pretty simple and utilizes Bit Manipulations. You just keep finding if the* least significant bit (LSB)* is 0 till the time the *number* isn’t zero. I’ll write a simple pseudo-code for this,

int count=0;

int mask=1;

while ( INPUT_NUMBER ) //till number doesn’t become zero

{

if (INPUT_NUMBER & mask == 0) //checking if LSB is 0

{

count++;

}

INPUT_NUMBER = INPUT_NUMBER>>1; //right shifting by 1 to get next bit

}

Woah! That was a simple one. And damn efficient at that. Do you now realize how simple things can become with bit manipulations?! π

## Bit Manipulation (Overview)

“What? That title isn’t a question like you promised.” – Yep, it isn’t. I just wanted to give a short introduction of Bit Manipulation so that it might be easier for you to understand the term when I have used it in the future. An application of bit manipulation was already shown in the previous post (Find the only element in array which does not have a duplicate).

So if you don’t know it yet, all bit manipulation is about is playing around with bits to get the desired result. The most used operators for such manipulations are **|** (bitwise OR), **&** (bitwise AND), **^** (XOR), **>>** (right shift), **<<** (left shift).

Hopefully, everyone will be familiar with the operation of the first 3 operators. I’ll just explain the way shift operators function.

2<<3 would give you 16. Why? In binary 2=10, **shifting it right** by 3 bits, we get 10000 which equals 16. Simple as that. So right shift multiplies your number by 2 raised to the number of bits you shift.

On the other hand. 16>>3 gives two. The logic is exactly opposite to the one for right shit. Thus,** left shift** ends up dividing a number by 2 raised to the number of bits you shift. Easy-peasy!

You will be amazed to see the applications of such bit-manipulations to problems. Some problems are rendered so easy with the use of these operators that it would almost make you laugh. Other problems (**like finding ‘a*7’ for a given ‘a’ without using *,/,+**) necessarily require the use of bit manipulations. We will soon discuss more applications where bit manipulations make your life easier. π

PS: The solution for the question in **bold** is –

b=a<<3; print b-a; //in essence, multiplying number by 8 and then subtracting it once from the result of the shifting π

*More cool stuff follows soon.*

## Find the only element in an array which does not have a duplicate. (Only occurs once)

While this question might seem eerily similar to the last one, it is vastly different. Here, you have an array in which every element has a duplicate except one element. For example,

2, 2, 3, 4, 5, 9, 5, 4, 9, 1, 3

Here, 1 is your expected answer since it does not have a duplicate. So how would you go about tackling this question? I will point out three approaches :

1. **Sort** the array. It will take **O(n lg n) time** with a sorting method like Quick Sort (or one of the others we discussed previously). Once the array is sorted, you just need to move through the array once and compare every pair of consecutive elements. The first pair that isn’t equal will be your answer. Sorting the earlier example, we get,

1, 2, 2, 3, 3, 4, 4, 5, 5, 9, 9

You can quickly find that 1 occurs only once by this kind of comparison.

2. **Counting** the number of times a number occurs by utilizing another array. But this can only be used when you have an fixed range within which the elements can be. Even if we have such a range given, this way takes **O(n) of both time and space**. Can we do better?

3. Yes, we can do better. The best method will take only **time O(n)** and utilizes** bit manipulation**. All you need to do is move through the array once and XOR each element. In the previous example, we would do,

2^2^3^4^5^9^5^4^9^1^3 (XOR sign – ^)

The result will be 1, i.e., your answer. Why? XOR has the property of setting bit as zero if the two bits being XORed are same. Also, it follows the commutative property. The above expression is equivalent to,

1^2^2^3^3^4^4^5^5^9^9

Hence, all duplicates will give a zero. And zero XORed with your no-duplicates-for-it number will give you the number itself. Tada! π

Nice, eh?!