LeetCode 3007: Maximum Number That Sum of the Prices Is Less Than or Equal to K Solution

Master LeetCode problem 3007 (Maximum Number That Sum of the Prices Is Less Than or Equal to K), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Medium

Binary Search Dynamic Programming Bit Manipulation

Problem Explanation

Explanation

To solve this problem, we need to find the greatest number whose accumulated price (total price from 1 to that number) is less than or equal to k, where the price of a number is calculated based on the count of set bits at positions x, 2x, 3x, etc., in its binary representation.

We can use binary search to find the greatest cheap number. The key observation is that the accumulated price is a non-decreasing function of num. We can perform a binary search on the possible values of num to find the greatest number within the given constraints.

Initially, we set our search range to be from 1 to k because the accumulated price of a number n is at most log2(n).
In each iteration of the binary search, we calculate the accumulated price for the mid number and update our search range accordingly.
We continue this process until we find the greatest cheap number within the constraints.

The time complexity of this approach is O(log N) where N is the search space (k in this case), and the space complexity is O(1).

Solution Code

class Solution {
    public int findGreatestNumber(int k, int x) {
        long left = 1;
        long right = k;
        
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (calculateAccumulatedPrice(mid, x) <= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return (int)left;
    }
    
    private long calculateAccumulatedPrice(long num, int x) {
        long price = 0;
        long factor = 1;
        
        while (num > 0) {
            long count = num / 2;
            long remainder = num % 2;
            price += count * factor;
            if (remainder > 0) {
                price += Math.min(remainder, 1L << x);
            }
            num /= 2;
            factor *= 2;
            x++;
        }
        
        return price;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3007 (Maximum Number That Sum of the Prices Is Less Than or Equal to K)?

This page provides optimized solutions for LeetCode problem 3007 (Maximum Number That Sum of the Prices Is Less Than or Equal to K) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3007 (Maximum Number That Sum of the Prices Is Less Than or Equal to K)?

The time complexity for LeetCode 3007 (Maximum Number That Sum of the Prices Is Less Than or Equal to K) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3007 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3007 in Java, C++, or Python.

Back to LeetCode Solutions