Bird
Raised Fist0

What is the time complexity of the Brian Kernighan's bit counting trick approach when counting set bits for all numbers from 0 to n?

medium🪤 Complexity Trap Q13 of Q15
Bit Manipulation - Counting Bits (0 to N)
What is the time complexity of the Brian Kernighan's bit counting trick approach when counting set bits for all numbers from 0 to n?
AO(n * k) where k is the average number of set bits per number
BO(n) because each number is processed in constant time
CO(n * log n) because each number requires checking all bits
DO(n^2) due to nested loops over bits and numbers
Step-by-Step Solution
Solution:

  1. Step 1: Identify loops and operations

    Outer loop runs n+1 times; inner loop runs as many times as set bits in each number.

  2. Step 2: Analyze average inner loop iterations

    Each iteration clears one set bit, so total inner loop iterations over all numbers is proportional to total set bits, roughly n * k.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Counting bits per number depends on number of set bits, not all bits [OK]
Quick Trick: Time depends on total set bits, not total bits [OK]
Common Mistakes:
MISTAKES
  • Assuming O(n log n) because of bit length
  • Thinking each number is constant time
  • Confusing nested loops as quadratic
Trap Explanation:
PITFALL
  • O(n log n) looks plausible since numbers have log n bits, but Kernighan's trick only loops over set bits.
Interviewer Note:
CONTEXT
  • Tests understanding of bit-level operation costs and average case complexity.
Master "Counting Bits (0 to N)" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Bit Manipulation Quizzes
Bitwise AND of Numbers Range - Bitwise AND of Numbers Range - Quiz 5medium Power of Four - Power of Four - Quiz 3easy Power of Four - Power of Four - Quiz 14medium Single Number (XOR Self-Cancellation) - Single Number (XOR Self-Cancellation) - Quiz 12easy Single Number (XOR Self-Cancellation) - Single Number (XOR Self-Cancellation) - Quiz 7medium Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 2easy Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 7medium Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 8hard Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 3easy UTF-8 Validation - UTF-8 Validation - Quiz 13medium