1

Given an array A, I have to multiply all the elements of array. Since the numbers can go upto 10^9 , I have to find the trailing zeroes of the product. I did the following : 

int ans= 0; // to count no of trailing zeroes 
 for(long int i =0; i<n ; i++) // n can be very large(upto 10^5)
 { 
    long long int p=1;
   p=p*a[i];
  while (p2℅10 ==0)
   { ans++;
     p=p/10;
    }
 }

Function to calculate number of 2's is as follows. I replaced 2 with 5 to calculate nunber of 5's. 

Int nm2(long long a)
{
  Int b=0;
  while(a℅2==0){
    a=a/2;
     b++;
    }
  return b;
  }

Int p2=0,p5=0;
For(long long i=L;i<R;i++)
 { 
   p2 += nm2(a[i]);
   p5 += nm5 (a[i]);
  }
 Int ans += min(p2,p5); // storing no of zeroes every time I multiply elements of array from Index L to Index R of array a[].

How can I improve it ? Or is there any other different way to calculate it with faster efficiency. Please help me out.

Sam_Buck
  • 25
  • 5
  • This looks like the most efficient possible way to me. Shifts are faster than divides, but I don't see way to exploit that here. I think you nailed it, personally, and I look forward to seeing what other people say. Nice question! – allen1 Oct 12 '16 at 20:11
  • 1
    FWIW, if you're *really* concerned with efficiency, http://stackoverflow.com/questions/12356442/binary-divisibility-by-10 ; also see here: http://stackoverflow.com/questions/7070346/c-best-way-to-get-integer-division-and-remainder BTW, is that indentation the same you use in your actual code? –  Oct 12 '16 at 20:22
  • @vaxquis Won't this method be long? Converting a long long to binary and then those bit manipulations and then calculating no of zeroes. ? I'm no good but it seems a lengthy way. – Sam_Buck Oct 12 '16 at 20:25
  • 2
    The code has serious problems. First of all, if any of your a[i] is 0, your code will enter an infinite loop. Secondly, multiplying so many integers guarantees to overflow. I'd say before seeking advice, you should make an effort to improve the qualify of the question. – Donghui Zhang Oct 12 '16 at 20:25
  • 1
    std::div will do the modulo and the division at once – zacaj Oct 12 '16 at 20:25
  • @DonghuiZhang 0 – Sam_Buck Oct 12 '16 at 20:27
  • @zacaj I looked up the div function just now but I don't think it's faster or if it is then please correct me. I don't mean any offense. – Sam_Buck Oct 12 '16 at 20:31
  • Sam, result will still overflow, unless you have a lot of values in array that are equal to one, since n can be enormous. Consider if every value is 2, and n=10^5. Result would be 2^(10^5), which is 10^5 bit number, will definitely blow away a long long int. – Joel Lee Oct 12 '16 at 20:35
  • @Joellee I know and that's why I am checking every time for 10's and removing them. I don't know how to do it otherwise. – Sam_Buck Oct 12 '16 at 20:48
  • Problem is, there may be no trailing zeros in the result, and you won't remove anything. See my answer if all you want is the number of trailing zeros. If you also want the actual result, you will have to take a completely different approach to representing it. But I don't think that is what you are after. – Joel Lee Oct 12 '16 at 20:52
  • What are L & R? Also, why `ans +=...`? What are you adding to here? This should be `ans =...`. – Joel Lee Oct 12 '16 at 22:04
  • L is lower bound of array for eg 0 and R is upper bound for the array . I am given some range to do this multiplication. And `ans +=` because I want to add number of zeroes whenever i multiply the elements of array. I may multiply my array multiple times and I need to keep on adding the nunber of trailing zeroes. – Sam_Buck Oct 12 '16 at 22:14
  • I feel like something is missing from your problem statement. Your original problem: calculate the number of trailing zeros in the product of all elements in an array. If you need to do this multiple times, put it in a function and call it whenever you need to get the product. of elements in an array. – Joel Lee Oct 12 '16 at 22:42
  • Yeah, I have did like that exceot that instead of function it's choice based. Whenever I have to run this query it switches to this case and performs the action. – Sam_Buck Oct 13 '16 at 13:10
  • Can you give an example where my answer (essentially what you have shown in last part of your question) gives wrong result? The number theory is solid. – Joel Lee Oct 13 '16 at 18:29
  • @JoelLee I don't know exactly the case where it goes wrong. I had done exactly the way you are proposing now . But I think it goes wrong somewhere between when I replace the array elements by `(i+1)*N where N can be as large as 10^9 and I is the index of element`. This is a different query to be run on the array multiple times. Even though I update the nunber of 2's and 5's after updating each element. I am getting a wrong answer. – Sam_Buck Oct 15 '16 at 06:30
  • Are you still working on this? I haven't been on StackOverflow for a while. – Joel Lee Oct 19 '16 at 18:24
  • @JoelLee yeah I was. But had to stop since I hit a dead end. Plus due to my exams I didn't get much time to fiddle with it. – Sam_Buck Oct 21 '16 at 16:44
  • So are you still interested in solving? – Joel Lee Oct 21 '16 at 18:50
  • @JoelLee yeah, of course I am. I was thinking of applying segment tree but I don't know if it will solve the problem. – Sam_Buck Oct 23 '16 at 15:24
  • Sam, I'm looking at your comment: "But I think it goes wrong somewhere between when I replace the array elements by (i+1)*N where N can be as large as 10^9 and I is the index of element." Does this mean you are using as test data an array where `A[i] = (i+1)*N`. If so, are you getting incorrect result, and how do you know it is incorrect? – Joel Lee Oct 24 '16 at 01:23
  • @JoelLee yeah but this is a query which can be performed very large times and I think this is the problem. Suppose I want to replace all elements (10^5) and suppose I'm doing this query (10^9) times. It will be very time consuming. So I have to reduce time on this query. – Sam_Buck Oct 25 '16 at 07:52
  • Is the goal here to (a) compute a huge product efficiently (PROD( a[i], i=1..N), or (b) to figure out the number of trailing zeros? Or both? It isn't clear from your problem statement. It sounds like maybe what you are really trying to do is (a), but you are using (b) to help you do that faster. If you are really trying to solve (a), I would use a completely different approach. – Joel Lee Oct 26 '16 at 20:22
  • @JoelLee I have to do both of them many times. So that's why it takes so much time. – Sam_Buck Oct 27 '16 at 18:08

2 Answers2

2

This is more about number theory than it is about details of division. Here's what I would do

int fives = 0;
int twos = 0;

for (int i=0; i<n; i++) {
    fives += countFives(a[i]);
    twos += countTwos(a[i]);
}

int trailingZeros = fives > twos ?  twos : fives;

The two functions countTwos and countFives are pretty straightforward, and would count the number of factors of 2 and 5, respectively, of a given input value.

The line that calculates the number of trailing zeros is based on that fact that each trailing zero must be due to exactly one factor of 2 and one factor of 5. If you have more 2's than 5's they will not contribute any additional zeros, and vice versa. So the number of trailing zeros is equal to the smaller of the two counts.

Joel Lee
  • 3,656
  • 1
  • 18
  • 21
  • I exactly did this in the beginning. But for long numbers the answer came wrong. Though some elements are updated in array before this final multiplication but I did update number of 2's and 5's every time a update was made in the array. That's why I had to do division but with this I get time limit exceeded. – Sam_Buck Oct 12 '16 at 20:52
  • Can you give me an example where my algorithm gives incorrect result. I'm confident it is correct. Not meaning to be arrogant, but each trailing zero has to be due to a factor of 10 = 2*5, so number of trailing zeros is equal to the number of 2 factors that "match" a 5 factor. – Joel Lee Oct 12 '16 at 21:00
  • Can you post your algorithm that counts factors of 2's and 5's?, so I can see what you were doing? – Joel Lee Oct 12 '16 at 21:03
  • I have included it in the original post. Please rectify if there are mistakes or if it could be made efficiently. – Sam_Buck Oct 12 '16 at 21:18
  • 2
    @samthornton You are counting twos correctly. The question is how do you _use the result_. Please show the complete code. – user58697 Oct 12 '16 at 21:21
  • 1
    @user58697 is correct about counting factors of 2 (or 5). Must be some other issue. – Joel Lee Oct 12 '16 at 21:22
  • @user58697 I first calculate the number of 2 and nunber of 5 and then take the min of them and add it to ans – Sam_Buck Oct 12 '16 at 21:49
  • Wait, you are taking the min of the two's and five's counts INSIDE your loop? If that is what you are doing, it is incorrect. Consider the sequence: `3, 2, 5`. Product is 30, so one trailing zero. If you are doing min inside the loop, you will get none. – Joel Lee Oct 12 '16 at 21:55
  • @JoelLee no I'm not taking min inside loop. I'm just adding the number of 2's and 5's using the loop and then min of them. And L and R are just the bounds on that loop for eg L=0 and R=size of array -1 – Sam_Buck Oct 12 '16 at 22:12
0

isn't it what scientific notation is for when you deal with really large number?

No idea why you need trailing zeros, but std::scientific might help you with expression of really large numbers.

user6590212
  • 1
  • 1
  • No , I just need the nunber of trailing zeroes. – Sam_Buck Oct 13 '16 at 13:07
  • Convert the number into a string and count starting from the end of it. or print the result into a file. and then count them when you have it stored in a file. – user6590212 Oct 13 '16 at 21:22
  • the answer will have more than 18 number of digits so storing this big answer each time and doing this multiple times will be very hectic and slow. So that's why I am trying to use number of 2's and 5's. – Sam_Buck Oct 16 '16 at 07:22