Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-148 · FOCUSED PRACTICE

Counting Bits

Starter · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1525838 deterministic checks. Learner drafts are not executed.

Understand the problem

For every integer i from zero through n inclusive, return the number of one bits in the ordinary nonnegative binary representation of i.

  • n is an int in 0..1000000. Negative or larger values throw IllegalArgumentException before allocation. This numeric/output limit is explicit because the result stores n+1 entries.
  • Return a fresh int[] of length n+1 with answer[i] equal to i’s population count. n=0 returns [0], not an empty array. Each call owns an independent result that the caller may mutate.
  • All counted values are nonnegative. Leading zero bits contribute nothing, and no string conversion or built-in population-count call is used in the optimized reference. This API builds every prefix answer rather than counting bits in one arbitrary signed int.

Examples

  1. Input: n=2
    Output: [0,1,1]

    Zero has no one bits; one and binary ten each have one.

  2. Input: n=5
    Output: [0,1,1,2,1,2]

    Binary eleven has two; binary one hundred has one.

  3. Input: n=0
    Output: [0]

    The inclusive range still contains zero.

Before you start

  • Unsigned right shift and least-significant-bit extraction
  • Dependency order for dynamic programming arrays

Recognize the structure

Every positive binary integer splits into its remaining higher bits and one final bit. Removing the least-significant bit produces floor(i/2), a smaller integer whose answer is already available in increasing order. The removed bit contributes either zero or one. Reuse that subproblem instead of rescanning all bit positions for every value. This is tabulation over numeric states, with the answer table itself serving as the dependency store.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

No unsaved text changes · 110/20,000 characters

Self-review

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Write i as 2q+b with b either zero or one.

Hint 2

What happens to its binary digits when you shift right once?

Hint 3

Use the already computed count at i>>>1 and add its last bit i&1.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Count each value independently by clearing set bits

For each value, repeatedly replace remaining with remaining&(remaining−1), incrementing a counter until zero. Subtracting one flips the lowest one and following zeros; AND clears that lowest one while preserving higher ones. This computes each count independently, with no reuse across values. Its total cost is the sum of individual population counts, bounded by O(n log(n+1)) in a variable-width model. Tests use binary-text digit counting as a separate oracle.

Improve the baseline

Define an inclusive table and its zero base

bits[i] counts one bits in i, for every i in [0,n]. Java zero initialization establishes bits[0]=0. The output has n+1 entries; with the explicit cap, n+1 cannot overflow and the allocation remains bounded.

Remove exactly the final binary digit

For nonnegative value, value>>>1 is floor(value/2). The expression value&1 isolates the final bit. Therefore bits[value]=bits[value>>>1]+(value&1). Parentheses keep both operations and their intended roles obvious.

Use increasing values as a dependency order

For every positive value, value>>>1 is strictly smaller. Its count is finalized before the current assignment, so a single ascending loop computes every entry exactly once. No recursion, extra cache, or repeated binary conversion is required.

Read powers of two and boundaries correctly

An even value contributes zero after shifting; an odd value contributes one. At a power of two, the parent is a smaller power of two and the final count stays one. The preceding number has many one bits, so population counts are not monotone in their numeric index.

Account for the returned storage honestly

The table is both required output and reference dependency storage. Its Θ(n+1) entries are unavoidable when every answer must be returned. Only loop variables are additional auxiliary space; a claim of constant total space would hide the requested output.

Why it is correct

Zero base

The binary representation of zero contains no one bits. The freshly zero-initialized table therefore has the correct first answer even when the loop has no iterations.

Binary decomposition

For positive i=2q+b with b in {0,1}, q’s binary digits are precisely i’s digits except the final b. The count of one bits is popcount(q)+b. Shift and mask recover q and b exactly under the nonnegative contract.

Induction, termination, and ownership

