Smallest string without any multiplication sign that represents the product of two given numbers
Given two numbers A and B, the task is to print the string of the smallest possible length which evaluates to the product of the two given numbers i.e., A*B, without using the multiplication sign.
Any perfect power of 2 can be expressed in the form of a left-shift operator.
For Example:
N = 2 = 1<<1 = β<<1β
N = 4 = 1<<2 = β<<2β
Using the above idea, any number can be expressed using a left-shift operator instead of a multiplication sign.
For Example:
N = 24 = 6*4 = 6(1<<2) = β6<<2β
Examples:
Input: A = 6, B = 10
Output: 6<<3+6<<1
Explanation:
The product of the 2 numbers = 6 Γ 10 = 60.
The above-given expression evaluates to 6 Γ (2 Γ 2 Γ 2) + 6 Γ 2 = 60.
The string β10<<2+10<<1β also evaluates to 60.
But β6<<3+6<<1β is the required output as its length is smaller.Input: A = 5, B = 5
Output: 5<<2+5
Explanation:
The product of the 2 numbers = 5 Γ 5 = 25.
The above-given expression evaluates to 5 Γ (2 Γ 2) + 5 = 25.
Approach: The idea is to use Left Shift Operator to find the product. Below are the steps:
- Represent B as powers of 2.
Let B = 2k1 + 2k2 + β¦ + 2kn, where k1 > k2 > .. > kn
- Therefore, the product of A and B can be written as
A * B = A * (2k1 + 2k2+ β¦ + 2kn )
- Use the β<<β (left shift operator) to multiply a number by any power of two.
- Thus A x B = A << k1 + A << k2 + β¦ + A << kn
- To find ki we use the log() function and continue the process with the remainder B β 2ki until the remainder becomes 0 or the log of the remainder becomes zero.
- Similarly, represent A*B = B<< k1 + B<< k2 + β¦ + B<< kn by representing A as the power of 2.
- Compare the two representations and print the string with a smaller length.
Below is the implementation of the above approach:
C++
// C++ program for // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the string // which evaluates to the // product of A and B string len( long A, long B) { // Stores the result string res = "" ; long Log = 0; do { // 2 ^ log <= B && // 2 ^ (log + 1) > B Log = ( long )( log (B) / log (2)); // Update res to // res+=A X 2^log if (Log != 0) { res = res + to_string(A) + "<<" + to_string(Log); } else { // Update res to // res+=A X 2^0 res += A; break ; } // Find the remainder B = B - ( long ) pow (2, Log); // If remainder is // not equal to 0 if (B != 0) { res += "+" ; } else break ; } while (Log != 0); // Return the // resultant string return res; } // Function to find the minimum // length representation of A*B void minimumString( long A, long B) { // Find representation of form // A << k1 + A << k2 + ... + A << kn string res1 = len(A, B); // Find representation of form // B << k1 + B << k2 + ... + B << kn string res2 = len(B, A); // Compare the length of // the representations if (res1.length() > res2.length()) { cout << res2 << endl; } else { cout << res1 << endl; } } // Driver code int main() { // Product A X B long A = 6; long B = 10; // Function Call minimumString(A, B); return 0; } // This code is contributed by divyeshrabadiya07 |
Java
// Java program for the above approach class GFG { // Function to find the string // which evaluates to the // product of A and B public static String len( long A, long B) { // Stores the result String res = "" ; long log = 0 ; do { // 2 ^ log <= B && // 2 ^ (log + 1) > B log = ( long )(Math.log(B) / Math.log( 2 )); // Update res to // res+=A X 2^log if (log != 0 ) { res += A + "<<" + log; } else { // Update res to res+=A X 2^0 res += A; break ; } // Find the remainder B = B - ( long )Math.pow( 2 , log); // If remainder is not equal // to 0 if (B != 0 ) { res += "+" ; } else break ; } while (log != 0 ); // Return the resultant string return res; } // Function to find the minimum // length representation of A*B public static void minimumString( long A, long B) { // Find representation of form // A << k1 + A << k2 + ... + A << kn String res1 = len(A, B); // Find representation of form // B << k1 + B << k2 + ... + B << kn String res2 = len(B, A); // Compare the length of // the representations if (res1.length() > res2.length()) { System.out.println(res2); } else { System.out.println(res1); } } // Driver Code public static void main(String args[]) { // Product A X B long A = 6 ; long B = 10 ; // Function Call minimumString(A, B); } } |
Python3
# Python3 program for the above approach from math import log # Function to find the string # which evaluates to the # product of A and B def lenn(A, B): # Stores the result res = "" logg = 0 while True : # 2 ^ logg <= B && # 2 ^ (logg + 1) > B logg = log(B) / / log( 2 ) # Update res to # res+=A X 2^logg if (logg ! = 0 ): res + = ( str (A) + "<<" + str ( int (logg))) else : # Update res to res+=A X 2^0 res + = A break # Find the remainder B = B - pow ( 2 , logg) # If remainder is not equal # to 0 if (B ! = 0 ): res + = "+" else : break if logg = = 0 : break # Return the resultant string return res # Function to find the minimum # length representation of A*B def minimumString(A, B): # Find representation of form # A << k1 + A << k2 + ... + A << kn res1 = lenn(A, B) # Find representation of form # B << k1 + B << k2 + ... + B << kn res2 = lenn(B, A) # Compare the length of # the representations if ( len (res1) > len (res2)): print (res2) else : print (res1) # Driver Code if __name__ = = '__main__' : # Product A X B A = 6 B = 10 # Function call minimumString(A, B) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the string // which evaluates to the // product of A and B public static string len( long A, long B) { // Stores the result string res = "" ; long log = 0; do { // 2 ^ log <= B && // 2 ^ (log + 1) > B log = ( long )(Math.Log(B) / Math.Log(2)); // Update res to // res+=A X 2^log if (log != 0) { res += A + "<<" + log; } else { // Update res to res+=A X 2^0 res += A; break ; } // Find the remainder B = B - ( long )Math.Pow(2, log); // If remainder is not equal // to 0 if (B != 0) { res += "+" ; } else break ; } while (log != 0); // Return the resultant string return res; } // Function to find the minimum // length representation of A*B public static void minimumString( long A, long B) { // Find representation of form // A << k1 + A << k2 + ... + A << kn string res1 = len(A, B); // Find representation of form // B << k1 + B << k2 + ... + B << kn string res2 = len(B, A); // Compare the length of // the representations if (res1.Length > res2.Length) { Console.WriteLine(res2); } else { Console.WriteLine(res1); } } // Driver Code public static void Main() { // Product A X B long A = 6; long B = 10; // Function call minimumString(A, B); } } // This code is contributed by code_hunt |
Javascript
<script> // Javascript program for // the above approach // Function to find the string // which evaluates to the // product of A and B function len(A, B) { // Stores the result let res = "" ; let Log = 0; do { // 2 ^ log <= B && // 2 ^ (log + 1) > B Log = Math.floor(Math.log(B) / Math.log(2)); // Update res to // res+=A X 2^log if (Log != 0) { res = res + String(A) + "<<" + String(Log); } else { // Update res to // res+=A X 2^0 res += A; break ; } // Find the remainder B = B - Math.pow(2, Log); // If remainder is // not equal to 0 if (B != 0) { res += "+" ; } else break ; } while (Log != 0); // Return the // resultant string return res; } // Function to find the minimum // length representation of A*B function minimumString(A, B) { // Find representation of form // A << k1 + A << k2 + ... + A << kn let res1 = len(A, B); // Find representation of form // B << k1 + B << k2 + ... + B << kn let res2 = len(B, A); // Compare the length of // the representations if (res1.length > res2.length) { document.write(res2 + "<br>" ); } else { document.write(res1 + "<br>" ); } } // Driver code // Product A X B let A = 6; let B = 10; // Function Call minimumString(A, B); // This code is contributed by gfgking </script> |
6<<3+6<<1
Time Complexity: O(log N)
Auxiliary Space: O(1)