达到目标的最小步骤，给定 (1, 0) 和操作 A = 2A - B 或 B = 2B - A
Minimum steps to reach target, given (1, 0) and operations A = 2A - B or B = 2B - A
我参加了面试，但我无法给出解决问题的最佳方法。
A=1, B=0
- Operation L: A=2A-B
- Operation R: B=2B-A
For each step, only one operation(L or R) is taken place.
For a given number N, what is the minimum number of operations required to make A or B equals to N?
最重要的是效率。
提前致谢。
在k次操作中你可以得到[-(2^k)+1, 2^k]中N的所有值。
注意 abs(A) + abs(B) = 2^k 对于所有可能的 k 路径，并且 A 和 B 正好覆盖范围 [-(2^k)+1, 2^k] in长度为 k 的路径集。
k=0: (1,0)
k=1: (1,-1), (2,0)
k=2: (1,-3), (2,-2), (3,-1), (4,0)
etc...
给定N，我们可以通过log找到最小的k。然后我们知道最后一对是 (N, N - 2^k) （或 (N-2^k, N) 如果 N <= 0）。沿着路径回到 k=0 很容易，因为对于下一个较小的 k，这两个元素之一将超出范围。
例如，N = 35。
Log2(35) = 5.13, so we use k=6.
2^6 = 64, so our final pair is (35, -29)
(35,-29) -> (3,-29) -> (3, -13) -> (3, -5) -> (3,-1) -> (1,-1) -> (1,0)
求出k是O(1)，找到路径是O(k)也就是O(log(abs(N))。
你不太可能需要在面试中证明任何事情，但如果你这样做了，你可以使用这个：
通过观察：A - B = 2^k for k steps observed for small k.
然后通过归纳法：我们有一些有效的 (A, B) s.t。 A-B = 2^k。然后 L 得到我们 (2A-B, B)，但是 2A-B-B = 2A-2B = 2(A-B) = 2^(k+1) 根据需要。同样对于 R.
这对于面试来说是一项具有挑战性的任务，但我会从递归开始，试图从结果中找到起源。给定有效 (A', B)，其中 A' 是我们追求的目标，
A' = 2A - B
对于一些A，这意味着
A = (A' + B) / 2
后者告诉我们，路径中的所有(A' + B)都必须能被2整除，由于路径结束（开始）于1，所以其中的所有(A' + B)都是2的幂。
我们可以观察到另一个属性，虽然它可能与解决方案无关，但一旦我们在第一步切换到(even, even)或(odd, odd)，我们就无法切换回来.
我参加了面试，但我无法给出解决问题的最佳方法。
A=1, B=0
- Operation L: A=2A-B
- Operation R: B=2B-A
For each step, only one operation(L or R) is taken place.
For a given number N, what is the minimum number of operations required to make A or B equals to N?
最重要的是效率。
提前致谢。
在k次操作中你可以得到[-(2^k)+1, 2^k]中N的所有值。
注意 abs(A) + abs(B) = 2^k 对于所有可能的 k 路径，并且 A 和 B 正好覆盖范围 [-(2^k)+1, 2^k] in长度为 k 的路径集。
k=0: (1,0)
k=1: (1,-1), (2,0)
k=2: (1,-3), (2,-2), (3,-1), (4,0)
etc...
给定N，我们可以通过log找到最小的k。然后我们知道最后一对是 (N, N - 2^k) （或 (N-2^k, N) 如果 N <= 0）。沿着路径回到 k=0 很容易，因为对于下一个较小的 k，这两个元素之一将超出范围。
例如，N = 35。
Log2(35) = 5.13, so we use k=6.
2^6 = 64, so our final pair is (35, -29)
(35,-29) -> (3,-29) -> (3, -13) -> (3, -5) -> (3,-1) -> (1,-1) -> (1,0)
求出k是O(1)，找到路径是O(k)也就是O(log(abs(N))。
你不太可能需要在面试中证明任何事情，但如果你这样做了，你可以使用这个：
通过观察：A - B = 2^k for k steps observed for small k.
然后通过归纳法：我们有一些有效的 (A, B) s.t。 A-B = 2^k。然后 L 得到我们 (2A-B, B)，但是 2A-B-B = 2A-2B = 2(A-B) = 2^(k+1) 根据需要。同样对于 R.
这对于面试来说是一项具有挑战性的任务，但我会从递归开始，试图从结果中找到起源。给定有效 (A', B)，其中 A' 是我们追求的目标，
A' = 2A - B
对于一些A，这意味着
A = (A' + B) / 2
后者告诉我们，路径中的所有(A' + B)都必须能被2整除，由于路径结束（开始）于1，所以其中的所有(A' + B)都是2的幂。
我们可以观察到另一个属性，虽然它可能与解决方案无关，但一旦我们在第一步切换到(even, even)或(odd, odd)，我们就无法切换回来.