Find a and b for a given Logarithmic Equation
Given a number n. Find positive numbers a(0 < a <= 109) and b(0 < b <= 109) such that they satisfy the equation log2a + log3b = n. Return any possible integer array of a and b, if the equation can be satisfied otherwise return the single integer array containing -1 which means there is no such a and b exists. Solution will be accepted if |n-log2a + log3b| < 10-6.
Examples:
Input: 3
Output: [1, 27]
Explanation: log2(1) = 0 and log3(27) = 3, 0 + 3 = 3 or [4, 3], [2, 9],…also can be the possible answer.Input: 40
Output: [4194304, 387420489]
Approach: To solve the problem follow the below steps:
- If we see the a’s and b’s range it is upto 109. So, we try to loop through all possibilities using two for loops but we get the time limit exceeds. That’s why the intuition here is to reduce the search for a and b.
- So, if we do log2(109) ~ 29 and log3(109) ~ 18. Here we took the integer part.
- Therefore, if n = a + b = 29 + 18 = 47 is the maximum value.
- Here in this code, we check that if n > 47 then we return -1 to indicate that there is no such a and b exists.
- Then the nested loop explores all the possible values of a and b such that t 2i + 3j = n.
- Then the code will calculate log(2, a) + log(3,b) to check that the value is approximately n with a small epsilon.
- If the calculated value is within the epsilon range then return the result.
- If the loops are complete without finding a valid solution, the code returns [-1] to indicate that no ‘a‘ and ‘b‘ were found for the given ‘n‘.
- The use of epsilon for comparison addresses the precision limitations of floating-point calculations.
Below is the implementation of the approach.
C++
// C++ code for the above appraoch: #include <cmath> #include <iostream> using namespace std; int * checkIfPossible( int n) { // If 'n' is greater than 47, return // [-1] since it's not possible if (n > 47) { int * result = new int [1]; result[0] = -1; return result; } // Define a small value for precision double epsilon = 1e-6; // Iterate through powers of 2 (i) and // powers of 3(j) for ( int i = 0; i < 30; i++) { for ( int j = 0; j < 19; j++) { if (i + j == n) { int a = static_cast < int >( // Calculate 'a' as 2^i pow (2, i)); int b = static_cast < int >( // Calculate 'b' as 3^j pow (3, j)); // Calculate the logarithms of 'a' // and 'b' with the respective bases double val = log (a) / log (2) + log (b) / log (3); // If the absolute difference // between 'n' and 'val' is // within 'epsilon' if (std:: abs (n - val) < epsilon) { // Return 'a' and 'b' as a // two-element array int * result = new int [2]; result[0] = a; result[1] = b; return result; } } } } // If no suitable 'a' and 'b' // were found, return [-1] int * result = new int [1]; result[0] = -1; return result; } // Drivers code int main() { int n = 3; int * res = checkIfPossible(n); if (res[0] == -1) { cout << "No such a and b exists."; } else { cout << "[" << res[0] << ", " << res[1] << "]"; // Free the dynamically allocated // memory delete [] res; } return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { public static int [] checkIfPossible( int n) { // If 'n' is greater than 47, return [-1] since it's // not possible if (n > 47 ) return new int [] { - 1 }; // Define a small value for precision double epsilon = 1e- 6 ; // Iterate through powers of 2 (i) and powers of // 3(j) for ( int i = 0 ; i < 30 ; i++) { // power of 2 for ( int j = 0 ; j < 19 ; j++) { // power of 3 if (i + j == n) { int a = ( int )Math.pow( 2 , i); // Calculate 'a' as 2^i int b = ( int )Math.pow( 3 , j); // Calculate 'b' as 3^j // Calculate the logarithms of 'a' and // 'b' with the respective bases double val = log(a, 2 ) + log(b, 3 ); // If the absolute difference between // 'n' and 'val' is within 'epsilon' if (Math.abs(n - val) < epsilon) { // Return 'a' and 'b' as a // two-element array return new int [] { a, b }; } } } } // If no suitable 'a' and 'b' were found, return // [-1] return new int [] { - 1 }; } // A method to calculate the logarithm of 'a' with a // specified base public static double log( int a, int base) { return Math.log(a) / Math.log(base); } public static void main(String[] args) { int n = 3 ; int res[] = checkIfPossible(n); if (res.length == 2 ) { System.out.print("[" + res[ 0 ] + "," + res[ 1 ] + "]"); } else { System.out.print("No such a and b exists."); } } } |
Python3
import math def check_if_possible(n): # If 'n' is greater than 47, return # [-1] since it's not possible if n > 47 : return [ - 1 ] # Define a small value for precision epsilon = 1e - 6 # Iterate through powers of 2 (i) and powers of 3 (j) for i in range ( 30 ): for j in range ( 19 ): if i + j = = n: a = int (math. pow ( 2 , i)) b = int (math. pow ( 3 , j)) # Calculate the logarithms of 'a' and 'b' with the respective bases val = math.log(a, 2 ) + math.log(b, 3 ) # If the absolute difference between 'n' and 'val' is within 'epsilon' if abs (n - val) < epsilon: # Return 'a' and 'b' as a two-element list return [a, b] # If no suitable 'a' and 'b' were found, return [-1] return [ - 1 ] # Drivers code if __name__ = = "__main__" : n = 3 res = check_if_possible(n) if res[ 0 ] = = - 1 : print ( "No such a and b exists." ) else : print (f "[{res[0]}, {res[1]}]" ) |
C#
using System; class Program { static int [] CheckIfPossible( int n) { // If 'n' is greater than 47, return // [-1] since it's not possible if (n > 47) { int [] result = new int [] { -1 }; return result; } // Define a small value for precision double epsilon = 1e-6; // Iterate through powers of 2 (i) and // powers of 3(j) for ( int i = 0; i < 30; i++) { for ( int j = 0; j < 19; j++) { if (i + j == n) { int a = ( int )Math.Pow(2, i); int b = ( int )Math.Pow(3, j); // Calculate the logarithms of 'a' // and 'b' with the respective bases double val = Math.Log(a, 2) + Math.Log(b, 3); // If the absolute difference // between 'n' and 'val' is // within 'epsilon' if (Math.Abs(n - val) < epsilon) { // Return 'a' and 'b' as a // two-element array int [] result = new int [] { a, b }; return result; } } } } // If no suitable 'a' and 'b' // were found, return [-1] int [] defaultResult = new int [] { -1 }; return defaultResult; } // Driver code static void Main() { int n = 3; int [] res = CheckIfPossible(n); if (res[0] == -1) { Console.WriteLine( "No such a and b exists." ); } else { Console.WriteLine($ "[{res[0]}, {res[1]}]" ); // No need to free memory in C# as it is automatically managed by the garbage collector } } } |
Javascript
// Javascript code for the above appraoch: function checkIfPossible(n) { // If 'n' is greater than 47, return // [-1] since it's not possible if (n > 47) { return [-1]; } // Define a small value for precision const epsilon = 1e-6; // Iterate through powers of 2 (i) and // powers of 3(j) for (let i = 0; i < 30; i++) { for (let j = 0; j < 19; j++) { if (i + j === n) { const a = Math.pow(2, i); const b = Math.pow(3, j); // Calculate the logarithms of 'a' // and 'b' with the respective bases const val = Math.log(a) / Math.log(2) + Math.log(b) / Math.log(3); // If the absolute difference // between 'n' and 'val' is // within 'epsilon' if (Math.abs(n - val) < epsilon) { // Return 'a' and 'b' as a // two-element array return [a, b]; } } } } // If no suitable 'a' and 'b' // were found, return [-1] return [-1]; } // Driver code const n = 3; const res = checkIfPossible(n); if (res[0] === -1) { console.log( "No such 'a' and 'b' exist." ); } else { console.log(`[${res[0]}, ${res[1]}]`); } |
Output
[1, 27]
Time Complexity: O(19*30) = O(570) = O(1)
Auxiliary Space: O(1)
Contact Us