Katkat
Back

Count Smaller Numbers with Only Zero and One in Base Four

Hudson River TradingData Scientist · Online Assessment
MediumData ScientistOnline AssessmentCoding & Algorithms

Last updated

Count the number of positive integers strictly less than n whose base-4 representation consists only of the digits 0 and 1.

Problem Statement

A positive integer is called fancy if its representation in base 4 contains only the digits 0 and 1 (without leading zeros).

Given a 64-bit positive integer n, return the count of fancy numbers that are strictly less than n.

An algorithm scanning all integers from 1 to n - 1 will exceed the time limit. Your solution should run in logarithmic time with respect to n.

Function Signature

def count_fancy_numbers(n: int) -> int:
    pass

Input & Output Format

  • Input: A single integer n (1 <= n <= 10^18).
  • Output: An integer representing the number of positive fancy integers strictly less than n.

Examples

Example 1

Input: n = 6
Output: 3
Explanation:
The base-4 representations of integers from 1 to 5 are:
- 1 -> "1" (fancy)
- 2 -> "2"
- 3 -> "3"
- 4 -> "10" (fancy)
- 5 -> "11" (fancy)
There are 3 fancy numbers strictly less than 6 (1, 4, and 5).

Example 2

Input: n = 21
Output: 6
Explanation:
21 in base 4 is "111". The positive fancy numbers strictly less than 21 are:
- 1 ("1")
- 4 ("10")
- 5 ("11")
- 16 ("100")
- 17 ("101")
- 20 ("110")
In total, there are 6 such numbers.

Constraints

  • 1 <= n <= 10^18

Hints

Hint 1

Express n in base 4, and observe the one-to-one correspondence between fancy numbers and standard binary representations.

Hint 2

If the first digit of n (from left to right) that is greater than 1 appears at index i, any valid choice of 0 or 1 from that index onward will automatically yield a value strictly less than n.

Hint 3

Truncate or saturate the base-4 representation at the first digit greater than 1 by replacing it and all subsequent digits with 1, then interpret the resulting prefix as a binary integer.

Follow-up questions

  • How would you generalize this solution if the allowed digits were an arbitrary subset of base b (e.g., digits {0, 2} in base 5)?
  • How would the solution change if you needed to find the k-th fancy number rather than counting numbers below n?
  • How can you handle constraints where n is given as an arbitrary-precision integer string of length up to 10^5?