# Path traversed using exactly M coins in K jumps

Given three integers **N**, **K** and** M** representing the Number of boxes (aligned horizontally from 1 to **N**), total numbers of allowed jumps and total available coins respectively, the task is to print the path that can be traversed within **[1, N]** by using exactly** M** coins in exactly **K** jumps. If a jump is made from position **X** to position **Y** then **abs(X – Y)** coins are used. If it is not possible to use **M** coins in **K** jumps, then print -1.**Examples:**

Input :N = 5, K = 4, M = 12Output :5 1 4 5Explanation :

First jump: Box 1 -> Box 5. Hence, |1-5| = 4 coins used.

Second Jump: Box 5 -> Box 1 Hence, |5-1| = 4 coins used.

Third Jump: Box 1 -> Box 4 using 3 coins.

Fourth Jump: Box 4 -> Box 5 using 1 coin.

Hence, exactly 12 coins used in 4 jumps.Input :N = 4, K = 3, M = 10Output :-1

**Approach:**

We can observe that the answer will be -1 for the following two cases:

K > N-1or

K * (N-1) < M.

The problem can be solved using Greedy Approach following the steps given below:

Repeat the below operation until **K** become zero.

- Find the minimum of
**N-1**and**M – K – 1**. - Based on the above minimum value, move towards the left or right based on the availability reduce K.
- Repeat the above steps until K becomes 0.

Below is implementation of the above approach:

## C++

`// C++ program to print` `// the path using exactly` `// K jumps and M coins` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function that print the path` `// using exactly K jumps and M coins` `void` `print_path(` `int` `N, ` `int` `jump, ` `int` `coin)` `{` ` ` `// If no path exists` ` ` `if` `(jump > coin` ` ` `|| jump * (N - 1) < coin) {` ` ` `cout << ` `"-1"` `<< endl;` ` ` `}` ` ` `else` `{` ` ` `int` `pos = 1;` ` ` `while` `(jump > 0) {` ` ` `// It decides which` ` ` `// box to be jump` ` ` `int` `tmp = min(N - 1,` ` ` `coin - (jump - 1));` ` ` `// It decides whether` ` ` `// to jump on left side or` ` ` `// to jump on right side` ` ` `if` `(pos + tmp <= N) {` ` ` `pos += tmp;` ` ` `}` ` ` `else` `{` ` ` `pos -= tmp;` ` ` `}` ` ` `// Print the path` ` ` `cout << pos << ` `" "` `;` ` ` `coin -= tmp;` ` ` `jump -= 1;` ` ` `}` ` ` `}` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 5, K = 4, M = 12;` ` ` `// Function Call` ` ` `print_path(N, K, M);` ` ` `return` `0;` `}` |

## Java

`// Java program to print the path` `// using exactly K jumps and M coins` `import` `java.io.*;` `class` `GFG{` `// Function that print the path` `// using exactly K jumps and M coins` `static` `void` `print_path(` `int` `N, ` `int` `jump,` ` ` `int` `coin)` `{` ` ` `// If no path exists` ` ` `if` `(jump > coin || jump * (N - ` `1` `) < coin)` ` ` `{` ` ` `System.out.println(` `"-1"` `);` ` ` `}` ` ` `else` ` ` `{` ` ` `int` `pos = ` `1` `;` ` ` `while` `(jump > ` `0` `)` ` ` `{` ` ` ` ` `// It decides which` ` ` `// box to be jump` ` ` `int` `tmp = Math.min(N - ` `1` `,` ` ` `coin - (jump - ` `1` `));` ` ` ` ` `// It decides whether` ` ` `// to jump on left side or` ` ` `// to jump on right side` ` ` `if` `(pos + tmp <= N)` ` ` `{` ` ` `pos += tmp;` ` ` `}` ` ` `else` ` ` `{` ` ` `pos -= tmp;` ` ` `}` ` ` ` ` `// Print the path` ` ` `System.out.print(pos + ` `" "` `);;` ` ` ` ` `coin -= tmp;` ` ` `jump -= ` `1` `;` ` ` `}` ` ` `}` `}` ` ` `// Driver Code` `public` `static` `void` `main (String[] args)` `{` ` ` `int` `N = ` `5` `, K = ` `4` `, M = ` `12` `;` ` ` ` ` `// Function Call` ` ` `print_path(N, K, M);` `}` `}` `// This code is contributed by shubhamsingh10` |

## Python3

`# Python3 program to print the path ` `# using exactly K jumps and M coins` `# Function that pr the path` `# using exactly K jumps and M coins` `def` `print_path(N, jump, coin):` ` ` `# If no path exists` ` ` `if` `(jump > coin ` `or` ` ` `jump ` `*` `(N ` `-` `1` `) < coin):` ` ` `print` `(` `"-1"` `)` ` ` ` ` `else` `:` ` ` `pos ` `=` `1` `;` ` ` `while` `(jump > ` `0` `):` ` ` `# It decides which` ` ` `# box to be jump` ` ` `tmp ` `=` `min` `(N ` `-` `1` `,` ` ` `coin ` `-` `(jump ` `-` `1` `));` ` ` `# It decides whether` ` ` `# to jump on left side or` ` ` `# to jump on right side` ` ` `if` `(pos ` `+` `tmp <` `=` `N):` ` ` `pos ` `+` `=` `tmp;` ` ` `else` `:` ` ` `pos ` `-` `=` `tmp;` ` ` ` ` `# Print the path` ` ` `print` `(pos, end ` `=` `" "` `)` ` ` `coin ` `-` `=` `tmp;` ` ` `jump ` `-` `=` `1` `;` ` ` `# Driver code` `N ` `=` `5` `K ` `=` `4` `M ` `=` `12` `# Function call` `print_path(N, K, M);` ` ` `# This code is contributed by grand_master` |

## C#

`// C# program to print the path` `// using exactly K jumps and M coins` `using` `System;` `class` `GFG{` `// Function that print the path` `// using exactly K jumps and M coins` `static` `void` `print_path(` `int` `N, ` `int` `jump,` ` ` `int` `coin)` `{` ` ` ` ` `// If no path exists` ` ` `if` `(jump > coin || jump * (N - 1) < coin)` ` ` `{` ` ` `Console.WriteLine(` `"-1"` `);` ` ` `}` ` ` ` ` `else` ` ` `{` ` ` `int` `pos = 1;` ` ` `while` `(jump > 0)` ` ` `{` ` ` ` ` `// It decides which` ` ` `// box to be jump` ` ` `int` `tmp = Math.Min(N - 1,` ` ` `coin - (jump - 1));` ` ` ` ` `// It decides whether` ` ` `// to jump on left side or` ` ` `// to jump on right side` ` ` `if` `(pos + tmp <= N)` ` ` `{` ` ` `pos += tmp;` ` ` `}` ` ` `else` ` ` `{` ` ` `pos -= tmp;` ` ` `}` ` ` ` ` `// Print the path` ` ` `Console.Write(pos + ` `" "` `);` ` ` ` ` `coin -= tmp;` ` ` `jump -= 1;` ` ` `}` ` ` `}` `}` ` ` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `N = 5, K = 4, M = 12;` ` ` ` ` `// Function Call` ` ` `print_path(N, K, M);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// JavaScript program to print the path` `// using exactly K jumps and M coins` `// Function that print the path` `// using exactly K jumps and M coins` `function` `print_path(N, jump, coin)` `{` ` ` `// If no path exists` ` ` `if` `(jump > coin || jump * (N - 1) < coin)` ` ` `{` ` ` `document.write(` `"-1"` `);` ` ` `}` ` ` `else` ` ` `{` ` ` `let pos = 1;` ` ` `while` `(jump > 0)` ` ` `{` ` ` ` ` `// It decides which` ` ` `// box to be jump` ` ` `let tmp = Math.min(N - 1,` ` ` `coin - (jump - 1));` ` ` ` ` `// It decides whether` ` ` `// to jump on left side or` ` ` `// to jump on right side` ` ` `if` `(pos + tmp <= N)` ` ` `{` ` ` `pos += tmp;` ` ` `}` ` ` `else` ` ` `{` ` ` `pos -= tmp;` ` ` `}` ` ` ` ` `// Print the path` ` ` `document.write(pos + ` `" "` `);;` ` ` ` ` `coin -= tmp;` ` ` `jump -= 1;` ` ` `}` ` ` `}` `} ` ` ` `// Driver Code` ` ` `let N = 5, K = 4, M = 12;` ` ` ` ` `// Function Call` ` ` `print_path(N, K, M);` ` ` `</script>` |

**Output:**

5 1 4 5

**Time Complexity: **O(K)**Auxiliary Space: **O(1)