Maximum Number That Sum of the Prices Is Less Than or Equal to 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.

1class Solution {2    private long getPrice(long num, int x) {3        long price = 0;4        for (int i = x; i <= 63; i += x) {5            if ((num & (1L << (i - 1))) != 0) {6                price++;7            }8        }9        return price;10    }11 12    private boolean isCheap(long num, long k, int x) {13        long accumulatedPrice = 0;14        for (long i = 1; i <= num; i++) {15            accumulatedPrice += getPrice(i, x);16            if (accumulatedPrice > k) {17                return false;18            }19        }20        return true;21    }22 23    public long findMaximumNumber(long k, int x) {24        long low = 1, high = 20000000000000000L; // A sufficiently large upper bound25        long ans = 0;26        while (low <= high) {27            long mid = low + (high - low) / 2;28            if (mid == 0) { 29                low = 1;30                continue;31            }32            if (isCheap(mid, k, x)) {33                ans = mid;34                low = mid + 1;35            } else {36                high = mid - 1;37            }38        }39        return ans;40    }41}

• 1. Initialize accumulatedPrice = 0L and num = 0L.
• 2. Start a loop that increments num by 1 in each iteration.
• 3. Inside the loop, calculate priceOfNum:
  • a. Initialize priceOfNum = 0.
  • b. Iterate through bit positions pos = x, 2*x, 3*x, ... up to a reasonable limit (e.g., 63, for long).
  • c. Check if the pos-th bit of num is set using the bitwise AND operation (num & (1L << (pos - 1))) != 0.
  • d. If it is set, increment priceOfNum.
• 4. Check if adding priceOfNum to accumulatedPrice would exceed k. This is to prevent overflow and unnecessary calculations: if (accumulatedPrice > k - priceOfNum).
• 5. If it exceeds k, then num - 1 is the answer. Return num - 1.
• 6. Otherwise, update accumulatedPrice += priceOfNum.

We initialize accumulatedPrice to 0 and loop num from 1 upwards. In each step, we calculate the price of the current num. The price is the number of set bits at positions that are multiples of x (i.e., x, 2x, 3x, ...). We add this price to accumulatedPrice. If accumulatedPrice becomes greater than k, it means the current num makes the total price too high. Therefore, the previous number, num - 1, is the maximum cheap number. This method is too slow for the given constraints on k because the answer num can be very large, making the loop run too many times.

1class Solution {2    private long getPrice(long num, int x) {3        long price = 0;4        for (int i = x; i <= 63; i += x) {5            if ((num & (1L << (i - 1))) != 0) {6                price++;7            }8        }9        return price;10    }11 12    public long findMaximumNumber(long k, int x) {13        long accumulatedPrice = 0;14        long num = 0;15        while (true) {16            num++;17            long priceOfNum = getPrice(num, x);18            if (accumulatedPrice > k - priceOfNum) {19                return num - 1;20            }21            accumulatedPrice += priceOfNum;22        }23    }24}

• 1. The main structure is a binary search on the answer num in a range like [1, 2 * 10^16].
• 2. In each step of the binary search, for a given mid, we calculate accumulated_price(mid) using an efficient helper function.
• 3. getAccumulatedPrice(num, x) function:
  • a. Initialize totalPrice = 0.
  • b. Loop through bit positions pos = x, 2*x, 3*x, ... up to 63.
  • c. For each pos, calculate the number of integers from 1 to num that have the pos-th bit set.
    • i. The pattern of the pos-th bit has a full cycle length of period = 1L << pos.
    • ii. The number of full periods in num+1 numbers (from 0 to num) is num_periods = (num + 1) / period.
    • iii. Each full period contributes period / 2 set bits.
    • iv. The remaining numbers are remainder = (num + 1) % period.
    • v. The contribution from the remainder is max(0, remainder - (period / 2)).
    • vi. The total count for position pos is the sum of contributions from full periods and the remainder.
  • d. Add this count to totalPrice.
• 4. After the loop, return totalPrice.
• 5. Back in the binary search, if getAccumulatedPrice(mid, x) <= k, we search for a larger answer (ans = mid, low = mid + 1). Otherwise, we search for a smaller one (high = mid - 1).

The core idea is to change the order of summation for accumulated_price(num). Instead of sum over numbers (sum over bits), we do sum over bits (sum over numbers). The inner sum becomes counting how many numbers from 1 to num have a specific bit set. We can write an efficient helper function, countSetBitsAtPos(num, pos), to calculate this count. The bits at any position pos follow a periodic pattern: 2^(pos-1) zeros, then 2^(pos-1) ones, repeating. We can use this pattern to calculate the count in O(1) time using division and modulo operations. The accumulated_price(num) function then loops through the relevant bit positions (x, 2x, 3x, ...) and sums up the results from countSetBitsAtPos. This calculation is very fast, taking O(log(num)) time. With this efficient check, the binary search becomes feasible.

1class Solution {2    // Calculates the total price for all numbers from 1 to num.3    private long getAccumulatedPrice(long num, int x) {4        long totalPrice = 0;5        // Iterate through each bit position that contributes to the price.6        // Positions are 1-indexed.7        for (int pos = x; pos <= 63; pos += x) {8            // Calculate how many numbers from 1 to num have the pos-th bit set.9            long period = 1L << pos;10            long halfPeriod = period / 2;11 12            // Count numbers in the range [0, num], which is num + 1 numbers.13            long numAndZero = num + 1;14 15            // Number of full periods.16            long numPeriods = numAndZero / period;17            18            // Each full period has halfPeriod numbers with the pos-th bit set.19            long count = numPeriods * halfPeriod;20 21            // Count in the remaining part of the last, incomplete period.22            long remainder = numAndZero % period;23            count += Math.max(0L, remainder - halfPeriod);24            25            totalPrice += count;26        }27        return totalPrice;28    }29 30    public long findMaximumNumber(long k, int x) {31        long low = 1;32        long high = 20000000000000000L; // A safe upper bound33        long ans = 0;34 35        while (low <= high) {36            long mid = low + (high - low) / 2;37            if (mid == 0) {38                low = 1;39                continue;40            }41            42            long accumulatedPrice = getAccumulatedPrice(mid, x);43 44            if (accumulatedPrice <= k) {45                // mid is a potential answer, try for a larger one.46                ans = mid;47                low = mid + 1;48            } else {49                // mid is too large, search in the lower half.50                high = mid - 1;51            }52        }53        return ans;54    }55}