Assume entries below i are correct. The dependency q=floor(i/2)<i is available, and decomposition establishes entry i. A finite ascending loop fills the whole inclusive range. Returning the newly allocated array provides an independent result on each call.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    private Solution() {}
    private static void validate(int n) {
        if (n < 0 || n > 1_000_000) throw new IllegalArgumentException("n must be 0..1000000");
    }
    public static int[] countBits(int n) {
        validate(n);
        int[] bits = new int[n + 1];
        for (int value = 1; value <= n; value++) {
            bits[value] = bits[value >>> 1] + (value & 1);
        }
        return bits;
    }
    // Count each number independently by clearing its lowest set bit.
    public static int[] baseline(int n) {
        validate(n);
        int[] bits = new int[n + 1];
        for (int value = 1; value <= n; value++) {
            int remaining = value;
            while (remaining != 0) {
                remaining &= remaining - 1;
                bits[value]++;
            }
        }
        return bits;
    }
}

Read the meaningful blocks

Validate before allocation

Reject n outside 0..1000000, including MAX_VALUE, before evaluating an impractical output allocation. The valid n+1 expression is safe.

Allocate the output and retain its zero base

new int[n+1] supplies exactly the requested indices and zero initialization. Starting at one avoids a self-dependency at zero.

Assign from one smaller parent and one bit

The right-hand side reads only finalized output. Parent lookup and bit masking are constant-time operations for this fixed-width contract. Return the same fresh table rather than copying it again.

Complexity

The optimized method takes Θ(n+1) time including output allocation/initialization and uses Θ(n+1) result storage plus O(1) additional auxiliary space. n=0 still allocates one entry and takes constant time.

The baseline takes O((n+1) log(n+2)) bit-clear iterations as a safe variable-width upper bound, or O(W(n+1)) with W=32 fixed Java bits. Thus both are technically linear in n for fixed-width bounded ints, but the recurrence does one transition per value rather than up to its number of set bits. Both return Θ(n+1) entries.

Exact-state walkthroughs

Reveal normal and boundary traces

Even and odd values share a binary parent

Input: 5 · Inclusive population-count array: [0,1,1,2,1,2]

Step 1 of 13: Allocate every inclusive output index and seed zero.

Null entries below mean uncomputed teaching cells; actual Java storage is zero initialized. Only bits[0]=0 is a finalized base.

Counting Bits — a finalized binary parent and one last bit

Phase: initial.

Inclusive range: 0..5. The output contains 6 entries, including zero.

  • 0: 0binary 0
  • 1: uncomputedbinary 1
  • 2: uncomputedbinary 10
  • 3: uncomputedbinary 11
  • 4: uncomputedbinary 100
  • 5: uncomputedbinary 101

Zero has count zero. Every positive cell reads a strictly smaller finalized index. Actual Java storage starts at zero; “uncomputed” distinguishes cells not yet justified by the recurrence. Population counts may drop at powers of two.

The table is required output and belongs to the caller. Each invocation returns a fresh array; only the loop variables are constant auxiliary space.

