# Minimum number of steps required to reach origin from a given point

Given two integers** A** and **B** representing coordinates of a point in the first quadrant, the task is to find the minimum number of steps required to reach the origin. All possible moves from a point **(i, j)** are **(i – 1, j), (i, j – 1)** or **(i, j)** (*staying at the same position*). **Note:** It is not allowed to move in the same direction twice in a row.

**Examples:**

Input:A = 4, B = 0Output:7Explanation:

Below are the movements from the given points to origin:

(4, 0) → (3, 0) → (3, 0)(stays) → (2, 0) → (2, 0)(stays) → (1, 0) → (1, 0)(stays) → (0, 0).

Hence, 7 moves are required to reach origin.

Input:A = 3, B = 5Output:9Explanation:

Below are the movements from the given points to origin:

(3, 5) → (3, 4) → (2, 4) → (2, 3) → (1, 3) → (1, 2) → (0, 2) → (0, 1) → (0, 1)(stays) → (0, 0).

Hence, 9 moves are required to reach origin.

**Naive Approach:** The simplest approach is to recursion. The idea is to recursively consider all possible moves from each point and for each of them, calculate the minimum number of steps required to reach the origin. **Time Complexity:** O(3^{max(A, B)})**Auxiliary Space:** O(1)

**Efficient Approach: **To optimize the above approach, the idea is based on the observation that if the **absolute difference between the x and y coordinates is 1 or 0**, then the minimum number of steps required to reach the origin is **(a + b)**. Otherwise, it takes **(2 * abs(a – b) – 1)** moves to reach **(k, k)**, where **k** is the minimum of **a, b**.

Therefore, the minimum number of steps required to reach origin from

(a, b)is equal to = (Steps required to reach (k, k) + Steps required to reach (0, 0) from (k, k)) = (2 * abs(a – b) – 1) + (2 * k)

Follow the steps below to solve the problem:

- Initialize a variable,
**ans**, which stores the minimum number of steps required to reach origin from**(a, b)**. - If the absolute difference of
**a**and**b**is**1**or**0**, then update**ans**to**(a + b)**. - Otherwise:
- Find the minimum of
**a, b**, and store it in a variable**k**. - Using the formula, update
**ans = (2 * abs(a – b) – 1) + (2 * k)**.

- Find the minimum of
- After completing the above steps, print the value of
**ans**as the result.

Below is the implementation for the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the minimum moves` `// required to reach origin from (a, b)` `void` `findMinMoves(` `int` `a, ` `int` `b)` `{` ` ` `// Stores the minimum number of moves` ` ` `int` `ans = 0;` ` ` `// Check if the absolute` ` ` `// difference is 1 or 0` ` ` `if` `(a == b || ` `abs` `(a - b) == 1) {` ` ` `ans = a + b;` ` ` `}` ` ` `else` `{` ` ` `// Store the minimum of a, b` ` ` `int` `k = min(a, b);` ` ` `// Store the maximum of a, b` ` ` `int` `j = max(a, b);` ` ` `ans = 2 * k + 2 * (j - k) - 1;` ` ` `}` ` ` `// Print the answer` ` ` `cout << ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given co-ordinates` ` ` `int` `a = 3, b = 5;` ` ` `// Function Call` ` ` `findMinMoves(a, b);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG` `{` ` ` ` ` `// Function to find the minimum moves` ` ` `// required to reach origin from (a, b)` ` ` `static` `void` `findMinMoves(` `int` `a, ` `int` `b)` ` ` `{` ` ` `// Stores the minimum number of moves` ` ` `int` `ans = ` `0` `;` ` ` `// Check if the absolute` ` ` `// difference is 1 or 0` ` ` `if` `(a == b || Math.abs(a - b) == ` `1` `)` ` ` `{` ` ` `ans = a + b;` ` ` `}` ` ` `else` ` ` `{` ` ` `// Store the minimum of a, b` ` ` `int` `k = Math.min(a, b);` ` ` `// Store the maximum of a, b` ` ` `int` `j = Math.max(a, b);` ` ` `ans = ` `2` `* k + ` `2` `* (j - k) - ` `1` `;` ` ` `}` ` ` `// Print the answer` ` ` `System.out.print(ans);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main (String[] args)` ` ` `{` ` ` ` ` `// Given co-ordinates` ` ` `int` `a = ` `3` `, b = ` `5` `;` ` ` `// Function Call` ` ` `findMinMoves(a, b);` ` ` `}` `}` `// This code is contributed by Dharanendra L V.` |

