How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at SoFi.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at SoFi during technical interviews.

Count numbers with same popcount up to all-ones bound

Q: Count numbers with same popcount up to all-ones bound

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.

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.

For any positive integer `n`, define `f(n)` as the smallest integer greater than or equal to `n` whose binary representation consists only of `1` bits. If `n` has bit-length `k`, then `f(n) = 2^k - 1`. Given a positive integer `n`, let `popcount(x)` be the number of set bits in `x`. Count how many integers `m` satisfy all of the following: - `1 <= m <= f(n)` - `m != n` - `popcount(m) = popcount(n)` Return this count.

Constraints

`1 <= n <= 10^18`
Target time complexity: `O(log n)`
`n` fits in at most 60 bits

Examples

Input: (5,)

Expected Output: 2

Explanation: `5` is `101`, so `k = 3` and `f(n) = 7` (`111`). The numbers from `1` to `7` with exactly two set bits are `3`, `5`, and `6`. Excluding `5`, the answer is `2`.

Input: (7,)

Expected Output: 0

Explanation: `7` is `111`, so it already equals `f(n)`. The only number from `1` to `7` with three set bits is `7` itself, so excluding it leaves `0`.

Input: (1,)

Expected Output: 0

Explanation: `1` is `1`, so `f(n) = 1`. The only number in range is `1` itself, and it must be excluded.

Input: (8,)

Expected Output: 3

Explanation: `8` is `1000`, so `k = 4` and `f(n) = 15` (`1111`). The numbers with one set bit are `1`, `2`, `4`, and `8`. Excluding `8`, the answer is `3`.

Input: (10,)

Expected Output: 5

Explanation: `10` is `1010`, so `k = 4` and `popcount(n) = 2`. There are `C(4, 2) = 6` numbers from `0` to `15` with exactly two ones. Since `0` is not among them and `10` must be excluded, the answer is `6 - 1 = 5`.

Input: (13,)

Expected Output: 3

Explanation: `13` is `1101`, so `k = 4` and `popcount(n) = 3`. The numbers from `1` to `15` with three set bits are `7`, `11`, `13`, and `14`. Excluding `13`, the answer is `3`.

Input: (576460752303423488,)

Expected Output: 59

Explanation: This is `2^59`, which has bit-length `60` and popcount `1`. Among all numbers from `1` to `2^60 - 1`, there are exactly `60` powers of two, so excluding `n` leaves `59`.

Hints

If `n` has bit-length `k`, then every number from `0` to `2^k - 1` can be viewed as a binary string of length `k` by allowing leading zeros.
How many length-`k` binary strings contain exactly `popcount(n)` ones?

Quick Overview

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.