Increase A by atmost B times so that zeroes at the end of A are maximized
Given 2 integers A and B, the task is to increase A by at most B times such that zeroes at the end of A are maximized and print that final value of A. If 2 or more numbers have the same number of trailing zeroes, print the largest one.
Examples:
Input: A = 6, B = 11
Output: 60
Explanation: The answer would be 60, when we increase A by 10 times. Note that to get 2 zeroes at the end we need to increase A by at least 50 times. But we cannot do so as B = 11.Input: A = 10050, B = 12345
Output: 120600000
Approach: To solve the problem follow the below idea.
- Let’s first count the degree of occurrence of 2 and 5 in the number A, denoted by Count2 and Count5 respectively. We can represent A as A = 2^Count2 * 5^Count5 * d, where d is not divisible by either 2 or 5.
- Let the answer be A*k. k ≤ B.
- We can increase Count2 or Count5 to get the A with the most trailing zeroes possible while spending the least possible k. For example, if Count2 < Count5, we can increase Count2 by 1 and multiply k by 2 as long as k*2 ≤ m and Count2 != Count5.
- We have Count2 = Count5, or k*5 > B, or k*2 > B. For the case Count2 = Count5, we multiply k by 10 as long as k*10 ≤ B.
- At this point, we have k*10 > B, so we find x = floor(B/k), which is a number between 1 and 9 (inclusive).
- Finally, we multiply k by x to get the desired answer, which is A*k.
Below are the steps for the above approach:
- Initialize a variable A0 to store the original value of A.
- Initialize two counters Count2 and Count5 to 0 to count the number of factors of 2 and 5 in A.
- Run a loop to check if A is divisible by 2, divide A by 2, and increment Count2.
- Similarly run a loop to check if A is divisible by 5, divide A by 5, and increment Count5.
- Initialize a variable k = 1.
- Run a loop to check whether Count2 is less than Count5 and whether k times 2 is less than or equal to B. If so, Count2 is incremented, and k is multiplied by 2.
- Similarly, run a loop to check whether Count5 is less than Count2 and whether k times 5 is less than or equal to B. If so, Count5 is incremented, and k is multiplied by 5.
- Run a loop to check whether k times 10 is less than or equal to B. If so, k is multiplied by 10.
- Check if k = 1, that means A0 times B is the optimal answer, otherwise, k is multiplied by B divided by k, to ensure that a result is a round number between 1 and 9.
- The final result is A0 * k.
Following is the code based on the above approach :
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define int long long // Function to increase A by at most B // times such that zeroes at the end // of A are maximized int maximizeZeroes( int A, int B) { // Save the original value of A int A0 = A; // Count the number of 2s and 5s in A int Count2 = 0, Count5 = 0; while (A > 0 && A % 2 == 0) { A /= 2; Count2++; } while (A > 0 && A % 5 == 0) { A /= 5; Count5++; } // Choose k to maximize the number // of trailing zeroes in A // (i.e. answer is A.k) int k = 1; // Increase cnt2 or cnt5 to get the // most round number possible, while // spending the least possible k. while (Count2 < Count5 && k * 2 <= B) { Count2++; k *= 2; } while (Count5 < Count2 && k * 5 <= B) { Count5++; k *= 5; } // If we can add more trailing zeroes, // keep multiplying by 10. while (k * 10 <= B) { k *= 10; } // If k becomes 1, that means A0*B // is the optimal answer if (k == 1) { return (A0 * B); } // To maximize the output, as B/K // would be between 1 and 9 else { k *= B / k; return (A0 * k); } } // Driver code int32_t main() { int A = 10050, B = 12345; int ans = maximizeZeroes(A, B); // Function call cout << ans << endl; return 0; } |
Java
// Java code for the above approach class GFG { // Function to increase A by at most B // times such that zeroes at the end // of A are maximized static int maximizeZeroes( int A, int B) { // Save the original value of A int A0 = A; // Count the number of 2s and 5s in A int Count2 = 0 , Count5 = 0 ; while (A > 0 && A % 2 == 0 ) { A /= 2 ; Count2++; } while (A > 0 && A % 5 == 0 ) { A /= 5 ; Count5++; } // Choose k to maximize the number // of trailing zeroes in A // (i.e. answer is A.k) int k = 1 ; // Increase cnt2 or cnt5 to get the // most round number possible, while // spending the least possible k. while (Count2 < Count5 && k * 2 <= B) { Count2++; k *= 2 ; } while (Count5 < Count2 && k * 5 <= B) { Count5++; k *= 5 ; } // If we can add more trailing zeroes, // keep multiplying by 10. while (k * 10 <= B) { k *= 10 ; } // If k becomes 1, that means A0*B // is the optimal answer if (k == 1 ) { return (A0 * B); } // To maximize the output, as B/K // would be between 1 and 9 else { k *= B / k; return (A0 * k); } } // Driver code public static void main(String[] args) { int A = 10050 , B = 12345 ; int ans = maximizeZeroes(A, B); // Function call System.out.println(ans); } } // This code is contributed by Tapesh(tapeshdua420) |
Python3
# Function to increase A by at most B # times such that zeroes at the end # of A are maximized def maximizeZeroes(A: int , B: int ) - > int : # Save the original value of A A0 = A # Count the number of 2s and 5s in A Count2 = 0 Count5 = 0 while A > 0 and A % 2 = = 0 : A / / = 2 Count2 + = 1 while A > 0 and A % 5 = = 0 : A / / = 5 Count5 + = 1 # Choose k to maximize the number # of trailing zeroes in A # (i.e. answer is A.k) k = 1 # Increase cnt2 or cnt5 to get the # most round number possible, while # spending the least possible k. while Count2 < Count5 and k * 2 < = B: Count2 + = 1 k * = 2 while Count5 < Count2 and k * 5 < = B: Count5 + = 1 k * = 5 # If we can add more trailing zeroes, # keep multiplying by 10. while k * 10 < = B: k * = 10 # If k becomes 1, that means A0*B # is the optimal answer if k = = 1 : return A0 * B # To maximize the output, as B/K # would be between 1 and 9 else : k * = B / / k return A0 * k # Driver code if __name__ = = '__main__' : A = 10050 B = 12345 ans = maximizeZeroes(A, B) # Function call print (ans) |
C#
using System; class GFG { // Function to increase A by at most B // times such that zeroes at the end // of A are maximized static long MaximizeZeroes( long A, long B) { // Save the original value of A long A0 = A; // Count the number of 2s and 5s in A long Count2 = 0, Count5 = 0; while (A > 0 && A % 2 == 0) { A /= 2; Count2++; } while (A > 0 && A % 5 == 0) { A /= 5; Count5++; } // Choose k to maximize the number // of trailing zeroes in A // (i.e. answer is A.k) long k = 1; // Increase Count2 or Count5 to get the // most round number possible, while // spending the least possible k. while (Count2 < Count5 && k * 2 <= B) { Count2++; k *= 2; } while (Count5 < Count2 && k * 5 <= B) { Count5++; k *= 5; } // If we can add more trailing zeroes, // keep multiplying by 10. while (k * 10 <= B) { k *= 10; } // If k becomes 1, that means A0*B // is the optimal answer if (k == 1) { return (A0 * B); } // To maximize the output, as B/K // would be between 1 and 9 else { k *= B / k; return (A0 * k); } } // Driver code static void Main( string [] args) { long A = 10050, B = 12345; long ans = MaximizeZeroes(A, B); // Function call Console.WriteLine(ans); } } |
Javascript
// Function to increase A by at most B // times such that zeroes at the end // of A are maximized function maximizeZeroes(A, B) { // Save the original value of A let A0 = A; // Count the number of 2s and 5s in A let Count2 = 0, Count5 = 0; while (A > 0 && A % 2 === 0) { A /= 2; Count2++; } while (A > 0 && A % 5 === 0) { A /= 5; Count5++; } // Choose k to maximize the number // of trailing zeroes in A // (i.e. answer is A.k) let k = 1; // Increase cnt2 or cnt5 to get the // most round number possible, while // spending the least possible k. while (Count2 < Count5 && k * 2 <= B) { Count2++; k *= 2; } while (Count5 < Count2 && k * 5 <= B) { Count5++; k *= 5; } // If we can add more trailing zeroes, // keep multiplying by 10 while (k * 10 <= B) { k *= 10; } // If k becomes 1, that means A0*B // is the optimal answer if (k === 1) { return (A0 * B); } // To maximize the output, as B/K // would be between 1 and 9 else { k *= Math.floor(B / k); return (A0 * k); } } // Driver code let A = 10050, B = 12345; let ans = maximizeZeroes(A, B); console.log(ans); |
Output
120600000
Time Complexity: O(log(A) +log(B))
Auxiliary Space: O(1)