State after this step
VariableValue
input5
phase"initial"
table[0,null,null,null,null,null]
See the affected Java block
 1 public final class Solution {
 2     private Solution() {}
 3     private static void validate(int n) {
 4         if (n < 0 || n > 1_000_000) throw new IllegalArgumentException("n must be 0..1000000");
 5     }
 6     public static int[] countBits(int n) {
 7         validate(n);
 8         int[] bits = new int[n + 1];
 9         for (int value = 1; value <= n; value++) {
10             bits[value] = bits[value >>> 1] + (value & 1);
11         }
12         return bits;
13     }
14     // Count each number independently by clearing its lowest set bit.
15     public static int[] baseline(int n) {
16         validate(n);
17         int[] bits = new int[n + 1];
18         for (int value = 1; value <= n; value++) {
19             int remaining = value;
20             while (remaining != 0) {
21                 remaining &= remaining - 1;
22                 bits[value]++;
23             }
24         }
25         return bits;
26     }
27 }
28

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Allocate every inclusive output index and seed zero.

    Null entries below mean uncomputed teaching cells; actual Java storage is zero initialized. Only bits[0]=0 is a finalized base.

    input
    5
    phase
    "initial"
    table
    [0,null,null,null,null,null]
  2. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    5
    phase
    "candidate"
    table
    [0,null,null,null,null,null]
    value
    1
    parent
    0
    lastBit
    1
    parentCount
    0
    next
    1
  3. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    5
    phase
    "commit"
    table
    [0,1,null,null,null,null]
    value
    1
    parent
    0
    lastBit
    1
    parentCount
    0
    next
    1
  4. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    5
    phase
    "candidate"
    table
    [0,1,null,null,null,null]
    value
    2
    parent
    1
    lastBit
    0
    parentCount
    1
    next
    1
  5. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    5
    phase
    "commit"
    table
    [0,1,1,null,null,null]
    value
    2
    parent
    1
    lastBit
    0
    parentCount
    1
    next
    1
  6. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    5
    phase
    "candidate"
    table
    [0,1,1,null,null,null]
    value
    3
    parent
    1
    lastBit
    1
    parentCount
    1
    next
    2
  7. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    5
    phase
    "commit"
    table
    [0,1,1,2,null,null]
    value
    3
    parent
    1
    lastBit
    1
    parentCount
    1
    next
    2
  8. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    5
    phase
    "candidate"
    table
    [0,1,1,2,null,null]
    value
    4
    parent
    2
    lastBit
    0
    parentCount
    1
    next
    1
  9. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    5
    phase
    "commit"
    table
    [0,1,1,2,1,null]
    value
    4
    parent
    2
    lastBit
    0
    parentCount
    1
    next
    1
  10. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    5
    phase
    "candidate"
    table
    [0,1,1,2,1,null]
    value
    5
    parent
    2
    lastBit
    1
    parentCount
    1
    next
    2
  11. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    5
    phase
    "commit"
    table
    [0,1,1,2,1,2]
    value
    5
    parent
    2
    lastBit
    1
    parentCount
    1
    next
    2
  12. Return the fresh inclusive count array.

    The table is required output, not hidden constant-space workspace. n=0 returns the explicit [0] base.

    input
    5
    phase
    "complete"
    table
    [0,1,1,2,1,2]
  13. Return the documented outcome.

    Input promises, output ownership, numeric domain, and rounding policy remain separate. Visualization histories and bit strings are excluded from reference workspace.

    result
    [0,1,1,2,1,2]

Crossing a power-of-two boundary

Input: 8 · Inclusive population-count array: [0,1,1,2,1,2,2,3,1]

Step 1 of 19: Allocate every inclusive output index and seed zero.

Null entries below mean uncomputed teaching cells; actual Java storage is zero initialized. Only bits[0]=0 is a finalized base.

Counting Bits — a finalized binary parent and one last bit

Phase: initial.

Inclusive range: 0..8. The output contains 9 entries, including zero.

  • 0: 0binary 0
  • 1: uncomputedbinary 1
  • 2: uncomputedbinary 10
  • 3: uncomputedbinary 11
  • 4: uncomputedbinary 100
  • 5: uncomputedbinary 101
  • 6: uncomputedbinary 110
  • 7: uncomputedbinary 111
  • 8: uncomputedbinary 1000

Zero has count zero. Every positive cell reads a strictly smaller finalized index. Actual Java storage starts at zero; “uncomputed” distinguishes cells not yet justified by the recurrence. Population counts may drop at powers of two.

The table is required output and belongs to the caller. Each invocation returns a fresh array; only the loop variables are constant auxiliary space.

