Given a coordinate (x, y). The task is to calculate the number of steps required to reach point (x, y) from (0, 0) using zig-zag way and you cannot travel in straight line for more than 1 unit. Also, start moving along Y axis.
For example we can reach the Point denoted by red color in the respective ways as shown in the below diagram:
Examples:
Input: x = 4, y = 4 Output: 8 In the diagram above the line is passing using 8 steps. Input: x = 4, y = 3 Output: 9 Input: x = 2, y = 1 Output: 5
Approach: By sketching a small diagram we can see the two cases:
- Case 1: If x is less than y then answer will always be x + y + 2*((y-x)/2).
- Case 2: If x is greater than equal to y then answer will always be x + y + 2*(((x-y)+1)/2).
Below is the implementation of the above approach:
C++
// C++ program to find the number of steps// required to reach (x, y) from (0, 0) following// a zig-zag path#include <bits/stdc++.h>using namespace std;// Function to return the required positionint countSteps(int x, int y){ if (x < y) { return x + y + 2 * ((y - x) / 2); } else { return x + y + 2 * (((x - y) + 1) / 2); }}// Driver Codeint main(){ int x = 4, y = 3; cout << countSteps(x, y); return 0;} |
Java
// Java program to find the number of steps // required to reach (x, y) from (0, 0) following // a zig-zag path class GfG {// Function to return the required position static int countSteps(int x, int y) { if (x < y) { return x + y + 2 * ((y - x) / 2); } else { return x + y + 2 * (((x - y) + 1) / 2); } } // Driver Code public static void main(String[] args) { int x = 4, y = 3; System.out.println(countSteps(x, y)); }} // This code is contributed by Prerna Saini |
Python3
# Python3 program to find the number of # steps required to reach (x, y) from # (0, 0) following a zig-zag path # Function to return the required position def countSteps(x, y): if x < y: return x + y + 2 * ((y - x) // 2) else: return x + y + 2 * (((x - y) + 1) // 2) # Driver Code if __name__ == "__main__": x, y = 4, 3 print(countSteps(x, y)) # This code is contributed by Rituraj Jain |
C#
// C# program to find the number of steps // required to reach (x, y) from (0, 0) // following a zig-zag path using System;class GfG {// Function to return the required position static int countSteps(int x, int y) { if (x < y) { return x + y + 2 * ((y - x) / 2); } else { return x + y + 2 * (((x - y) + 1) / 2); } } // Driver Code public static void Main() { int x = 4, y = 3; Console.WriteLine(countSteps(x, y)); }} // This code is contributed by Code_Mech. |
PHP
<?php// PHP program to find the number of steps // required to reach (x, y) from (0, 0) // following a zig-zag path // Function to return the required position function countSteps($x, $y) { if ($x < $y) { return $x + $y + 2 * (($y - $x) / 2); } else { return $x + $y + 2 * ((($x - $y) + 1) / 2); } } // Driver Code $x = 4; $y = 3; echo(countSteps($x, $y)); // This code is contributed // by Code_Mech.?> |
Javascript
<script> // Javascript program to find the number of steps // required to reach (x, y) from (0, 0) following // a zig-zag path // Function to return the required position function countSteps(x, y) { if (x < y) { return x + y + 2 * parseInt((y - x) / 2); } else { return x + y + 2 * parseInt(((x - y) + 1) / 2); } } // Driver Code var x = 4, y = 3; document.write(countSteps(x, y));// This code is contributed by rrrtnx. </script> |
Output:
9
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
