How should I practice Count Numbers with the Same Set-Bit Count?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Count Numbers with the Same Set-Bit Count associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Bit Manipulation

Count Numbers with the Same Set-Bit Count

Learn this problem

● Medium

MicrosoftFULLTIMEOA

See Microsoft hiring insights

Problem statement

You are given a positive integer n. Define f(n) as the smallest integer greater than or equal to n whose binary representation consists entirely of 1 bits.

Count the positive integers x that satisfy all of the following conditions:

x <= f(n)
x != n
x and n contain the same number of set bits in their binary representations

Return the count modulo 1,000,000,007.

Complete countSameBitNumbers for the given integer n.

Function

countSameBitNumbers(n: int) → int

Examples

Example 1

n = 6return = 2

f(6) = 7, whose binary representation is 111. The integers other than 6 with two set bits and at most 7 are 3 (011) and 5 (101).

Example 2

n = 10return = 5

f(10) = 15. Among the six four-bit patterns containing two set bits, one represents n itself, so five other integers qualify.

Example 3

n = 7return = 0

The only positive integer at most 7 with three set bits is 7, which must be excluded.

Constraints

0 < n < 2^31