We are given two numbers A and B, we need to write a program to determine if A and B can be reached starting from (1, 1) following the given steps. Start from (1, 1) and at every step choose a random number K and multiply K to any one of the two numbers obtained in the previous step and K2 to the other number.
Examples:
Input: A = 3, B = 9
Output: yes
Explanation: Starting from A = 1 and B = 1.
We choose k=3 and multiply 3 with the first number to get A=3 and multiply k2=9 to the second-number to get B=9.Input: A = 60, B = 450
Output: yes
Explanation : Starting from A = 1 and B = 1,
Step 1: multiply k=3 and k2 to get 3 and 9
Step 2: Multiply k=5 and k2 = 25 to get to 15 and 225
Step 3: Multiply k2=4 and k=2 to get to A=60 and B=450
The idea to solve this problem is to observe closely that at each step we are multiplying k and k2 to the numbers. So if A and B can be reached, it will have k^3 at every step as factors in A*B. In simple words, if the number A*B is a perfect cube and it divides A and B both, only then the number can be reached starting from 1 and 1 by performing given steps.
Below is the implementation of above idea:
C++
// CPP program to determine if // A and B can be reached starting // from 1, 1 following the given steps. #include <bits/stdc++.h> using namespace std; // function to check is it is possible to reach // A and B starting from 1 and 1 bool possibleToReach(int a, int b) { // find the cuberoot of the number int c = cbrt(a * b); // divide the number by cuberoot int re1 = a / c; int re2 = b / c; // if it is a perfect cuberoot and divides a and b if ((re1 * re1 * re2 == a) && (re2 * re2 * re1 == b)) return true; else return false; } int main() { int A = 60, B = 450; if (possibleToReach(A, B)) cout << "yes"; else cout << "no"; return 0; } |
Java
// Java program to determine if // A and B can be reached starting // from 1, 1 following the given // steps. class GFG { // function to check is it is // possible to reach A and B // starting from 1 and 1 static boolean possibleToReach(int a, int b) { // find the cuberoot of the number int c = (int)Math.cbrt(a * b); // divide the number by cuberoot int re1 = a / c; int re2 = b / c; // if it is a perfect cuberoot and // divides a and b if ((re1 * re1 * re2 == a) && (re2 * re2 * re1 == b)) return true; else return false; } // Driver code public static void main(String[] args) { int A = 60, B = 450; if (possibleToReach(A, B)) System.out.println("yes"); else System.out.println("no"); } } // This code is contributed by // Smitha Dinesh Semwal |
Python 3
# Python 3 program to determine if # A and B can be reached starting # from 1, 1 following the given steps. import numpy as np # function to check is it is possible to # reach A and B starting from 1 and 1 def possibleToReach(a, b): # find the cuberoot of the number c = np.cbrt(a * b) # divide the number by cuberoot re1 = a // c re2 = b // c # if it is a perfect cuberoot and # divides a and b if ((re1 * re1 * re2 == a) and (re2 * re2 * re1 == b)): return True else: return False # Driver Code if __name__ == "__main__": A = 60 B = 450 if (possibleToReach(A, B)): print("yes") else: print("no") # This code is contributed by ita_c |
C#
// C# program to determine if // A and B can be reached starting // from 1, 1 following the given // steps. using System; public class GFG{ // function to check is it is // possible to reach A and B // starting from 1 and 1 public static bool possibleToReach(int a, int b) { // find the cuberoot of the number int c = (int)Math.Pow(a * b, (double) 1 / 3); // divide the number by cuberoot int re1 = a / c; int re2 = b / c; // if it is a perfect cuberoot // and divides a and b if ((re1 * re1 * re2 == a) && (re2 * re2 * re1 == b)) return true; else return false; } // Driver Code static public void Main (String []args) { int A = 60, B = 450; if (possibleToReach(A, B)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by Ajit. |
PHP
<?php // PHP program to determine if // A and B can be reached starting // from 1, 1 following the given steps. // function to check is it is // possible to reach A and B // starting from 1 and 1 function possibleToReach($a, $b) { // find the cuberoot // of the number $c =($a * $b); // divide the number // by cuberoot $re1 = $a / $c; $re2 = $b / $c; // if it is a perfect cuberoot // and divides a and b if (($re1 * $re1 * $re2 == $a) && ($re2 * $re2 * $re1 == $b)) return 1; else return -1; } // Driver Code $A = 60; $B = 450; if (possibleToReach($A, $B)) echo "yes"; else echo "no"; // This code is contributed by aj_36 ?> |
Javascript
<script> // JavaScript program to determine if // A and B can be reached starting // from 1, 1 following the given steps. // function to check is it is // possible to reach A and B // starting from 1 and 1 function possibleToReach(a, b) { // find the cuberoot of the number let c = Math.cbrt(a * b); // divide the number by cuberoot let re1 = a / c; let re2 = b / c; // if it is a perfect cuberoot and // divides a and b if ((re1 * re1 * re2 == a) && (re2 * re2 * re1 == b)) return true; else return false; } // Driver code let A = 60, B = 450; if (possibleToReach(A, B)) document.write("Yes"); else document.write("No"); // This code is contributed by splevel62. </script> |
yes
Time complexity: O(log(A*B)) for given A and B, as it is using cbrt function
Auxiliary space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
