initial
i couldnt solve this
Let’s say we have 13 bottles and we wanna make it less or equal to 2 bottles by combining. We get 6R1 so 6 of 2l and 1 of 1l. Let’s further combine. 6R2 is 3R0 so we have 3 of 4l and that 1 of1l from prior calculation. We combine one more time 3R2 to get 1 of 8l, 1 of 4l and 1 of 1l. We can’t combine anymore cuz the amount of water has to be the same to be combined. We ideally want to combine using as less bottles as poss so to do that, we fill from the lowest amount poss 1l. We buy 1 1l and we can combine with our 1 of 1l to get 1 of 2l. But we still have 3 bottles - 1 of 8l, 1 of 4l and 1 of 2l. So the next smallest amount we have is 2l so we buy 2 more 1l to combine with our 1 of 2l. We thus get 2 of 4l and we combine and we get 2 of 8l and we combine and get 1 of 16l, which is less than 2 bottles.
Looking at this binary way (cuz we are combining with 2), 13 is 1101. We wanna make the number of 1s less or equal to the given m cuz number of 1s represent how many bottles there are and that index of 1s represent the amount of water it is holding. So we wanna make 1 become 0. We dont wanna make 0 -> 1 cuz that is increasing no. of 1s. So we get the rightmost index of 1(smallest amount of water poss) and we add 2^index number of bottles to our count and n(to update value of n). 2^index cuz that is how many bottles we need to make 1->0. For example, 1101 the rightmost index is 0 so we add 2^0 = 1 bottle and it becomes 1110. Still there are 3 1s so we get the next index which is 1. To make 1 of 2l, we need 2^1 = 2 more bottles to buy. So this formula makes sense.
We can get the rightmost index via reversing the binary string by tmp[::-1]
well explained here
https://latte-is-horse.tistory.com/364
solution
n, m = map(int, input().split())
ans = 0
while bin(n).count('1') > m:
index = bin(n)[2:][::-1].index('1')
ans += 2**index
n += 2**index
print(ans)complexity
count() is o(n) time but if we convert n to binary, the length becomes log(n) bits so time complexity is log(n)
The .count() method in Python has a time complexity of O(n), where 'n' is the number of elements in the list (or characters in the string) that you are counting. It needs to examine each element in the list (or character in the string) to count occurrences. Therefore, as the size of the input increases, the time it takes for .count() to execute will also increase linearly.
In your specific code, .count('1') is used to count the occurrences of the character '1' in the binary representation of n. The binary representation can have up to log2(n) bits, so in the worst case, it will take O(log n) time to count the '1's.
The while loop checks the count of '1's in the binary representation of n, which can have up to log2(n) bits. Therefore, it iterates at most log2(n) times, which makes the time complexity O(log n). This is because in each iteration, the code shifts right in the binary representation of n by at least one bit by adding 2^index to ans.
The space complexity remains O(1) because the code uses a fixed amount of memory regardless of the input values.
