## Thursday, August 4, 2016

### Find a number in minimum steps - GeeksforGeeks

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 tree`
`struct` `number`
`{`
`    ``int` `no;`
`    ``int` `level;`
`public``:`
`    ``number() {}`
`    ``number(``int` `n, ``int` `l):no(n),level(l) {}`
`};`

`// Prints level of node n`
`void` `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));`
`    ``}`