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:
================ Observations
The most basic observation here is that trailing zeroes are nothing but powers of 10. So, if a number has prime factorization of form 2^x * 5^y ..., the number of trailing zeroes is \textrm{min}(x, y) because for one trailing zero we need one 2 and one 5.
Let’s see what kind of prime factors Lucky Numbers have. We only have interest in prime factors 2 and 5. For any number with 5 as one of the prime factor, it should have a 5 or 0 as the last digit. So no lucky number has 5 as prime factor. Lucky numbers can have 2 as prime factor when the number ends in digit 4.
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.
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 ?
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.
i got only 30 points. used the same approach as mentioned here.
my code-> CodeChef: Practical coding for everyone.
instead of checking while(num5 > num2) i calculate the difference between num5 and num2 num5 -= num2. if that is positive and even multiply all of them with 2’s(coz they’ll couple to form a 4) else multiply the extra 5 with 4 . this didnt pass the last two test cases and got 30 points. anything wrong in the approach ?
EDIT: silly mistake . had to take long long . >_<
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.
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
2 x 4 = 8
3 x 4 = 12
4 x 4 = 16
5 x 4 = 20
6 x 4 = 24
7 x 4 = 28
8 x 4 = 32
9 x 4 = 36
10 x 4 = 40
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
125 * 4 * 4 = 2000
Pseudo code:
for each test {
read in value
while last_non_zero_digit_is_five(value) {
value = value * 4
}
print value
}
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