## Python3

`# Python3 program for the above approach` `# function to find the minimum moves` `# required to reach origin from (a, b)` `def` `findMinMoves(a, b):` ` ` ` ` `# Stores the minimum number of moves` ` ` `ans ` `=` `0` ` ` `# Check if the absolute` ` ` `# difference is 1 or 0` ` ` `if` `(a ` `=` `=` `b ` `or` `abs` `(a ` `-` `b) ` `=` `=` `1` `):` ` ` `ans ` `=` `a ` `+` `b` ` ` `else` `:` ` ` `# Store the minimum of a, b` ` ` `k ` `=` `min` `(a, b)` ` ` `# Store the maximum of a, b` ` ` `j ` `=` `max` `(a, b)` ` ` `ans ` `=` `2` `*` `k ` `+` `2` `*` `(j ` `-` `k) ` `-` `1` ` ` `# Prthe answer` ` ` `print` `(ans)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `# Given co-ordinates` ` ` `a,b ` `=` `3` `, ` `5` ` ` `# Function Call` ` ` `findMinMoves(a, b)` ` ` `# This code is contributed by mohit kumar 29.` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG` `{` ` ` `// Function to find the minimum moves` ` ` `// required to reach origin from (a, b)` ` ` `static` `void` `findMinMoves(` `int` `a, ` `int` `b)` ` ` `{` ` ` `// Stores the minimum number of moves` ` ` `int` `ans = 0;` ` ` `// Check if the absolute` ` ` `// difference is 1 or 0` ` ` `if` `(a == b || Math.Abs(a - b) == 1)` ` ` `{` ` ` `ans = a + b;` ` ` `}` ` ` `else` ` ` `{` ` ` `// Store the minimum of a, b` ` ` `int` `k = Math.Min(a, b);` ` ` `// Store the maximum of a, b` ` ` `int` `j = Math.Max(a, b);` ` ` `ans = 2 * k + 2 * (j - k) - 1;` ` ` `}` ` ` `// Print the answer` ` ` `Console.Write(ans);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `// Given co-ordinates` ` ` `int` `a = 3, b = 5;` ` ` `// Function Call` ` ` `findMinMoves(a, b);` ` ` `}` `}` `// This code is contributed by chitranayal.` |

## Javascript

`<script>` `// JavaScript program to implement the above approach` `// Function to find the minimum moves` `// required to reach origin from (a, b)` `function` `findMinMoves(a, b)` `{` ` ` `// Stores the minimum number of moves` ` ` `let ans = 0;` ` ` `// Check if the absolute` ` ` `// difference is 1 or 0` ` ` `if` `(a == b || Math.abs(a - b) == 1) {` ` ` `ans = a + b;` ` ` `}` ` ` `else` `{` ` ` `// Store the minimum of a, b` ` ` `let k = Math.min(a, b);` ` ` `// Store the maximum of a, b` ` ` `let j = Math.max(a, b);` ` ` `ans = 2 * k + 2 * (j - k) - 1;` ` ` `}` ` ` `// Print the answer` ` ` `document.write(ans);` `}` `// Driver Code` ` ` `// Given co-ordinates` ` ` `let a = 3, b = 5;` ` ` `// Function Call` ` ` `findMinMoves(a, b);` `</script>` |

**Output:**

9

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.