Interview Question

Staff Hardware Engineer Interview

-Boxborough, MA

Qualcomm

If you have a 600 digit number with only 0's and 1's, and exactly 300 1's, can the number be a square?

AnswerAdd Tags

Interview Answers

6 Answers

5

The answer should be YES: @gustion: your example with 49 (7 pwr2) is correct but with 25 (5 pwr2) is incorrect. 7 in binary is 111 (3 1-bits is half of 6 bits), but 5 in binary is 101 (2 1-bits does not equal half of 6 bits). In general, any binary number with n-bits, half of which are 0's and half are 1's is a square of a binary number with half the number of bits, all being 1-value bits. In addition, the number's magnitude will be n/2-1 1-bits followed by n/2 0-bits followed by the last 1-bit. For example, lets say we have a 16-bit number. The number which will have 8 1-bit and 8 0-bit binary digits and also be a square is: 1111 1110 0000 0001 (7 1-bits followed by 8 0-bits followed by 1-bit) and this number is a square of 1111 1111 Binary number with 600 bits and 300 1-bits will have a magnitude of 299 1-bits followed by 300 0-bits followed by 1-bit, and it will be a square of a 300-bit number with the magnitude of 300 1-bits.

Chris on

0

Well on a simple note, 9's binary is 1001, a 4 digit binary with two 1's and two 0's, and is a perfect square. The same analogy should also be true for any such number.

Anirban on

0

No

Anonymous on

0

I am trying to undersatnd why you say the answer is No. for a 6 bit binary number, of which 3 bits are exactly 1s. 25 and 49 are possible such numbers that happens to be a square... Why can't this possibility extend to a 600 bit binary number?

question on

0

Because (2^n - 1)^2 = 2^(2n) - 2 * (2^n) + 1 = 2^(2n) - 2^(n + 1) + 2^0. Such that bit n + 1 to 2n -1 will be 1, bit n to 1 will be 0, and bit 0 will be 1, which makes it n bits of 1 & n bits of 0. You can test 15^2 = 225 to understand it.

Hao-Yu (Peter) Yang on

0

can someone explain why this pattern works?

dan on

Add Answers or Comments

To comment on this, Sign In or Sign Up.