Bird
Raised Fist0

When using Brian Kernighan's algorithm to count set bits for all integers from 0 to n, what is the overall time complexity in terms of n?

medium💡 Conceptual Thinking Q5 of Q15
Bit Manipulation - Counting Bits (0 to N)
When using Brian Kernighan's algorithm to count set bits for all integers from 0 to n, what is the overall time complexity in terms of n?
AO(n log n)
BO(n)
CO(n^2)
DO(log n)
Step-by-Step Solution
Solution:

  1. Step 1: Understand Brian Kernighan's algorithm

    It counts set bits by repeatedly clearing the least significant set bit in a number.

  2. Step 2: Analyze per number cost

    Each number i requires as many operations as the number of set bits in i.

  3. Step 3: Sum over all numbers from 0 to n

    The total operations equal the sum of set bits in all numbers from 0 to n, which is O(n log n) because average bits per number is proportional to log n.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Sum of bits over n numbers ~ n * log n [OK]
Quick Trick: Sum of bits over n numbers is n log n [OK]
Common Mistakes:
MISTAKES
  • Assuming O(n) because each number is processed once
  • Confusing bit count with number of numbers
  • Ignoring that bit count per number varies with log n
Trap Explanation:
PITFALL
  • O(n) looks plausible but ignores bit counting cost per number
Interviewer Note:
CONTEXT
  • Tests understanding of time complexity of bit counting algorithms
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