## Google Interview Question for Software Developers

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

Say , SUM(n) = n*(n-1)/2

Observations :
----------------------

(1) -i == (2's complement of i) + 1

(2) (i & -i) == 1 if i is odd

(3) (i & -i) == 2^x if i is even ; x = number of trailing 0s in binary representation of i

Odd case :
-----------------

*** How many (i,j) (i<j) pairs will give (i & -i) == (j & -j) == 1 ??

Ans : SUM(50) = 1225 ;
--------

How?
----------

There are 50 odd numbers in range [0,100).

for (i == 1) => 49 odd pairs
for (i == 3) => 48 odd pairs
for (i == 5) => 47 odd pairs
and so on...

so, 49 + 48 + 47 + ....... + 1 = SUM(50) = 1225 ;

Even Case:
------------------

How many pairs (i,j) (i<j) with same number of trailing zeroes in their binary rep. ?

Ans :
--------

How many numbers in range [0,100)

=> with 1 trailing 0 == 99/2 - 99/4 = 49-24 = 25;

=> with 2 trailing 0s == 99/4 - 99/8 = 24-12 = 12;

=> with 3 trailing 0s == 99/8 - 99/16 = 12-6 = 6;

=> with 4 trailing 0s == 99/16 - 99/32 = 6-3 = 3;

=> with 5 trailing 0 == 99/32 - 99/64 = 3-1 = 2;

So, Number of pairs with same number of trailing 0's :

SUM(25) + SUM(12) + SUM(6) + SUM(3) + SUM(2) = 385

So, Total : 1225 + 385 = 1610
----------------------------------------------------------X----------------------------------------------

Thanks for posting this nice problem (^_^)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.