PROBLEM LINK:Author: Nazarbek Altybay DIFFICULTY:Simple PREREQUISITES:basic maths PROBLEM:You are given up to $10^5$ queries. In each query, you are given a number $N < 10^9$, you have to transform $N$ to a number with maximum trailing zeroes by multiplying it with lucky numbers(any number of times). The decimal value of such a number should be minimum. A number is called lucky number if its decimal representations contain only lucky digits $4$ and $7$. QUICK EXPLANATION:Keep setting $N$ = $N * 4$(since $4$ is lucky) until $y > x$ where $x$ and $y$ are powers of $2$ and $5$ respectively, in prime factorization of $N$. EXPLANATION:================
Now, let's see how using above observations we arrive to our solution. Say, prime factorization of $N$ is of form $2^x * 5^y ...$. We know lucky numbers cannot provide more $5$'s, so our only way to increase number of trailing zeroes is to add more $2$'s if $y > x$. If $y \le x$, we cannot increase trailing zeroes in any way by multiplying with Lucky numbers. Also, since our aim is to get smallest possible number with most number of trailing zeroes, we will try to multiply those Lucky numbers which contribute $2$'s only, so we multiply with $4$ until $x < y$. Following pseudo code summarizes the solution: scan N; //cnt 2 is power of 2, cnt5 is power of 5 cnt2 = cnt5 = 0; temp = N; while ((temp % 2) == 0) { cnt2++; temp /= 2; } temp = N; while ((temp % 5) == 0) { cnt5++; temp /= 5; } ans = N; while (cnt5 > cnt2) { ans *= 4; cnt2 += 2; //since we multiply with a 4 ie. 2 to the power 2 } print ans; COMPLEXITY:For each query, the complexity can be said as $O(\textrm{max}(x, y))$, where $x$ and $y$ are powers of $2$ in prime factorization of $N$. So complexity is, $O(\textrm{log} N)$ per query. AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 18 Jun '15, 05:36

Answer is hidden as author is suspended. Click here to view.
answered 13 Jul '15, 16:07

what if I keep multiplying with 4 and keep checking the maximum trailing zero till now.. won't that be helpful ?. I tried this approach but got only 30 marks.. can anyone help what I'm missing here ? ex. 125
answered 13 Jul '15, 15:47

http://www.codechef.com/viewsolution/7338180 This solution is giving wrong answer for n=1 and a[i]=500,but still it got 30 points.This clearly shows that the test cases are weak.Please look into this serious matter. answered 13 Jul '15, 15:49

why the above approach fails for last two cases ?? all are long long int. answered 13 Jul '15, 19:15

I got 30 pts.I have used the logic of difference of power and using the logic that "since 5 raised to power 11 is 48828125 and 5 to the power 12 will be greater than 10*9 so limiting temp(difference of power) till 11" http://www.codechef.com/viewsolution/7448043 somebody help. answered 13 Jul '15, 21:47

Another way to view the problem is to work out what number can be multiplied by 4 or 7 and an extra zero is the last digit of the answer. So: 1 x 4 = 4 The only number that can be multiplied by 4 and gives an extra zero is 5. 10 x 4 doesn't give us an extra zero as 10 already has one zero. If you do the same for 7 then you'll find nothing multiplied by 7 gives an extra zero so it can be completely ignored. Now that we know 5 x 4 is the only way to get an extra zero we can just see if the final non zero digit is a 5. If it is then multiply the number by 4 and repeat until this fails. The reason this needs to be repeated is because of test cases like below where after multiplying by 4 the new value still has a 5 as the last non zero digit:
125 * 4 = 500 Pseudo code: for each test { read in value while last_non_zero_digit_is_five(value) { value = value * 4 } print value } My solution can be found here http://www.codechef.com/viewsolution/7359571 unfortunately the function name isn't the most accurate. Hopefully this helps someone understand the problem. answered 15 Jul '15, 15:07

@arcticblue  I have implemented in the same way as you did..it worked.. answered 16 Jul '15, 12:11

EASIEST MATH PROBLEM. We can get zeroes only by 5x4 or 10xnumber(any). Check if given no can produce zeroes(i.e last digit should be 5 or 5 followed by zeroes)Ex: 45,1250,etc . If yes, then, after multipling with 4 if the digit before trailing zeros is 5 again, we can produce another zeroes. After this we can't get any more zeroes. NO NEED OF 7 here ONLY 4 is REQ FOR ANS. THEY GAVE 7 JUST TO TRICK US. OTHERWISE we cant get any zeroes. EX: n=125, 125x4=500, 500x4=2000. No more zeroes. Thus 2000 is ANS. SIMPLE LOGIC. JOB DONE. https://www.codechef.com/viewsolution/7391022 answered 16 Jul '15, 23:42
