aboutsummaryrefslogtreecommitdiff
path: root/max_num_sum_leq_k.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-19 13:27:29 -0600
committerJack Sangdahl <[email protected]>2024-08-19 13:27:29 -0600
commit7d3f1413e30f3782ab73829efb38dabd28041a28 (patch)
tree764300f80afb967e332d19fc3b6cabfe1cfed2f3 /max_num_sum_leq_k.c
parent1d40fa67f4c59b46b14637f2b339f48f69c57df4 (diff)
downloadleetcode-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.c62
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
+}