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

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.

• 1. Define a search range for the answer, low = 1, high = 2 * 10^16 (a safe upper bound). Initialize ans = 0.
• 2. 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.
• 3. 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.

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;
    }
}