| 14 | const int inf = 1e9 + 7; |
| 15 | |
| 16 | ll int collatz(ll int curr, vector<ll int> &vec, ll int lv) |
| 17 | { |
| 18 | if (curr <= lv && vec[curr] != -1) |
| 19 | { |
| 20 | // when we find any number in chain which has a value more than -1, its time to stop |
| 21 | return vec[curr]; |
| 22 | } |
| 23 | // collatz basic rule: n even -> (n / 2), n odd - > 3n +1 |
| 24 | |
| 25 | ll int next = (3 * curr) + 1; |
| 26 | |
| 27 | if (curr % 2 == 0) |
| 28 | { |
| 29 | next = curr / 2; |
| 30 | } |
| 31 | // prev number in range = 1 + next number in range |
| 32 | // (8 -> 4 -> 2 -> 1) here (answer for 8 is 4) and (answer for 4 is 3) |
| 33 | int nextv = 1 + collatz(next, vec, lv); |
| 34 | // if number lies in range(0 - vector.size()) then update it , other ignore it |
| 35 | if (curr <= lv) |
| 36 | { |
| 37 | vec[curr] = nextv; |
| 38 | } |
| 39 | return nextv; |
| 40 | } |
| 41 | |
| 42 | void solve() |
| 43 | { |