aboutsummaryrefslogtreecommitdiff
path: root/max_num_sum_leq_k.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_num_sum_leq_k.py')
-rw-r--r--max_num_sum_leq_k.py46
1 files changed, 46 insertions, 0 deletions
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))