Number of steps required to reach point (x,y) from (0,0) using zig-zag way

0 0 3 minutes read

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 position
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
int 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:

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 zambiatek!