Given an array arr[] consisting of N positive integers and two integers X and Y, the task is to check if it is possible to reach (X, Y) from (0, 0) such that moving to (Xf, Yf) from (Xi, Yi) is allowed only if the euclidean distance between them is present in the array arr[]. If it is possible, then print Yes. Otherwise, print No.
Note: Each distance present in the array arr[] can be used at most once.
Examples:
Input: arr[ ] = {2, 5}, X = 5, Y= 4
Output: Yes
Explanation:
Following are the moves required to reach from (0, 0) to (5, 4):
- Move from point (0, 0) to (2, 0). The euclidean distance is sqrt((2 – 0)2 + (0 – 0)) = 2, which is present in the array.
- Move from point (2, 0) to (5, 4). The euclidean distance is sqrt((5 – 2)2 + (4 – 0)2) = 5, which is present in the array.
After the above set of moves, the point (5, 4) can be reached. Hence, print Yes.
Input: arr[] = {4}, X = 3, Y= 4
Output: No
Approach: The given problem can be solved by using the following observations by considering the Euclidean Distance between points (0, 0) to (X, Y) as Z = sqrt(X*X + Y*Y), then the problem can be divided into 3 cases:
- If the sum of the array element is less than Z, it is impossible to reach (X, Y) by any set of moves.
- If the sum of the array element is equal to Z, it is possible to reach (X, Y) after N moves.
- Otherwise for every distance check for the following conditions:
- If for any A[i], A[i] > Z + (All other distance except A[i]) then it is never possible to reach (X, Y) because the path will be a polygon and for an N-polygon the sum of (N – 1) sides must be greater than the other side for every possible side.
- Otherwise, it is always possible to reach the point (X, Y).
From the above observations considering the three cases, print the result accordingly.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the point (X, Y)// is reachable from (0, 0) or notint isPossibleToReach(int A[], int N, int X, int Y){ // Find the Euclidean Distance double distance = sqrt(double(X * X + Y * Y)); // Calculate the maximum distance double mx = 0; for (int i = 0; i < N; i++) { mx += double(A[i]); } // Case 1. if (mx < distance) { cout << "NO"; return 0; } // Case 2. if ((mx - distance) < 0.000001) { cout << "YES"; return 0; } // Otherwise, check for the polygon // condition for each side for (int i = 0; i < N; i++) { if (distance + mx < double(2) * double(A[i])) { cout << "No"; return 0; } } // Otherwise, print Yes cout << "Yes"; return 0;}// Driver Codeint main(){ int A[] = { 2, 5 }; int X = 5, Y = 4; int N = sizeof(A) / sizeof(A[0]); isPossibleToReach(A, N, X, Y); return 0;} |
Java
// C# program for the above approachimport java.io.*;class GFG{ // Function to check if the point (X, Y)// is reachable from (0, 0) or notstatic int isPossibleToReach(int []A, int N, int X, int Y){ // Find the Euclidean Distance double distance = Math.sqrt((X * X + Y * Y)); // Calculate the maximum distance double mx = 0; for(int i = 0; i < N; i++) { mx += (A[i]); } // Case 1. if (mx < distance) { System.out.print("NO"); return 0; } // Case 2. if ((mx - distance) < 0.000001) { System.out.print("YES"); return 0; } // Otherwise, check for the polygon // condition for each side for(int i = 0; i < N; i++) { if (distance + mx < 2 * A[i]) { System.out.print("No"); return 0; } } // Otherwise, print Yes System.out.print("Yes"); return 0;}// Driver Codepublic static void main (String[] args){ int []A = { 2, 5 }; int X = 5, Y = 4; int N = A.length; isPossibleToReach(A, N, X, Y);}}// This code is contributed by shivanisinghss2110 |
Python3
# Python program for the above approachimport math# Function to check if the point(X, Y)# is reachable from (0, 0) or notdef isPossibleToReach(A, N, X, Y): # Find the Euclidean Distance distance = math.sqrt(X * X + Y * Y) # Calculate the maximum distance mx = 0 for i in range(N): mx += A[i] # Case 1. if (mx < distance): print("NO") return 0 # Case 2. if ((mx - distance) < 0.000001): print("YES") return 0 # Otherwise, check for the polygon # condition for each side for i in range(N): if (distance + mx < (2) * (A[i])): print("No") return 0 # Otherwise, print Yes print("Yes") return 0# Driver CodeA = [2, 5] X = 5Y = 4N = len(A)isPossibleToReach(A, N, X, Y)# This code is contributed by shivani. |
C#
// C# program for the above approachusing System;class GFG{ // Function to check if the point (X, Y)// is reachable from (0, 0) or notstatic int isPossibleToReach(int []A, int N, int X, int Y){ // Find the Euclidean Distance double distance = Math.Sqrt((X * X + Y * Y)); // Calculate the maximum distance double mx = 0; for(int i = 0; i < N; i++) { mx += (A[i]); } // Case 1. if (mx < distance) { Console.Write("NO"); return 0; } // Case 2. if ((mx - distance) < 0.000001) { Console.Write("YES"); return 0; } // Otherwise, check for the polygon // condition for each side for(int i = 0; i < N; i++) { if (distance + mx < 2 * A[i]) { Console.Write("No"); return 0; } } // Otherwise, print Yes Console.Write("Yes"); return 0;}// Driver Codestatic public void Main (){ int []A = { 2, 5 }; int X = 5, Y = 4; int N = A.Length; isPossibleToReach(A, N, X, Y);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for the above approach; // Function to check if the point (X, Y) // is reachable from (0, 0) or not function isPossibleToReach(A, N, X, Y) { // Find the Euclidean Distance let distance = Math.sqrt((X * X + Y * Y)); // Calculate the maximum distance let mx = 0; for (let i = 0; i < N; i++) { mx += A[i]; } // Case 1. if (mx < distance) { document.write("NO"); return 0; } // Case 2. if ((mx - distance) < 0.000001) { document.write("YES"); return 0; } // Otherwise, check for the polygon // condition for each side for (let i = 0; i < N; i++) { if (distance + mx < 2 * A[i]) { document.write("No"); return 0; } } // Otherwise, print Yes document.write("Yes"); return 0; } // Driver Code let A = [2, 5]; let X = 5, Y = 4; let N = A.length; isPossibleToReach(A, N, X, Y);// This code is contributed by Potta Lokesh </script> |
Output:
Yes
Time Complexity: O(N)
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!
