diff options
author | Jack Sangdahl <[email protected]> | 2024-08-19 13:27:29 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-19 13:27:29 -0600 |
commit | 7d3f1413e30f3782ab73829efb38dabd28041a28 (patch) | |
tree | 764300f80afb967e332d19fc3b6cabfe1cfed2f3 /max_num_sum_leq_k.c | |
parent | 1d40fa67f4c59b46b14637f2b339f48f69c57df4 (diff) | |
download | leetcode-7d3f1413e30f3782ab73829efb38dabd28041a28.tar.gz leetcode-7d3f1413e30f3782ab73829efb38dabd28041a28.zip |
3007. maximum number that sum of the prices <= to k
Diffstat (limited to 'max_num_sum_leq_k.c')
-rw-r--r-- | max_num_sum_leq_k.c | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/max_num_sum_leq_k.c b/max_num_sum_leq_k.c new file mode 100644 index 0000000..b97d21f --- /dev/null +++ b/max_num_sum_leq_k.c @@ -0,0 +1,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 +} |