3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K LeetCode Solution
In this guide, you will get 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K LeetCode Solution with the best time and space complexity. The solution to Maximum Number That Sum of the Prices Is Less Than or Equal to K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number That Sum of the Prices Is Less Than or Equal to K
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.
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
Complexity Analysis
Time Complexity: O(\log 10^5)
Space Complexity: O(1)
3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K LeetCode Solution in C++
class Solution {
public:
long long findMaximumNumber(long long k, int x) {
long l = 1;
long r = 1e15;
while (l < r) {
const long m = (l + r + 1) / 2;
if (getSumPrices(m, x) <= k)
l = m;
else
r = m - 1;
}
return l;
}
private:
// Returns the sum of prices of all numbers from 1 to `num`.
long getSumPrices(long num, int x) {
long sumPrices = 0;
// Increment `num` to account the 0-th row in the count of groups.
++num;
for (int i = leftmostColumnIndex(num); i > 0; --i)
// If the current column is valid, count the number of 1s in this column.
if (i % x == 0) {
const long groupSize = 1L << i;
const long halfGroupSize = 1L << i - 1;
sumPrices += num / groupSize * halfGroupSize;
sumPrices += max(0L, (num % groupSize) - halfGroupSize);
}
return sumPrices;
}
// Returns the leftmost column index in 1-indexed.
int leftmostColumnIndex(long num) {
return 63 - __builtin_clzl(num) + 1;
}
}; /* code provided by PROGIEZ */
3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K LeetCode Solution in Java
class Solution {
public long findMaximumNumber(long k, int x) {
long l = 1;
long r = 1000000000000000L;
while (l < r) {
final long m = (l + r + 1) / 2;
if (getSumPrices(m, x) > k)
r = m - 1;
else
l = m;
}
return l;
}
// Returns the sum of prices of all numbers from 1 to `num`.
private long getSumPrices(long num, int x) {
long sumPrices = 0;
num++; // Increment `num` to account the 0-th row in the count of groups.
for (int i = leftmostColumnIndex(num); i > 0; --i)
if (i % x == 0) {
final long groupSize = 1L << i;
final long halfGroupSize = 1L << i - 1;
sumPrices += num / groupSize * halfGroupSize;
sumPrices += Math.max(0L, (num % groupSize) - halfGroupSize);
}
return sumPrices;
}
// Returns the leftmost column index in 1-indexed.
private int leftmostColumnIndex(long num) {
return 63 - Long.numberOfLeadingZeros(num) + 1;
}
} // code provided by PROGIEZ
3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K LeetCode Solution in Python
class Solution:
def findMaximumNumber(self, k: int, x: int) -> int:
def getSumPrices(num: int) -> int:
"""Returns the sum of prices of all numbers from 1 to `num`."""
sumPrices = 0
# Increment `num` to account the 0-th row in the count of groups.
num += 1
for i in range(num.bit_length(), 0, -1):
if i % x == 0:
groupSize = 1 << i
halfGroupSize = 1 << i - 1
sumPrices += num // groupSize * halfGroupSize
sumPrices += max(0, (num % groupSize) - halfGroupSize)
return sumPrices
l = 1
r = 10**15
return bisect.bisect_right(range(l, r + 1), k, key=getSumPrices) - 1 + l # code by PROGIEZ
