Binary based problems

Find the number of set bits in the binary equivalent of a decimal number. The solution is required to be O(1) in both time and space. here is a slick solution. Although it is claimed here that it is nearly O(1), I’m not sure the judges would have accepted it.

For any unsigned number b, n is the number of signed bits, and n is calculated as follows:

for(n=0; b; b >>= 1)
if (b & 1) n++;

Un more. From an infinte bit stream, determine whether the decimal equivalent of the binary obtained so far is divisible by three.

Sum the even and odd bits separately. If their difference is divisible by three, so is the number. You can obtain the result by considering the number is represented as Summatuion over(3-1)^n instead of the usual Sum over 2^n, and then expanding using binomial expansion.

Too bad, this didn’t strike me during the event. More problems will be posted. You are free to request or even send interesting Qs to me.


The Chameleons Problem

At one point, a remote island’s population of chameleons was divided as follows:

* 13 red chameleons
* 15 green chameleons
* 17 blue chameleons

Each time two different colored chameleons would meet, they would change their color to the third one. (i.e.. If green meets red, they both change their color to blue.) is it ever possible for all chameleons to become the same color? why or why not? If the number iof chameleons are a,b and c., is it possible to arrive at a condition for this to be possible??

Here is the solution:

let f(a,b,c) = |a-b| + |b-c| + |c-a|.

Then for each operation, the f() value changes by 0,3,6; anyway the changes is 3k. So if finally all have the same color,

then f() = 2(a+b+c).

In the case a=13, b=15, c=17, f()=8;
Finally we need f()=2(13+15+17)=90.

This implies 8+3k = 90. This is impossible for an integer value of k.

If a=6, b=6, c=33,

Intially, f()=0+27+27=54

Final value would be f()=2*(45).

54+3k=90 is possible when k=12.

I guess that solves it.

Kurukshetra 08 and its side effects

Kurukshetra 08

Kurukshetera 08! is come and gone. Our team was one of the three selected for the finals of Project K. I guess, our project on Number plate recognition was impressive. The team Root(-1), originally the team name of Lenin, now our team, took third place in iCode. But it is not of the spoils of war that has forced me to write a blog article. (duh,, I haven’t written one in ages) It was the K!OSPC, the OnSite programming Contest that is prompting to write these lines.

We messed up!!! Thats the short of it. Every team that got selected in iCode made it through to round 2 of OSPC. All that is, expect ours. Questions were totally the kind you’d expect in a tech interview. And we were like “Dude!!!!????” And I had to do a hell lot of searching just to get to the answer to one of them. The truth is that forums are great. But if all you want is one answer straight away, forums are a waste of time. People just keep dragging the pages, sometimes getting nowhere. So that’s why I’ve decided, I’ll keep a collection of the most interesting questing questions i meet with and put up its solution once I find it. Only the solution.

As it is in most cases, answers are open to contention. But the idea is to keep it is as far away from a forum as possible. Just a ready reference. Thats all.