Scale Engineer

Maximum Number That Sum of the Prices Is Less Than or Equal to K

Med
#2675Time: O(S * log(S) * log(S)), where S is the size of the search space. This is too slow.Space: O(1)
Patterns
Dynamic ProgrammingBit Manipulation
Algorithms
Binary Search

Prompt

You are given an integer k and an integer x. The price of a number num is calculated by the count of set bits at positions x, 2x, 3x, etc., in its binary representation, starting from the least significant bit. The following table contains examples of how price is calculated.

x num Binary Representation Price
1 13 000001101 3
2 13 000001101 1
2 233 011101001 3
3 13 000001101 1
3 362 101101010 2

The accumulated price of num is the total price of numbers from 1 to num. num is considered cheap if its accumulated price is less than or equal to k.

Return the greatest cheap number.

 

Example 1:

Input: k = 9, x = 1

Output: 6

Explanation:

As shown in the table below, 6 is the greatest cheap number.

x num Binary Representation Price Accumulated Price
1 1 001 1 1
1 2 010 1 2
1 3 011 2 4
1 4 100 1 5
1 5 101 2 7
1 6 110 2 9
1 7 111 3 12

Example 2:

Input: k = 7, x = 2

Output: 9

Explanation:

As shown in the table below, 9 is the greatest cheap number.

x num Binary Representation Price Accumulated Price
2 1 0001 0 0
2 2 0010 1 1
2 3 0011 1 2
2 4 0100 0 2
2 5 0101 0 2
2 6 0110 1 3
2 7 0111 1 4
2 8 1000 1 5
2 9 1001 1 6
2 10 1010 2 8

 

Constraints:

  • 1 <= k <= 1015
  • 1 <= x <= 8

Approaches

3 approaches with complexity analysis and trade-offs.

The problem asks for the "greatest" cheap number. The function accumulated_price(num) is monotonically increasing with num. This allows us to use binary search on the answer num. For each mid value in our binary search, we check if accumulated_price(mid) <= k.

Algorithm

    1. Define a search range for the answer, low = 1, high = 2 * 10^16 (a safe upper bound). Initialize ans = 0.
    1. While low <= high:
    • a. Calculate mid = low + (high - low) / 2.
    • b. Call a helper function isCheap(mid, k, x) to check if mid is a cheap number.
    • c. If isCheap returns true:
      • i. mid is a potential answer. Store it: ans = mid.
      • ii. Try for a larger number: low = mid + 1.
    • d. If isCheap returns false:
      • i. mid is too large. Search in the lower half: high = mid - 1.
    1. Return ans.
  • isCheap(num, k, x) function:
    • a. Initialize totalPrice = 0.
    • b. Loop i from 1 to num.
    • c. For each i, calculate its price by checking bits at positions x, 2x, ....
    • d. Add the price of i to totalPrice.
    • e. If at any point totalPrice > k, return false immediately.
    • f. If the loop completes, return true.

Walkthrough

We can binary search for the answer num in a large range, for example, from 1 to 2 * 10^16. For each mid value, we need to check if it's a "cheap" number. In this approach, we calculate accumulated_price(mid) by iterating from i = 1 to mid, calculating the price of each i, and summing them up. If accumulated_price(mid) <= k, it means mid could be our answer, and we search in the right half (low = mid + 1). Otherwise, mid is too large, so we search in the left half (high = mid - 1). While this approach correctly uses binary search, the check function itself is too slow.

class Solution {    private long getPrice(long num, int x) {        long price = 0;        for (int i = x; i <= 63; i += x) {            if ((num & (1L << (i - 1))) != 0) {                price++;            }        }        return price;    }     private boolean isCheap(long num, long k, int x) {        long accumulatedPrice = 0;        for (long i = 1; i <= num; i++) {            accumulatedPrice += getPrice(i, x);            if (accumulatedPrice > k) {                return false;            }        }        return true;    }     public long findMaximumNumber(long k, int x) {        long low = 1, high = 20000000000000000L; // A sufficiently large upper bound        long ans = 0;        while (low <= high) {            long mid = low + (high - low) / 2;            if (mid == 0) {                 low = 1;                continue;            }            if (isCheap(mid, k, x)) {                ans = mid;                low = mid + 1;            } else {                high = mid - 1;            }        }        return ans;    }}

Complexity

Time

O(S * log(S) * log(S)), where S is the size of the search space. This is too slow.

Space

O(1)

Trade-offs

Pros

  • Correctly identifies the monotonic property of the problem, leading to a binary search structure.

Cons

  • The check function is very slow. The complexity of isCheap(num, ...) is O(num * log(num)), making the overall approach time-out.

Solutions

class Solution { private int x ; private long num ; private Long [][] f ; public long findMaximumNumber ( long k , int x ) { this . x = x ; long l = 1 , r = ( long ) 1 e17 ; while ( l < r ) { long mid = ( l + r + 1 ) >>> 1 ; num = mid ; f = new Long [ 65 ][ 65 ]; int pos = 64 - Long . numberOfLeadingZeros ( mid ); if ( dfs ( pos , 0 , true ) <= k ) { l = mid ; } else { r = mid - 1 ; } } return l ; } private long dfs ( int pos , int cnt , boolean limit ) { if ( pos == 0 ) { return cnt ; } if (! limit && f [ pos ][ cnt ] != null ) { return f [ pos ][ cnt ]; } long ans = 0 ; int up = limit ? ( int ) ( num >> ( pos - 1 ) & 1 ) : 1 ; for ( int i = 0 ; i <= up ; ++ i ) { ans += dfs ( pos - 1 , cnt + ( i == 1 && pos % x == 0 ? 1 : 0 ), limit && i == up ); } if (! limit ) { f [ pos ][ cnt ] = ans ; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem