Numbers with K Set Bits

Difficulty: 1900 5000 ms 128 MB

combinatorics digit-dp

Count the integers in [L, R] whose binary representation has exactly K one-bits.

Input: one line with three integers L, R, K.

Output: the count of integers with popcount K.

Constraints:

• 1 ≤ L ≤ R ≤ 10¹⁸
• 0 ≤ K ≤ 60

Sample Tests

1 10 2

5

5 5 2

1

Read the Editorial