Maximum Number That Sum of the Prices Is Less Than or Equal to K solution and explanation
Google
9 more videos on this problem
Maximum Number That Sum of the Prices Is Less Than or Equal to K |Brute Force |Optimal |Contest 380codestorywithMIK · 1:06:24 · 7K views
3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K | Bit Manipulation TrickAryan Mittal · 43:13 · 3K views
3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K | Weekly Leetcode 380codingMohan · 36:11 · 1K views
3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K (Leetcode Medium)Programming Live with Larry · 29:02 · 793 views
【每日一题】LeetCode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to KHuifeng Guan · 27:40 · 434 views
3007 Maximum Number That Sum of the Prices Is Less Than or Equal to K | LeetCode Weekly-380 ContestABCodeST · 17:52 · 294 views
3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K | Leetcode Contest| Optimal🔥CodeVichar · 8:22 · 276 views
Maximum Number That Sum of the Prices Is Less Than or Equal to KRohit Satpute · 9:17 · 202 views
Leetcode 3007: Maximum Number That Sum of the Prices Is Less Than or Equal to KAlgorithms Casts · 28:25 · 194 views
Maximum Number That Sum of the Prices Is Less Than or Equal to K (Leetcode Weekly 380)Soumya Bhattacharjee · 12:52 · 150 views
The problem
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 <= 10151 <= x <= 8
Approach overview
Problem Overview: Given integers k and x, every number has a price defined by how many set bits appear at bit positions that are multiples of x. The task is to find the maximum integer n such that the total price of all numbers from 1 to n is less than or equal to k.
Approach 1: Brute Force Search (O(n log n) time, O(1) space)
Iterate from 1 upward and compute the price of every number individually. For each integer, check its binary representation and count set bits only at positions where position % x == 0. Accumulate the total price and stop once the sum exceeds k. This approach directly follows the definition of the problem and is easy to implement using basic bit manipulation. The downside is performance: computing the price for every number requires scanning its bits, which makes the solution too slow when n becomes large.
Approach 2: Binary Search with Digit DP (O(log n * bits) time, O(bits) space)
The key observation: instead of evaluating each number individually, compute how many valid bits appear in the range [1, n]. Once you can quickly calculate the total price up to any n, the problem becomes finding the largest n whose total price is ≤ k. That turns the task into a classic binary search problem.
During the check step, count how many numbers in [1, n] have a set bit at each position that is a multiple of x. This can be computed using a bit counting pattern or a small dynamic programming style digit DP over the binary representation of n. For each valid bit position, determine how many numbers contribute a set bit there and add that to the total price.
Binary search runs over the possible answer range (typically up to 10^15 or higher depending on constraints). Each midpoint check computes the cumulative price using the bit counting logic. Because the number of bits in an integer is small (around 60 for 64‑bit numbers), the counting step is fast, making the overall complexity roughly O(log n * 60).
Recommended for interviews: The expected solution uses binary search combined with bit counting or digit DP. Interviewers want to see that you convert the problem into a monotonic search condition and efficiently compute the prefix price. Starting with the brute force explanation demonstrates understanding of the price definition, while the optimized binary search approach shows strong algorithmic reasoning.
Approach 1: Brute Force Search
This approach involves checking each number incrementally to determine the accumulated price. For each number, compute its price by counting set bits at positions x, 2x, 3x, etc. Keep a running total of the accumulated price and find the largest number where this total is less than or equal to k.
def calculate_price(num, x):
price = 0
position = x
while num > 0:
if num & (1 << (position - 1)):
price += 1
num >>= 1
position += x
return price
def find_greatest_cheap_number(k, x):
accumulated_price = 0
num = 0
while True:
price = calculate_price(num + 1, x)
if accumulated_price + price > k:
break
accumulated_price += price
num += 1
return num
print(find_greatest_cheap_number(9, 1)) # Output: 6
print(find_greatest_cheap_number(7, 2)) # Output: 9public class CheapNumber {
public static int calculatePrice(int num, int x) {
int price = 0;
int position = x;
while (num > 0) {
if ((num & (1 << (position - 1))) != 0)
price++;
position += x;
}
return price;
}
public static int findGreatestCheapNumber(int k, int x) {
int accumulatedPrice = 0;
int num = 0;
while (true) {
int price = calculatePrice(num + 1, x);
if (accumulatedPrice + price > k)
break;
accumulatedPrice += price;
num++;
}
return num;
}
public static void main(String[] args) {
System.out.println(findGreatestCheapNumber(9, 1)); // Output: 6
System.out.println(findGreatestCheapNumber(7, 2)); // Output: 9
}
}#include <iostream>
int calculate_price(int num, int x) {
int price = 0;
int position = x;
while (num) {
if (num & (1 << (position - 1)))
price++;
position += x;
}
return price;
}
int find_greatest_cheap_number(int k, int x) {
int accumulated_price = 0;
int num = 0;
while (true) {
int price = calculate_price(num + 1, x);
if (accumulated_price + price > k)
break;
accumulated_price += price;
num++;
}
return num;
}
int main() {
std::cout << find_greatest_cheap_number(9, 1) << std::endl; // Output: 6
std::cout << find_greatest_cheap_number(7, 2) << std::endl; // Output: 9
return 0;
}function calculatePrice(num, x) {
let price = 0;
let position = x;
while (num > 0) {
if (num & (1 << (position - 1))) {
price++;
}
num >>= 1;
position += x;
}
return price;
}
function findGreatestCheapNumber(k, x) {
let accumulatedPrice = 0;
let num = 0;
while (true) {
let price = calculatePrice(num + 1, x);
if (accumulatedPrice + price > k) {
break;
}
accumulatedPrice += price;
num++;
}
return num;
}
console.log(findGreatestCheapNumber(9, 1)); // Output: 6
console.log(findGreatestCheapNumber(7, 2)); // Output: 9;#include <stdio.h>
int calculate_price(int num, int x) {
int price = 0;
int position = x;
while (num) {
if (num & (1 << (position - 1)))
price++;
position += x;
}
return price;
}
int find_greatest_cheap_number(int k, int x) {
int accumulated_price = 0;
int num = 0;
while (1) {
int price = calculate_price(num + 1, x);
if (accumulated_price + price > k)
break;
accumulated_price += price;
num++;
}
return num;
}
int main() {
printf("%d\n", find_greatest_cheap_number(9, 1)); // Output: 6
printf("%d\n", find_greatest_cheap_number(7, 2)); // Output: 9
return 0;
}using System;
class Program {
static int CalculatePrice(int num, int x) {
int price = 0;
int position = x;
while (num > 0) {
if ((num & (1 << (position - 1))) != 0) {
price++;
}
position += x;
}
return price;
}
static int FindGreatestCheapNumber(int k, int x) {
int accumulatedPrice = 0;
int num = 0;
while (true) {
int price = CalculatePrice(num + 1, x);
if (accumulatedPrice + price > k) {
break;
}
accumulatedPrice += price;
num++;
}
return num;
}
static void Main() {
Console.WriteLine(FindGreatestCheapNumber(9, 1)); // Output: 6
Console.WriteLine(FindGreatestCheapNumber(7, 2)); // Output: 9
}
}- Uses a bit manipulation technique to calculate the price of each number incrementally.
- Loops until the accumulated price exceeds
k.
Time Complexity: O(N * log(N)).
Space Complexity: O(1).
Approach 2: Dynamic Programming Search
This approach involves using dynamic programming and caching to store precomputed results for price calculation, thereby reducing redundant computations. This method is particularly helpful when re-computing the price of numbers multiple times, allowing a speed-up by avoiding recalculations.
def calculate_price(num, x, dp):
if num == 0: return 0
if num in dp: return dp[num]
price = 0
if num & 1:
price += 1
num >>= 1
step = x - 1
while num > 0:
if num & 1:
price += 1
num >>= 1
step -= 1
if step == 0:
step = x - 1
dp[num] = price
return price
def find_greatest_cheap_number(k, x):
dp = {}
accumulated_price = 0
num = 0
while True:
price = calculate_price(num + 1, x, dp)
if accumulated_price + price > k:
break
accumulated_price += price
num += 1
return num
print(find_greatest_cheap_number(9, 1)) # Output: 6
print(find_greatest_cheap_number(7, 2)) # Output: 9import java.util.HashMap;
public class CheapNumberDP {
private static HashMap<Integer, Integer> dp = new HashMap<>();
private static int calculatePrice(int num, int x) {
if (num == 0) return 0;
if (dp.containsKey(num)) return dp.get(num);
int price = 0;
if ((num & 1) != 0)
price++;
num >>= 1;
int step = x - 1;
while (num > 0) {
if ((num & 1) != 0)
price++;
num >>= 1;
if (--step == 0) step = x - 1;
}
dp.put(num, price);
return price;
}
public static int findGreatestCheapNumber(int k, int x) {
int accumulatedPrice = 0;
int num = 0;
while (true) {
int price = calculatePrice(num + 1, x);
if (accumulatedPrice + price > k)
break;
accumulatedPrice += price;
num++;
}
return num;
}
public static void main(String[] args) {
System.out.println(findGreatestCheapNumber(9, 1)); // Output: 6
System.out.println(findGreatestCheapNumber(7, 2)); // Output: 9
}
}#include <iostream>
#include <vector>
#include <cstring>
std::vector<int> dp(100001, -1);
int calculate_price(int num, int x) {
if (num == 0) return 0;
if (dp[num] != -1) return dp[num];
int price = 0;
if (num & 1)
price += 1;
num >>= 1;
int step = x - 1;
while (num > 0) {
if (num & 1)
price += 1;
num >>= 1;
if (--step == 0) step = x - 1;
}
return dp[num] = price;
}
int find_greatest_cheap_number(int k, int x) {
int accumulated_price = 0;
int num = 0;
while (true) {
int price = calculate_price(num + 1, x);
if (accumulated_price + price > k)
break;
accumulated_price += price;
num++;
}
return num;
}
int main() {
std::cout << find_greatest_cheap_number(9, 1) << std::endl; // Output: 6
std::cout << find_greatest_cheap_number(7, 2) << std::endl; // Output: 9
return 0;
}function calculatePrice(num, x, dp) {
if (num === 0) return 0;
if (num in dp) return dp[num];
let price = 0;
if (num & 1) {
price++;
}
num >>= 1;
let step = x - 1;
while (num > 0) {
if (num & 1) {
price++;
}
num >>= 1;
step--;
if (step === 0) step = x - 1;
}
dp[num] = price;
return price;
}
function findGreatestCheapNumber(k, x) {
const dp = {};
let accumulatedPrice = 0;
let num = 0;
while (true) {
const price = calculatePrice(num + 1, x, dp);
if (accumulatedPrice + price > k) {
break;
}
accumulatedPrice += price;
num++;
}
return num;
}
console.log(findGreatestCheapNumber(9, 1)); // Output: 6
console.log(findGreatestCheapNumber(7, 2)); // Output: 9;#include <stdio.h>
#include <string.h>
int dp[100001];
int calculate_price(int num, int x) {
if (num == 0) return 0;
if (dp[num] != -1) return dp[num];
int price = 0;
if (num & 1)
price += 1;
num >>= 1;
int step = x - 1;
while (num > 0) {
if (num & 1)
price += 1;
num >>= 1;
if (--step == 0) step = x - 1;
}
return dp[num] = price;
}
int find_greatest_cheap_number(int k, int x) {
memset(dp, -1, sizeof(dp));
int accumulated_price = 0;
int num = 0;
while (1) {
int price = calculate_price(num + 1, x);
if (accumulated_price + price > k)
break;
accumulated_price += price;
num++;
}
return num;
}
int main() {
printf("%d\n", find_greatest_cheap_number(9, 1)); // Output: 6
printf("%d\n", find_greatest_cheap_number(7, 2)); // Output: 9
return 0;
}using System;
using System.Collections.Generic;
class Program {
static Dictionary<int, int> dp = new Dictionary<int, int>();
static int CalculatePrice(int num, int x) {
if (num == 0) return 0;
if (dp.ContainsKey(num)) return dp[num];
int price = 0;
if ((num & 1) != 0) {
price++;
}
num >>= 1;
int step = x - 1;
while (num > 0) {
if ((num & 1) != 0) {
price++;
}
num >>= 1;
step--;
if (step == 0) step = x - 1;
}
dp[num] = price;
return price;
}
static int FindGreatestCheapNumber(int k, int x) {
int accumulatedPrice = 0;
int num = 0;
while (true) {
int price = CalculatePrice(num + 1, x);
if (accumulatedPrice + price > k) {
break;
}
accumulatedPrice += price;
num++;
}
return num;
}
static void Main() {
Console.WriteLine(FindGreatestCheapNumber(9, 1)); // Output: 6
Console.WriteLine(FindGreatestCheapNumber(7, 2)); // Output: 9
}
}- Dynamic programming strategy with memoization using a dictionary to store and retrieve prices quickly.
Time Complexity: O(N * log(N)), memoization reduces redundant calculations.
Space Complexity: O(N).
Approach 3: Binary Search + Digit DP
We notice that if num increases, the total value from 1 to num also increases. Therefore, we can use a binary search method to find the largest cheap number.
We define the left boundary of the binary search as l = 1. Since there is at least one valuable number in every 2^x + 1 numbers, and the total value does not exceed 10^{15}, we can set the right boundary of the binary search as r = 10^{18}.
Next, we perform a binary search. For each mid, we use the digit DP method to calculate the total value from 1 to mid. If the total value does not exceed k, it means mid is a cheap number, and we update the left boundary l to mid. Otherwise, we update the right boundary r to mid - 1.
Finally, we return the left boundary l.
The time complexity is O(log^2 k), and the space complexity is O(log k).
function findMaximumNumber(k: number, x: number): number {
let [l, r] = [1n, 10n ** 17n];
let num: bigint;
const f: bigint[][] = Array.from({ length: 65 }, () => Array(65).fill(-1n));
const dfs = (pos: number, cnt: number, limit: boolean): bigint => {
if (pos === 0) {
return BigInt(cnt);
}
if (!limit && f[pos][cnt] !== -1n) {
return f[pos][cnt];
}
let ans: bigint = 0n;
let up: number = 1;
if (limit) {
up = Number((num >> BigInt(pos - 1)) & 1n);
}
for (let i = 0; i <= up; i++) {
let v: number = cnt;
if (i === 1 && pos % x === 0) {
v++;
}
ans += dfs(pos - 1, v, limit && i === up);
}
if (!limit) {
f[pos][cnt] = ans;
}
return ans;
};
while (l < r) {
let mid: bigint = (l + r + 1n) >> 1n;
num = mid;
let m: number = num.toString(2).length;
for (let i = 0; i < f.length; i++) {
f[i].fill(-1n);
}
if (dfs(m, 0, true) <= BigInt(k)) {
l = mid;
} else {
r = mid - 1n;
}
}
return Number(l);
}func findMaximumNumber(k int64, x int) int64 {
var l, r int64 = 1, 1e17
var num int64
var f [65][65]int64
var dfs func(pos, cnt int, limit bool) int64
dfs = func(pos, cnt int, limit bool) int64 {
if pos == 0 {
return int64(cnt)
}
if !limit && f[pos][cnt] != -1 {
return f[pos][cnt]
}
var ans int64
up := 1
if limit {
up = int(num >> (pos - 1) & 1)
}
for i := 0; i <= up; i++ {
v := cnt
if i == 1 && pos%x == 0 {
v++
}
ans += dfs(pos-1, v, limit && i == up)
}
if !limit {
f[pos][cnt] = ans
}
return ans
}
for l < r {
mid := (l + r + 1) >> 1
num = mid
m := bits.Len(uint(num))
for i := range f {
for j := range f[i] {
f[i][j] = -1
}
}
if dfs(m, 0, true) <= k {
l = mid
} else {
r = mid - 1
}
}
return l
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Search | Time Complexity: O(N * log(N)). |
| Dynamic Programming Search | Time Complexity: O(N * log(N)), memoization reduces redundant calculations. |
| Binary Search + Digit DP | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Search | O(n log n) | O(1) | Useful for understanding the price definition or when constraints are very small |
| Binary Search + Bit Counting / Digit DP | O(log n * bits) | O(bits) | Best choice for large inputs; efficiently finds the maximum valid number using monotonic search |
Frequently asked questions
Is Maximum Number That Sum of the Prices Is Less Than or Equal to K easy or hard?
The problem is typically classified as Medium. The difficulty comes from recognizing that brute force enumeration is infeasible and that the prefix price function is monotonic, allowing a binary search combined with bit counting or digit DP.
Maximum Number That Sum of the Prices Is Less Than or Equal to K Python/Java solution
Most implementations follow the same pattern: binary search for the maximum n and a helper function that calculates the total price up to n using bit counting. This logic translates cleanly to Python, Java, C++, C#, and JavaScript because it only uses integer arithmetic and bit operations.
How to solve Maximum Number That Sum of the Prices Is Less Than or Equal to K in O(log n)?
Use binary search over the possible answer range and compute the total price for each midpoint. The price calculation counts how many numbers contribute a set bit at positions divisible by x using bit patterns or digit DP. Since each check only processes about 60 bits, the total runtime becomes O(log n).
What is the best approach for Maximum Number That Sum of the Prices Is Less Than or Equal to K?
The optimal approach uses binary search on the answer combined with bit counting (digit DP). For a candidate number n, compute the total price contributed by all numbers from 1 to n by counting set bits at positions that are multiples of x. Because the price sum grows monotonically with n, binary search efficiently finds the largest valid value.
Is Maximum Number That Sum of the Prices Is Less Than or Equal to K asked at Google/Amazon/Meta?
Problems combining binary search with bit manipulation and prefix counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often require computing contributions of bits across ranges or applying digit DP with a monotonic condition.
What data structure is used in Maximum Number That Sum of the Prices Is Less Than or Equal to K?
The solution mainly relies on binary search and bit manipulation. Some implementations use a digit dynamic programming approach over the binary representation of numbers to count contributions efficiently.
What is the time complexity of Maximum Number That Sum of the Prices Is Less Than or Equal to K?
The optimized solution runs in O(log n * bits), where bits is the number of bits in the integer representation (around 60 for 64-bit numbers). Each binary search step evaluates a prefix price calculation using bit counting, which scans valid bit positions.