Quick Overview

Count positive integers below a strict upper bound whose base-4 representation contains only zeros and ones, without scanning every smaller integer.

Count Smaller Numbers with Only Zero and One in Base Four

Company: Hudson

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

A positive integer is a fancy number if its base-4 representation contains only the digits `0` and `1`. Implement `countFancy(n)`, which returns the number of fancy numbers strictly less than `n`. The input and output use ordinary decimal integers. ### Rules and Constraints - This practice version counts positive integers only; zero is excluded. - Use each integer's usual base-4 representation without leading zeros. Each integer is counted once. - `1 <= n <= 1,000,000,000,000,000`. - The result must be exact. An approach that examines every positive integer below `n` does not meet the intended input scale. ### Example 1 ```text n = 17 Output: 4 ``` The qualifying decimal values are `1`, `4`, `5`, and `16`, whose base-4 representations are `1`, `10`, `11`, and `100`. ### Example 2 ```text n = 5 Output: 2 ``` The values `1` and `4` qualify. Although `5` has base-4 representation `11`, it is excluded by the strict upper bound.

Overview: Count positive integers below a strict upper bound whose base-4 representation contains only zeros and ones, without scanning every smaller integer.

Read the full Hudson Data Scientist interview experience this question came from

A positive integer is a fancy number if its base-4 representation contains only the digits `0` and `1`. Implement `countFancy(n)`, which returns the number of fancy numbers strictly less than `n`. The input and output use ordinary decimal integers. ### Rules and Constraints - This practice version counts positive integers only; zero is excluded. - Use each integer's usual base-4 representation without leading zeros. Each integer is counted once. - `1 <= n <= 1,000,000,000,000,000`. - The result must be exact. An approach that examines every positive integer below `n` does not meet the intended input scale. ### Example 1 ```text n = 17 Output: 4 ``` The qualifying decimal values are `1`, `4`, `5`, and `16`, whose base-4 representations are `1`, `10`, `11`, and `100`. ### Example 2 ```text n = 5 Output: 2 ``` The values `1` and `4` qualify. Although `5` has base-4 representation `11`, it is excluded by the strict upper bound.

Constraints

  • 1 <= n <= 1000000000000000; n and the returned count are exact ordinary decimal integers.
  • Count only positive integers strictly less than n whose usual base-4 representation contains only digits 0 and 1.
  • Zero is excluded, and each value is counted once; leading zeros do not create additional values.
  • Do not enumerate every positive integer below n.

Examples

Input: (17,)

Expected Output: 4

Explanation: Published sample 1: 1,4,5,16 are the four qualifying positive values.

Input: (5,)

Expected Output: 2

Explanation: Published sample 2: only 1 and 4 are strictly smaller.

Loading coding console...

Show the approach

Approach

Count the allowed base-4 digit strings smaller than the bound by scanning its digits from most significant to least significant. For counting only, pad shorter values with leading zeros to the bound's length; this gives each value exactly one fixed-length representation. Keep the current power of four, and the number of allowed suffixes below that position. With k remaining positions, the suffix count is 2^k because each position can contain zero or one.

Maintain that the scanned prefix is still equal to the bound and that smaller counts all allowed strings whose first smaller position has already been chosen. If the next bound digit is zero, the only allowed equal choice is zero. If it is one, choosing zero makes the number smaller and contributes every allowed suffix; then continue along the equal choice one. If it is two or three, both allowed choices are smaller, so add twice the suffix count and stop. No allowed prefix can remain equal after that digit.

Every smaller fixed-length string has a unique first position where it differs from the bound, and it is counted exactly in that position's branch. A completely equal string is never added, so the comparison is strict even when n itself is fancy. This count includes the all-zero string exactly once; n is at least one, so subtract one to exclude zero. Leading-zero padding is only a counting device and never duplicates a value.

Find the highest power of four using integer division, then reduce the place by four and the suffix count by two at each step. This takes O(log n) time and O(1) auxiliary space. Java and C++ use 64-bit integers for n and all arithmetic. In JavaScript the input is at most 10^15, below 2^53; powers of four, remainders and all counts remain exact, with no bitwise conversion to 32 bits. No logarithm approximation or enumeration of the qualifying values is required.

Time complexity:
O(log n), scanning at most the base-4 digit count of n.
Space complexity:
O(1) auxiliary space.