6 min read · Dec 1, 2023
--
It is a problem of finding the number of operations when n is made zero according to the rule. It can be easily solved by using Math rather than Dynamic Programming. The time complexity is O(log²n), and there is also a way to solve only O(logn).
Korean Blog : https://blog.naver.com/hongdevlife/223280577172
Problem of finding the minimum number of operations when n is zeroed according to the rule
Rule: To change the i-th, the i-1th bit must be 1 and the rest must be 0.
Input
- n : a number to be replaced by zero
Output
- Minimum number of operations
Constraints
- 0 ≤ n ≤ 10⁹
Let’s figure out the rules by considering the easy case. If we think about 2^i, i is the index of bit, n = 8 when i = 3 and 1000 in binary. To change to 3rd bit 1 → 0, you can make 0100 by making 1100 and erasing 1. 0100 is the value when the i-th is 2. If this operation is f(i), then f(i) = f(i-1) + 1. To make 1000 zero, proceed to 1000 → 1100 → 0100 → 0000. That is, in order to change the i-th bit, it proceeds in the order of i-1th bit 1 → i-th bit 0 → i-1th bit 0. In terms of expression, $f(i)=f(i-1) + 1 + f’(i-1)$, and f’ is 0→1. Since f’ and f are the same, we can organize them as f(i) = 2*f(i-1) + 1.
It can be seen that n → 0 and 0 → n have the same shortest path. This can be easily proved. The path with n → 0 is the shortest path (a1, a2, … , an) Assume that the opposite is shorter when there is. The path of 0 → n is shorter (b1, b2, …, bm), n > m. Again (b1, b2, … , bm) is reversed (a1, a2, . . . … an) should be the shortest route, but contradictions arise because it is said to be shorter in the assumption. If you think of it as a graph, it is easy to see that there is no other path because it is a non-directional graph.
Let’s think of a case with the rest of the bits in addition to 2^i. If n = 10, then 1010 → 1100 → 0100 → 0. To change the i-th bit, the i-1th bit must be 1. In the end, it’s similar to the easy case I did above and there’s only a slight difference. 1000 → 1010 → 1100 → 0100 → 0 There is a difference by 1000 → 1010 before. If a is 1000 → 1010, then f(1000) = a + f(1010), then f(1010) = f(1000) — a.
f(i) can be calculated in two ways.
- With dynamic programming, f(i) can be calculated. Since f(i) is recursive, i-th is a method of storing the calculated value.
- In a better way, we can calculate f(i) with Math. It is calculated as f(i) = 2^{i+1}-1. f(0) = 2–1 = 1 f(1) = 4–1 = 3 f(2) = 8–1 = 7
If there is a bit in the middle, f(n) = f(i) — a and subtract by a. Continue to repeat f(n) = f(i) — a = f(i) — (f(i’)-a’). If you think of the binary 1111 case, f(1111) = f(1000) — (f(0100) — (f(0010) — f(0001))) and write it down f(1111) = f(1000) — f(0100) + f(0010) — f(0001).
Code
- Define the mask and answer to find the location of the bit.
- Apply the formula while repeating each bit.
class Solution {
public:
int minimumOneBitOperations(int n) {
int ans = 0;
int mask = 1;
for (int i = 0; mask <= n; ++i, mask <<= 1) {
if (n & mask) {
ans = ((1<<(i+1))-1) - ans;
}
}
return ans;
}
};Complexity
Beats 100%
- Time complexity: O(log²n)
- f(i) Calculation: O(logn)
- bit navigation: O(logn) - Space complexity: O(1)
Advanced Code
This problem is the same as “Gray Code”.
Gray Code means a code with a difference of 1 bit between the previous number and the next number https://en.wikipedia.org/wiki/Gray_code
According to the rules in question, it can be seen that the problem is also only 1 bit different.
A function that converts n into a gray code is defined in the wiki, and you can use this function as it is. This is because the number changed to the gray code is the number that was moved one by one. That means the gray code is the number of operations.
Looking at the change in the gray code when increasing the binary value, it is the same as the rule in this problem. This problem is to find the number of operations when n → 0. It can be seen that the number of operations becomes the value obtained by changing the gray code to decimal.
If you look at the table, there is Gray and you can move to Decimal 0 to make the Gray value 0. Since Decimal is sequentially from zero, it eventually becomes the number of operations that Decimal makes n → 0. In the input, n becomes the value of a particular gray code, Output is the value obtained by changing the gray code to the binary value.
class Solution {
public:
int minimumOneBitOperations(int n) {
int ans = n;
ans ^= ans >> 16;
ans ^= ans >> 8;
ans ^= ans >> 4;
ans ^= ans >> 2;
ans ^= ans >> 1;
return ans;
}
};Complexity
Beats 100%
- Time complexity: O(logn)
- Space complexity: O(1)
It’s a problem that I couldn’t solve in four hours. We have figured out how the data is going, but we have not been able to get out of the swamp of DP. I keep trying to define DP, and I think the cause is that I couldn’t find a better way there. I think I could have solved it if I had found it right away. When solving the problem, the DP didn’t cover it as if the condition was strong, so I should think about it differently at this time.
Minimum number of operations when n -> 0 i-1=1, i-2=0 must be used to change the i-th bit
n range 100 million There are 32 bits
i is affected by -1, -2 parts +1 parts affected x One by one in the direction of decreasing i
In order for the i-th to change, it is important how many times the -1 and -2 parts change There are four states: 00, 01, 10 and 11
You can save the number of times you change using DP dp[i][10] = i-th and -1, -2 is 1,0, changeable only then dp[i][00] = d[i-1][00], d[i-1][01], d[i-1][10] = d[i-2][0x] -> d[i-3][10] , d[i-1][11] = d[i-2] i000, i001, i010, i011
arrangement If i is 1, make dp[i][10] and change i to 0 Skip if i is 0
Determining whether the back value should be changed when a change is needed 3 Change Cases d[i][00]: i-1 needs to be changed to 1 d[i][01]: i-1 needs to be changed to 1, i-2 needs to be changed to 0 d[i][11]: i-2 needs to be changed to 0
Should I change the n, I don’t think I need to change it.. hair loss i-1, i-2 must change state at the i-th time
dp[i][0,1][0,1]
I don’t understand the problem… That’s why my condition was weird i-1 must be 1, i-2 to 0 must be 0.. All must be set to 0 from i-2 You can jump if the number of beats is 1 1100 -> 0100 i+1 is 1, i is also 1, i-1 is 0 The next time we start, 10,000… Continuing on.. 100.. Change required 1000.. -> 1100.. the number of cases to be changed Set to 1000… after the first step
- dp[i]: the number of times i-th 1->0, i-1 is 1 and the rest are 0
- dp[i][j]: The number of cases where i-th is changed to j, from i-1 to the rest must be guaranteed to be zero
3: 1111 -> 1101 -> 1100 -> 0100 4: 100 -> 101 -> 111 -> 110 -> 2: 010) -> 011 -> 1: 001 -> 000
1011 -> 1010 -> 1100 8+4=1100, 4->2(10) 3. dp[num] : The number of cases where num is 0
The dp expression is weird, so I can’t save the status well, Save only a part of the status and cover the changes, resulting in a strange value
