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 | |
parent | 1d40fa67f4c59b46b14637f2b339f48f69c57df4 (diff) | |
download | leetcode-7d3f1413e30f3782ab73829efb38dabd28041a28.tar.gz leetcode-7d3f1413e30f3782ab73829efb38dabd28041a28.zip |
3007. maximum number that sum of the prices <= to k
-rw-r--r-- | max_num_sum_leq_k.c | 62 | ||||
-rw-r--r-- | max_num_sum_leq_k.py | 46 |
2 files changed, 108 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 +} diff --git a/max_num_sum_leq_k.py b/max_num_sum_leq_k.py new file mode 100644 index 0000000..10d6021 --- /dev/null +++ b/max_num_sum_leq_k.py @@ -0,0 +1,46 @@ +# 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K +from bisect import bisect_right + +""" +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 +""" + + +class Solution(object): + def __init__(self): + self.x = None + + def price(self, num): + res = 0 + for i in range(self.x - 1, 64, self.x): + check = num % (1 << (i + 1)) + res += ((num - check) >> 1) + max(check - (1 << i), 0) + return res + + def findMaximumNumber(self, k, x): + """ + :type k: int + :type x: int + :rtype: int + """ + self.x = x + return bisect_right(range((1 << 63) - 1), k, key=self.price) - 2 + + +if __name__ == "__main__": + obj = Solution() + print(obj.findMaximumNumber(9, 1)) + print(obj.findMaximumNumber(7, 2)) |