Related: LeetCode 754 - Reach A Number
Find a number in minimum steps - GeeksforGeeks
Given an infinite number line from -INFINITY to +INFINITY and we are on zero. We can move n steps either side at each n'th time.
https://www.geeksforgeeks.org/minimum-moves-reach-target-infinite-line-set-2/
X. DFS without cache
https://www.geeksforgeeks.org/minimum-steps-to-reach-a-destination/
Find a number in minimum steps - GeeksforGeeks
Given an infinite number line from -INFINITY to +INFINITY and we are on zero. We can move n steps either side at each n'th time.
1st time; we can move only 1 step to both ways, means -1 1; 2nd time we can move 2 steps from -1 and 1; -1 : -3 (-1-2) 1(-1+2) 1 : -1 ( 1-2) 3(1+2) 3rd time we can move 3 steps either way from -3, 1, -1, 3 -3: -6(-3-3) 0(-3+3) 1: -2(1-3) 4(1+3) -1: -4(-1-3) 2(-1+3) 3: 0(0-3) 6(3+3) Find the minimum number of steps to reach a given number n.
This problem can be modeled as tree. We put initial point 0 at root, 1 and -1 as children of root. Next level contains values at distance 2 and so on.
0
/ \
-1 1
/ \ / \
1 -3 -1 3
/ \ / \ / \ / \
The problem is now to find the closes node to root with value n. The idea is to do Level Order Traversal of tree to find the closest node.
// To represent data of a node in treestruct number{ int no; int level;public: number() {} number(int n, int l):no(n),level(l) {}};// Prints level of node nvoid findnthnumber(int n){ // Create a queue and insert root queue<number> q; struct number r(0, 1); q.push(r); // Do level order traversal while (!q.empty()) { // Remove a node from queue struct number temp = q.front(); q.pop(); // To avoid infinite loop if (temp.no >= InF || temp.no <= -InF) break; // Check if dequeued number is same as n if (temp.no == n) { cout << "Found number n at level " << temp.level-1; break; } // Insert children of dequeued node to queue q.push(number(temp.no+temp.level, temp.level+1)); q.push(number(temp.no-temp.level, temp.level+1)); }
If target is negative, we can take it as positive because we start from 0 in symmetrical way.
Idea is to move in one direction as long as possible, this will give minimum moves. Starting at 0 first move takes us to 1, second move takes us to 3 (1+2) position, third move takes us to 6 (1+2+3) position, ans so on; So for finding target we keep on adding moves until we find the nth move such that 1+2+3+…+n>=target. Now if sum (1+2+3+…+n) is equal to target the our job is done, i.e we’ll need n moves to reach target. Now next case where sum is greater than target. Find the difference by how much we are ahead, i.e sum – target. Let the difference be d = sum – target.
If we take the i-th move backward then the new sum will become (sum – 2i), i.e 1+2+3+…-x+x+1…+n. Now if sum-2i = target then our job is done. Since, sum – target = 2i, i.e difference should be even as we will get an integer i flipping which will give the answer. So following cases arise.
Case 1 : Difference is even then answer is n, (because we will always get a move flipping which will lead to target).
Case 2 : Difference is odd, then we take one more step, i.e add n+1 to sum and now again take the difference. If difference is even the n+1 is the answer else we would have to take one more move and this will certainly make the difference even then answer will be n+2.
Idea is to move in one direction as long as possible, this will give minimum moves. Starting at 0 first move takes us to 1, second move takes us to 3 (1+2) position, third move takes us to 6 (1+2+3) position, ans so on; So for finding target we keep on adding moves until we find the nth move such that 1+2+3+…+n>=target. Now if sum (1+2+3+…+n) is equal to target the our job is done, i.e we’ll need n moves to reach target. Now next case where sum is greater than target. Find the difference by how much we are ahead, i.e sum – target. Let the difference be d = sum – target.
If we take the i-th move backward then the new sum will become (sum – 2i), i.e 1+2+3+…-x+x+1…+n. Now if sum-2i = target then our job is done. Since, sum – target = 2i, i.e difference should be even as we will get an integer i flipping which will give the answer. So following cases arise.
Case 1 : Difference is even then answer is n, (because we will always get a move flipping which will lead to target).
Case 2 : Difference is odd, then we take one more step, i.e add n+1 to sum and now again take the difference. If difference is even the n+1 is the answer else we would have to take one more move and this will certainly make the difference even then answer will be n+2.
Explanation : Since difference is odd. Target is either odd or even.
case 1: n is even (1+2+3+…+n) then adding n+1 makes the difference even.
case 2: n is odd then adding n+1 doesn’t makes difference even so we would have to take one more move, so n+2.
case 1: n is even (1+2+3+…+n) then adding n+1 makes the difference even.
case 2: n is odd then adding n+1 doesn’t makes difference even so we would have to take one more move, so n+2.
Example:
target = 5.
we keep on taking moves until we reach target or we just cross it.
sum = 1 + 2 + 3 = 6 > 5, step = 3.
Difference = 6 – 5 = 1. Since the difference is an odd value, we will not reach the target by flipping any move from +i to -i. So we increase our step. We need to increase step by 2 to get an even difference (since n is odd and target is also odd). Now that we have an even difference, we can simply switch any move to the left (i.e. change + to -) as long as the summation of the changed value equals to half of the difference. We can switch 1 and 4 or 2 and 3 or 5
target = 5.
we keep on taking moves until we reach target or we just cross it.
sum = 1 + 2 + 3 = 6 > 5, step = 3.
Difference = 6 – 5 = 1. Since the difference is an odd value, we will not reach the target by flipping any move from +i to -i. So we increase our step. We need to increase step by 2 to get an even difference (since n is odd and target is also odd). Now that we have an even difference, we can simply switch any move to the left (i.e. change + to -) as long as the summation of the changed value equals to half of the difference. We can switch 1 and 4 or 2 and 3 or 5
https://www.geeksforgeeks.org/minimum-steps-to-reach-a-destination/
