Counting remainders on division by two — Aptitude Question
Counting remainders on division by two: / is integer division. What is printed? Answer and worked solution on CodeKairo.
- Topic: Pseudocode
- Section: Programming MCQs
- Difficulty: Hard
- Time target: 120 seconds
Question
/ is integer division. What is printed?
Function B(Integer n)
Integer c
Set c = 0
While n > 0
Set c = c + (n MOD 2)
Set n = n / 2
End While
Return c
End Function
Print B(45)Options
- 3
- 4
- 5
- 6
Show the answer and the worked solution
Correct answer: B. 4
Worked solution
- The values of n are 45, 22, 11, 5, 2 and 1, giving remainders 1, 0, 1, 1, 0 and 1.
- Those remainders spell 45 in binary as 101101.
- The remainders add up to 1 + 0 + 1 + 1 + 0 + 1 = 4, so 4 is printed.
Answer: 4.
The idea
Repeated division by 2 while collecting the remainders is base conversion, so this routine returns the number of 1 bits. Checking with 45 = 32 + 8 + 4 + 1 confirms four set bits without a trace.
Shortcut. Each 1 bit is an odd value in the halving chain 45, 22, 11, 5, 2, 1, and four of those values are odd.
Common trap. 3 drops the final pass at n = 1, as if the loop ran while n > 1; that last remainder is the leading 1 bit of 101101.