×

# LCKYST - Editorial

Author: Nazarbek Altybay
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

Simple

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:

================
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.

# AUTHOR'S, TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

19.8k350498541

 0 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 125 * 4 = 500 125 * 16 = 2000 (ans) 125 * 64 = 8000 125 * 256 = 32000 125 * 1024 = 128000 125 * 4096 = 512000 125 * 16384 = 2048000 answered 13 Jul '15, 15:47 3●3 accept rate: 0% Did you check for overflows? (13 Jul '15, 15:51) ketanhwr6★ http://www.codechef.com/viewsolution/7445160 (13 Jul '15, 15:54)
 0 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 3★akshayv3 157●8 accept rate: 4%
 0 if (cnt5 and temp%10!=0) { multiple = (cnt5 / 2)+cnt5%2; ans = temp*pow(4, multiple); } else ans = temp;  why the above approach fails for last two cases ?? all are long long int. answered 13 Jul '15, 19:15 2★bajaj6 39●1●3●5 accept rate: 0%
 0 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 1 accept rate: 0%
 0 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 }  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 81●2 accept rate: 18%
 0 @arcticblue - I have implemented in the same way as you did..it worked.. answered 16 Jul '15, 12:11 2★pari205 1 accept rate: 0%
 0 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 13●1●1●2 accept rate: 0%
 0 @gaming30 initialize vector as vector A(N+1) or vector A(100001)....hope it helps answered 19 Jul '15, 16:21 5★apptica 949●2●10 accept rate: 17%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,220
×1,191
×141
×3

question asked: 18 Jun '15, 05:36

question was seen: 3,811 times

last updated: 26 Aug '15, 15:26