You are not logged in. Please login at www.codechef.com to post your questions!

×

LCKYST - Editorial

PROBLEM LINK:

Practice
Contest

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

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:

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

setter
tester

This question is marked "community wiki".

asked 18 Jun '15, 05:36

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

wikified 15 Jul '15, 13:30

admin's gravatar image

0★admin ♦♦
19.8k350498541


Answer is hidden as author is suspended. Click here to view.

answered 13 Jul '15, 16:07

sarvagya3943's gravatar image

4★sarvagya3943
(suspended)
accept rate: 36%

edited 26 Aug '15, 15:26

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

link

answered 13 Jul '15, 15:47

cereal_killer's gravatar image

1★cereal_killer
33
accept rate: 0%

Did you check for overflows?

(13 Jul '15, 15:51) ketanhwr6★

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.

link

answered 13 Jul '15, 15:49

akshayv3's gravatar image

3★akshayv3
1578
accept rate: 4%

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.

link

answered 13 Jul '15, 19:15

bajaj6's gravatar image

2★bajaj6
39135
accept rate: 0%

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

link

answered 13 Jul '15, 21:47

tejasvi96's gravatar image

2★tejasvi96
1
accept rate: 0%

edited 13 Jul '15, 21:48

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.

link

answered 15 Jul '15, 15:07

arcticblue's gravatar image

4★arcticblue
812
accept rate: 18%

@arcticblue - I have implemented in the same way as you did..it worked..

link

answered 16 Jul '15, 12:11

pari205's gravatar image

2★pari205
1
accept rate: 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

link

answered 16 Jul '15, 23:42

avidcoder's gravatar image

3★avidcoder
13112
accept rate: 0%

edited 16 Jul '15, 23:51

@gaming30 initialize vector as vector <int> A(N+1) or vector <int> A(100001)....hope it helps

link

answered 19 Jul '15, 16:21

apptica's gravatar image

5★apptica
949210
accept rate: 17%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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