State after this step
VariableValue
input8
phase"initial"
table[0,null,null,null,null,null,null,null,null]
See the affected Java block
 1 public final class Solution {
 2     private Solution() {}
 3     private static void validate(int n) {
 4         if (n < 0 || n > 1_000_000) throw new IllegalArgumentException("n must be 0..1000000");
 5     }
 6     public static int[] countBits(int n) {
 7         validate(n);
 8         int[] bits = new int[n + 1];
 9         for (int value = 1; value <= n; value++) {
10             bits[value] = bits[value >>> 1] + (value & 1);
11         }
12         return bits;
13     }
14     // Count each number independently by clearing its lowest set bit.
15     public static int[] baseline(int n) {
16         validate(n);
17         int[] bits = new int[n + 1];
18         for (int value = 1; value <= n; value++) {
19             int remaining = value;
20             while (remaining != 0) {
21                 remaining &= remaining - 1;
22                 bits[value]++;
23             }
24         }
25         return bits;
26     }
27 }
28

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Allocate every inclusive output index and seed zero.

    Null entries below mean uncomputed teaching cells; actual Java storage is zero initialized. Only bits[0]=0 is a finalized base.

    input
    8
    phase
    "initial"
    table
    [0,null,null,null,null,null,null,null,null]
  2. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,null,null,null,null,null,null,null,null]
    value
    1
    parent
    0
    lastBit
    1
    parentCount
    0
    next
    1
  3. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,null,null,null,null,null,null,null]
    value
    1
    parent
    0
    lastBit
    1
    parentCount
    0
    next
    1
  4. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,1,null,null,null,null,null,null,null]
    value
    2
    parent
    1
    lastBit
    0
    parentCount
    1
    next
    1
  5. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,1,null,null,null,null,null,null]
    value
    2
    parent
    1
    lastBit
    0
    parentCount
    1
    next
    1
  6. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,1,1,null,null,null,null,null,null]
    value
    3
    parent
    1
    lastBit
    1
    parentCount
    1
    next
    2
  7. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,1,2,null,null,null,null,null]
    value
    3
    parent
    1
    lastBit
    1
    parentCount
    1
    next
    2
  8. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,1,1,2,null,null,null,null,null]
    value
    4
    parent
    2
    lastBit
    0
    parentCount
    1
    next
    1
  9. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,1,2,1,null,null,null,null]
    value
    4
    parent
    2
    lastBit
    0
    parentCount
    1
    next
    1
  10. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,1,1,2,1,null,null,null,null]
    value
    5
    parent
    2
    lastBit
    1
    parentCount
    1
    next
    2
  11. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,1,2,1,2,null,null,null]
    value
    5
    parent
    2
    lastBit
    1
    parentCount
    1
    next
    2
  12. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,1,1,2,1,2,null,null,null]
    value
    6
    parent
    3
    lastBit
    0
    parentCount
    2
    next
    2
  13. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,1,2,1,2,2,null,null]
    value
    6
    parent
    3
    lastBit
    0
    parentCount
    2
    next
    2
  14. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,1,1,2,1,2,2,null,null]
    value
    7
    parent
    3
    lastBit
    1
    parentCount
    2
    next
    3
  15. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,1,2,1,2,2,3,null]
    value
    7
    parent
    3
    lastBit
    1
    parentCount
    2
    next
    3
  16. Read the smaller finalized binary parent and removed final bit.

    value=2×parent+lastBit. Since parent<value, increasing iteration order has already finalized the needed count.

    input
    8
    phase
    "candidate"
    table
    [0,1,1,2,1,2,2,3,null]
    value
    8
    parent
    4
    lastBit
    0
    parentCount
    1
    next
    1
  17. Finalize this population count in the output table.

    The assigned cell is now available to future children. Counts need not increase with their numeric indices.

    input
    8
    phase
    "commit"
    table
    [0,1,1,2,1,2,2,3,1]
    value
    8
    parent
    4
    lastBit
    0
    parentCount
    1
    next
    1
  18. Return the fresh inclusive count array.

    The table is required output, not hidden constant-space workspace. n=0 returns the explicit [0] base.

    input
    8
    phase
    "complete"
    table
    [0,1,1,2,1,2,2,3,1]
  19. Return the documented outcome.

    Input promises, output ownership, numeric domain, and rounding policy remain separate. Visualization histories and bit strings are excluded from reference workspace.

    result
    [0,1,1,2,1,2,2,3,1]

Zero remains an explicit result entry

Input: 0 · Inclusive population-count array: [0]

Step 1 of 3: Allocate every inclusive output index and seed zero.

Null entries below mean uncomputed teaching cells; actual Java storage is zero initialized. Only bits[0]=0 is a finalized base.

Counting Bits — a finalized binary parent and one last bit

Phase: initial.

Inclusive range: 0..0. The output contains 1 entries, including zero.

  • 0: 0binary 0

Zero has count zero. Every positive cell reads a strictly smaller finalized index. Actual Java storage starts at zero; “uncomputed” distinguishes cells not yet justified by the recurrence. Population counts may drop at powers of two.

The table is required output and belongs to the caller. Each invocation returns a fresh array; only the loop variables are constant auxiliary space.

State after this step
VariableValue
input0
phase"initial"
table[0]
See the affected Java block
 1 public final class Solution {
 2     private Solution() {}
 3     private static void validate(int n) {
 4         if (n < 0 || n > 1_000_000) throw new IllegalArgumentException("n must be 0..1000000");
 5     }
 6     public static int[] countBits(int n) {
 7         validate(n);
 8         int[] bits = new int[n + 1];
 9         for (int value = 1; value <= n; value++) {
10             bits[value] = bits[value >>> 1] + (value & 1);
11         }
12         return bits;
13     }
14     // Count each number independently by clearing its lowest set bit.
15     public static int[] baseline(int n) {
16         validate(n);
17         int[] bits = new int[n + 1];
18         for (int value = 1; value <= n; value++) {
19             int remaining = value;
20             while (remaining != 0) {
21                 remaining &= remaining - 1;
22                 bits[value]++;
23             }
24         }
25         return bits;
26     }
27 }
28

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Allocate every inclusive output index and seed zero.

    Null entries below mean uncomputed teaching cells; actual Java storage is zero initialized. Only bits[0]=0 is a finalized base.

    input
    0
    phase
    "initial"
    table
    [0]
  2. Return the fresh inclusive count array.

    The table is required output, not hidden constant-space workspace. n=0 returns the explicit [0] base.

    input
    0
    phase
    "complete"
    table
    [0]
  3. Return the documented outcome.

    Input promises, output ownership, numeric domain, and rounding policy remain separate. Visualization histories and bit strings are excluded from reference workspace.

    result
    [0]

Test the contract

  1. Input: n=1
    Output: [0,1]

    Inclusive singleton extension.

  2. Input: n=3
    Output: [0,1,1,2]

    Odd final bit contributes one.

  3. Input: n=8
    Output: [0,1,1,2,1,2,2,3,1]

    Counts drop at the next power of two.

  4. Input: n=-1
    Output: IllegalArgumentException

    Negative range bound.

  5. Input: n=1000001
    Output: IllegalArgumentException

    Reject excessive output before allocation.

Common mistakes and counterexamples

Allocate n entries or omit zero

Counterexample: n=0 must return [0], and n=2 needs index two.

Allocate n+1 and interpret the range inclusively.

Add one after every shift

Counterexample: Even values such as two end in zero and should not add a one.

Add value&1, not a constant.

Use an uncomputed dependency

Counterexample: A decreasing scan would read parent counts before they are finalized.

Fill increasing values because the binary parent is smaller.

Claim the counts rise with the index or total storage is constant

Counterexample: Seven has three one bits while eight has one; returning all answers requires a table.

Distinguish index order from count monotonicity and output storage from scalar workspace.

Follow-ups

Count one arbitrary signed int instead.

Define whether you count the full 32-bit two’s-complement representation. A negative value may have many high one bits, and a signed right-shift loop can fail to terminate. Clearing the lowest set bit or using unsigned shifts supports a fixed-width count.

Use the lowest-set-bit parent recurrence.

bits[i]=bits[i&(i−1)]+1 also reads a smaller finalized index. Prove that the operation removes exactly one set bit and explain why it is a different parent choice with the same output table.

Emit a lazy sequence instead of returning an array.

Output ownership and memory requirements change. Computing each value independently trades repeated bit work for reduced retained output. The current recurrence relies on earlier counts being available; a streaming implementation needs a suitable alternate state or explicit retention policy.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-18 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.