Count numbers with same popcount up to all-ones bound
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
## Problem
For any positive integer `n`, define `f(n)` as the **smallest integer `>= n` whose binary representation consists only of `1` bits**.
Equivalently, if `k` is the bit-length of `n` (so `2^(k-1) <= n <= 2^k - 1`), then:
- `f(n) = 2^k - 1` (binary: `k` ones)
You are given a positive integer `n`. Let `popcount(x)` be the number of set bits in `x`.
### Task
Count how many integers `m` satisfy all of the following:
- `1 <= m <= f(n)`
- `m != n`
- `popcount(m) = popcount(n)`
Return this count.
### Input
- A positive integer `n`.
### Output
- An integer: the count of valid `m`.
### Constraints
- `1 <= n <= 10^18`
- Target time complexity: `O(log n)`.
### Examples
1) `n = 5` (binary `101`)
- `k=3`, `f(n)=7` (binary `111`)
- Numbers `<=7` with two set bits: `3(011), 5(101), 6(110)`
- Excluding `n=5` → answer `2`
2) `n = 7` (binary `111`)
- `k=3`, `f(n)=7`
- Only number with three set bits is `7` itself → answer `0`
Quick Answer: This question evaluates skill in bit manipulation and combinatorial counting over binary representations in the Coding & Algorithms domain, specifically reasoning about popcount and counting integers up to an all-ones bound.