Halving until one — Pseudocode Aptitude Question
Halving until one: In the pseudocode below / is integer division: any fraction is discarded. What is printed? Answer and worked solution on CodeKairo.
- Topic: Pseudocode
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 90 seconds
Question
In the pseudocode below / is integer division: any fraction is discarded. What is printed?
Integer n, count
Set n = 100
Set count = 0
While n > 1
Set n = n / 2
Set count = count + 1
End While
Print countOptions
- 5
- 6
- 7
- 8
Show the answer and the worked solution
Correct answer: B. 6
Worked solution
- n moves 100 → 50 → 25 → 12 → 6 → 3 → 1, because 25 / 2 truncates to 12 and 3 / 2 truncates to 1.
- That is one increment of count for each arrow, and there are 6 of them.
- With n = 1 the condition n > 1 fails, so the loop ends with count = 6.
Answer: 6.
The idea
Repeated halving with truncation is the standard logarithmic loop. Listing the actual integers is faster and safer than reaching for a formula, because truncation makes the count shorter than the exact logarithm.
Shortcut. Truncating halvings from n down to 1 take ⌊log₂ n⌋ steps: 2⁶ = 64 ≤ 100 < 128 = 2⁷, so the loop runs 6 times.
Common trap. 7 comes from counting the seven values 100, 50, 25, 12, 6, 3, 1 instead of the six halvings between them, or from rounding log₂ 100 ≈ 6.6 up instead of down.