1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
// 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K
#include "leetcode.h"
/*
* you are given an integer 'k' and an integer 'x'. the price of a number is
* calculated by the count of set its at positions 'x, 2x, 3x, etc.', in its
* binary representation, starting from the least significant bit. the following
* tale 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
*/
long long check(long long n, long long x) {
long long res = 0, div, sz = 1 + log2(n);
for (long long i = 0; i < sz; i++) {
if (((i + 1) % x)) // ensure 'i + 1' is divisible by 'x'
continue;
long long pow2i = 1LL << i; // calculate 2^i
if (!i)
res += (n + 1) >> 1; // special case when i is 0, which is the msb
else {
div = n >> i; // calculate n / 2^i
if (!div)
continue;
res += (div >> 1) * pow2i; // add contribution based on 'div' and 'pow2i'
if (div & 1)
res += (n % pow2i) + 1; // add remainder contribution if 'div' is odd
}
}
return res;
}
long long findMaximumNumber(long long k, int x) {
long long ans = 0, low = 1, high = 1e16, mid;
while (high - low >= 3) {
mid = (low + high) >> 1;
if (check(mid, x) <= k) {
ans = fmax(ans, mid);
low = mid + 1;
} else
high = mid - 1;
}
for (long long i = low; i <= high; i++)
if (check(i, x) <= k)
ans = fmax(ans, i);
else
break;
return ans;
}
int main() {
printf("%lld\n", findMaximumNumber(9, 1)); // expect: 6
printf("%lld\n", findMaximumNumber(7, 2)); // expect: 9
}
|