Introduction

This interview question looks simple, but it tests whether you can choose the right bit counting strategy for the actual usage pattern. With 10,000 values of 16 bits, a direct scan is already fast. The interesting part is explaining alternatives for repeated queries and showing clear tradeoffs.

Clarify The Problem Before Coding

Interviewers often expect you to ask one key question first: do we need the count once, or many times for changing ranges. The answer changes the best solution.

• Single total count over the whole array: one pass with popcount is enough.
• Many range queries: preprocess prefix sums of bit counts.
• Many updates plus many queries: use a Fenwick tree or segment tree over per index popcount.

Because each element is 16 bit wide, you can also use a lookup table of size 65,536 when memory is not a concern.

Baseline Solution With Built In Popcount

The cleanest baseline is one pass and a CPU optimized popcount intrinsic.

1#include <stdint.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5int total_set_bits(const uint16_t *arr, int n) {
6    int total = 0;
7    for (int i = 0; i < n; i++) {
8        total += __builtin_popcount((unsigned)arr[i]);
9    }
10    return total;
11}
12
13int main(void) {
14    uint16_t arr[] = {1, 3, 7, 8, 65535};
15    int n = (int)(sizeof(arr) / sizeof(arr[0]));
16    printf("%d\n", total_set_bits(arr, n));
17    return 0;
18}

This runs in linear time and constant extra space. For only 10,000 numbers, this is usually the expected first answer.

Fast Repeated Queries With Prefix Bit Counts

If the interviewer changes the question to many range queries, preprocess once.

1def build_prefix_bit_counts(values):
2    prefix = [0]
3    running = 0
4    for v in values:
5        running += int(v).bit_count()
6        prefix.append(running)
7    return prefix
8
9
10def query_bits(prefix, left, right):
11    if left < 0 or right >= len(prefix) - 1 or left > right:
12        raise ValueError("invalid range")
13    return prefix[right + 1] - prefix[left]
14
15
16if __name__ == "__main__":
17    arr = [1, 3, 7, 8, 15, 16]
18    p = build_prefix_bit_counts(arr)
19    print(query_bits(p, 1, 4))  # bits in indices 1..4

Preprocessing is linear. Each query is constant time.

Lookup Table For 16 Bit Values

Because values are limited to 16 bits, you can precompute popcount for every possible value once and then use table lookup.

1def build_16bit_table():
2    table = [0] * 65536
3    for x in range(1, 65536):
4        table[x] = table[x >> 1] + (x & 1)
5    return table
6
7
8def total_bits_with_table(values, table):
9    return sum(table[v & 0xFFFF] for v in values)
10
11
12if __name__ == "__main__":
13    tbl = build_16bit_table()
14    arr = [0, 1, 2, 3, 65535]
15    print(total_bits_with_table(arr, tbl))

This is still linear in array length, but each element count becomes a very cheap memory read.

How To Talk Through Complexity In Interviews

A strong interview answer usually presents two layers.

1. Immediate correct baseline with clear complexity.
2. Upgrade path when query pattern changes.

For this question:

• Baseline: linear scan and popcount.
• Range query upgrade: prefix sums.
• Heavy update plus query upgrade: Fenwick tree on bit counts.
• Memory rich micro optimization: 16 bit lookup table.

That demonstrates algorithm selection, not only bit tricks.

Edge Cases Worth Mentioning

Mentioning edge cases shows practical maturity.

• Ensure values are treated as 16 bit, especially if input type is wider.
• Avoid signed shift assumptions in low level languages.
• Validate query ranges before prefix subtraction.
• Use a wide enough accumulator if array size can grow beyond the prompt.

Common Pitfalls

• Over engineering with complex trees before confirming query requirements.
• Forgetting that osize is tiny here and baseline already passes comfortably.
• Using floating point or string conversions for bit counting.
• Ignoring integer width and accidentally counting beyond 16 bits.
• Claiming an optimization without stating time and space impact.

Summary

• For one total count, a single pass with popcount is the best first answer.
• For repeated range queries, prefix bit counts give constant time queries.
• With unlimited RAM and 16 bit values, a 65,536 entry lookup table is viable.
• Always adapt the method to query and update patterns.
• Interview strength comes from clear tradeoff reasoning plus correct code.