Given coordinates of a source point (x1, y1) determine if it is possible to reach the destination point (x2, y2). From any point (x, y) there only two types of valid movements:
(x, x + y) and (x + y, y). Return a boolean true if it is possible else return false.
Note: All coordinates are positive.
Asked in: Expedia, Telstra
Examples:
Input : (x1, y1) = (2, 10)
(x2, y2) = (26, 12)
Output : True
(2, 10)->(2, 12)->(14, 12)->(26, 12)
is a valid path.
Input : (x1, y1) = (20, 10)
(x2, y2) = (6, 12)
Output : False
No such path is possible because x1 > x2
and coordinates are positive
The problem can be solved using simple recursion. Base case would be to check if current x or y coordinate is greater than that of destination, in which case we return false. If it is not the destination point yet we make two calls for both valid movements from that point.
If any of them yields a path we return true else return false.
C++
#include <bits/stdc++.h>
using namespace std;
bool isReachable( int sx, int sy, int dx, int dy)
{
if (sx > dx || sy > dy)
return false ;
if (sx == dx && sy == dy)
return true ;
return (isReachable(sx + sy, sy, dx, dy) ||
isReachable(sx, sy + sx, dx, dy));
}
int main()
{
int source_x = 2, source_y = 10;
int dest_x = 26, dest_y = 12;
if (isReachable(source_x, source_y, dest_x, dest_y))
cout << "True\n" ;
else
cout << "False\n" ;
return 0;
}
|
Java
class GFG {
static boolean isReachable( int sx, int sy,
int dx, int dy)
{
if (sx > dx || sy > dy)
return false ;
if (sx == dx && sy == dy)
return true ;
return (isReachable(sx + sy, sy, dx, dy) ||
isReachable(sx, sy + sx, dx, dy));
}
public static void main(String arg[])
{
int source_x = 2 , source_y = 10 ;
int dest_x = 26 , dest_y = 12 ;
if (isReachable(source_x, source_y, dest_x,
dest_y))
System.out.print( "True\n" );
else
System.out.print( "False\n" );
}
}
|
Python3
def isReachable(sx, sy, dx, dy):
if (sx > dx or sy > dy):
return False
if (sx = = dx and sy = = dy):
return True
return (isReachable(sx + sy, sy, dx, dy) or
isReachable(sx, sy + sx, dx, dy))
source_x, source_y = 2 , 10
dest_x, dest_y = 26 , 12
if (isReachable(source_x, source_y, dest_x, dest_y)):
print ( "True" )
else :
print ( "False" )
|
C#
using System;
class GFG {
static bool isReachable( int sx, int sy,
int dx, int dy)
{
if (sx > dx || sy > dy)
return false ;
if (sx == dx && sy == dy)
return true ;
return (isReachable(sx + sy, sy, dx, dy) ||
isReachable(sx, sy + sx, dx, dy));
}
public static void Main()
{
int source_x = 2, source_y = 10;
int dest_x = 26, dest_y = 12;
if (isReachable(source_x, source_y, dest_x,
dest_y))
Console.Write( "True\n" );
else
Console.Write( "False\n" );
}
}
|
PHP
<?php
function isReachable( $sx , $sy , $dx , $dy )
{
if ( $sx > $dx || $sy > $dy )
return false;
if ( $sx == $dx && $sy == $dy )
return true;
return (isReachable( $sx + $sy , $sy , $dx , $dy ) ||
isReachable( $sx , $sy + $sx , $dx , $dy ));
}
$source_x = 2;
$source_y = 10;
$dest_x = 26;
$dest_y = 12;
if (isReachable( $source_x , $source_y ,
$dest_x , $dest_y ))
echo "True\n" ;
else
echo "False\n" ;
?>
|
Javascript
<script>
function isReachable(sx, sy, dx, dy)
{
if (sx > dx || sy > dy)
return false ;
if (sx == dx && sy == dy)
return true ;
return (isReachable(sx + sy, sy, dx, dy) ||
isReachable(sx, sy + sx, dx, dy));
}
let source_x = 2, source_y = 10;
let dest_x = 26, dest_y = 12;
if (isReachable(source_x, source_y, dest_x,
dest_y))
document.write( "True\n" );
else
document.write( "False\n" );
</script>
|