# 30.11.2023 [1611. Minimum One Bit Operations to Make Integers Zero]
Minimum rounds of inverting rightmost bit or left of the rightmost `1` bit to make `n` zero
30.11.2023
1611. Minimum One Bit Operations to Make Integers Zero hard
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/421
Problem TLDR
Minimum rounds of inverting rightmost bit or left of the rightmost 1
bit to make n
zero
Intuition
Let’s observe the example:
// 6
// 110
// 010 b
// 011 a
// 001 b
// 000 a
// 10 = 2 + f(1) = 2^1 + f(2^0)
// 11 a
// 01 b -> f(1)
// 100 = 4 + f(10) = 2^2 + f(2^1)
// 101 a
// 111 b
// 110 a
// 010 b -> f(10)
// 1000 = 8 + f(100) = 2^3 + f(2^2)
// 1001 a
// 1011 b
// 1010 a
// 1110 b
// 1111 a
// 1101 b
// 1100 a
// 0100 b -> f(100)
There are two tricks we can derive:
Each single-bit number has a recurrent count of operations: f(0b100) = 0b100 + f(0b10) and so on.
The hard trick: when we consider the non-single-bit number, like
1101
, we dof(0b1101) = f(0b1000) - f(0b100) + f(0b1)
.
Complexity
Time complexity:
O(log(n))Space complexity:
O(log(n))
Code
fun minimumOneBitOperations(n: Int): Int {
val f = HashMap<Int, Int>()
f[0] = 0
f[1] = 1
var curr = 2
while (curr > 0) {
f[curr] = curr + f[curr / 2]!!
curr *= 2
}
var res = 0
var sign = 1;
for (i in 0..31) {
val bit = 1 shl i
if (n and bit != 0) {
res += sign * f[bit]!!
sign = -sign
}
}
return Math.abs(res)
}