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

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

You are given an integer k and an integer x.

The price of a number num is calculated by counting the number of set bits at positions x, 2x, 3x, etc., in its binary representation (starting from the least significant bit at position 1).

For example:

If x = 1 and num = 13 (binary: 1101), we check positions 1, 2, 3, 4, ... The set bits at positions 1, 3, 4 give us a price of 3.
If x = 2 and num = 13 (binary: 1101), we check positions 2, 4, 6, ... The set bits at positions 2, 4 give us a price of 2.

The accumulated price of num is the total price of all numbers from 1 to num.

A number num is considered cheap if its accumulated price is less than or equal to k.

Return the greatest cheap number.

Input & Output

Example 1 — Basic Case

$ Input: k = 9, x = 1

› Output: 6

💡 Note: For x=1, we count all set bits. Numbers 1-6 have accumulated price: 1+1+2+1+2+2=9 ≤ k. Number 7 would make it 9+3=12 > k.

Example 2 — Different x

$ Input: k = 7, x = 2

› Output: 9

💡 Note: For x=2, we count bits at positions 2,4,6,... Numbers 1-9 have lower accumulated price since fewer positions are counted.

Example 3 — Small Budget

$ Input: k = 1, x = 1

› Output: 1

💡 Note: Only number 1 (binary: 1) has price 1, accumulated price = 1 ≤ k. Number 2 would exceed budget.

Constraints

1 ≤ k ≤ 10¹⁵
1 ≤ x ≤ 8

Visualization

Tap to expand

Understanding the Visualization

Input

Budget k=9, check positions x=1 (every bit)

Process

Calculate accumulated price for numbers 1,2,3,4,5,6...

Output

Maximum number 6 where accumulated price ≤ k

Key Takeaway

🎯 Key Insight: Binary search the answer space and use digit DP to efficiently calculate accumulated prices

Asked in

G Google 15 f Meta 8

The key insight is to use binary search on the answer space combined with digit DP for efficient price calculation. We search for the maximum number whose accumulated price (sum of prices from 1 to that number) is ≤ k. Best approach is binary search + digit DP with Time: O(log n × d²), Space: O(d²).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(log n × d²)	O(d²)	Binary search the answer space and use digit DP to calculate accumulated price
Brute Force	O(n × log n)	O(1)	Calculate accumulated price for each number until exceeding k

Binary Search on Answer — Algorithm Steps

Binary search on the answer range [1, large_number]
For each candidate, use digit DP to calculate accumulated price
If accumulated price ≤ k, search right; otherwise search left
Return the maximum valid answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set search range [1, 10^15]

Binary Search

Test middle value using digit DP for price calculation

Converge

Narrow range until finding maximum valid number

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int k, int x) {
    // Simplified approach for C - using brute force with optimizations
    long long accumulated = 0;
    long long num = 0;
    
    while (1) {
        num++;
        int price = 0;
        long long temp = num;
        int pos = 1;
        
        while (temp > 0) {
            if ((temp & 1) && (pos % x == 0)) {
                price++;
            }
            temp >>= 1;
            pos++;
        }
        
        if (accumulated + price > k) {
            return num - 1;
        }
        accumulated += price;
        
        // Safety check for very large numbers
        if (num > 1000000) break;
    }
    
    return num - 1;
}

int main() {
    int k, x;
    scanf("%d", &k);
    scanf("%d", &x);
    printf("%lld\n", solution(k, x));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n × d²)

Binary search log n iterations, each with digit DP taking O(d²) where d is number of digits

⚡ Linearithmic

Space Complexity

O(d²)

DP memoization table for digit DP with O(d²) states

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler