Track first digit during a long multiplication in c

Question

I have an array of integer element range up to 10^5, and I have to find the first element after the total multiplication.

Example:

Array : 2,4,6,7 
multiplication result: 336 and the first element is 3.

Obviously I cannot multiply the elements with the range up to 10^5.

How can I track only the first digit during multiplication?

Do you have to find the first element after multiplication or during multiplication? You are mentioning both cases in your question. — StaticBeagle, Jun 09 '16 at 02:59
After multiplication. Its my approach is to track first element during multiplication i think this is the only way we can solve this problem. — Mayur Kharche, Jun 09 '16 at 03:24
You can multiply at least 7 operands of size up to 10^5 and still fit in a __int128. And you can multiply as many as you want with [gmp](http://gmplib.org). — Nick Matteo, Jun 09 '16 at 03:27
Is it the value of the individual elements that can range up to 10^5? Or the number of elements in the array? — samgak, Jun 09 '16 at 04:46
You could add the logarithms of the numbers and look at the fractional part. It might give the wrong answer from rounding error though. — samgak, Jun 09 '16 at 05:29

score 4 · Answer 1 · edited Sep 18 '16 at 19:02

We can also find the first digit with another method.

Suppose p be the final value after multiplying all the elements.

So, we have to find

P = a[0]*a[1]*a[2]*a[3]*.......*a[n-1]

for n sized array then we can take log with base 10 on both the side after that our expression changes to

log(p) = log(a[i])+log(a[1])+log(a[2])+.....+log(a[n-1])

Now, to find the first digit we have to get the fractional part of this variable sum which can be done in this way

frac = sum - (integer)sum

and at the last step calculate the 10^frac and convert it to the integer value which is our required first digit.

This algorithm is better in comparison to time complexity.

int getFirstDigit(long a[], long n) {
      double p;

      for(int i=0;i<n;i++) {
           p = p+log10(a[i]);
      }

      double frac = p - (long)p;

      int firdig = (int)pow(10,frac);

      return firdig; 
}

sudoer · Accepted Answer · 2016-06-10T14:34:57.410

1

In c or c++ make integer data type as long double such that first digit of number is before decimal point and rest are after decimal point.

Above can be done as follows:-

long double GetFraction(int number){
    int length = (int) log(number) + 1; // this will give number of digits in given number. And log is log base 10.
    long double fraction = (long double) number / (10^(length - 1);
    return fraction;
}

Example :-

Let number = 12345

length = log(12345) + 1 = 5;
fraction = (long double) 12345 / (10^4) = 1.2345

Now for all integers in array find fraction as mention above and multiply them as follow:-

int GetFirstDigit(int arr[] , int size){
    if(size == 0)
        return 0;
    long double firstDigit = 1.0;
    for(int i = 0 ; i < size ; i++){
        firstDigit = firstDigit*GetFraction(arr[i]);
        if(firstDigit >= 10.00) // You have to shorten your number otherwise it will same as large multiplication and will overflow.
            firstDigit/=10;
    }
    return (int) firstDigit;
}

Disclaimer:- This is my approach and I don't have any formal proof about accuracy of result. But I have verified result for integer up to 10^9 and array size up to 10^5

edited Jun 10 '16 at 14:34

answered Jun 10 '16 at 04:10

sudoer

195
12

But this method can't pass all the cases i think. – Vivek Puri Jun 13 '16 at 17:52
Can you provide test case where it fails, as I don't have any formal proof so I can't gurantee its result. – sudoer Jun 13 '16 at 18:14
I have implemented the same approach provided by you but I got WA – Vivek Puri Jun 13 '16 at 18:15
So thats I am asking can you provide test case where its getting wrong. – sudoer Jun 13 '16 at 18:17
I have not found any one but i think it fails because I am getting WA. – Vivek Puri Jun 13 '16 at 18:21

Coding Ninja · Answer 3 · 2016-06-10T08:20:46.127

0

Please donot forget to note that this is just an attempt to make you understand the logic and that you need to make changes in the code as per your requirement. I strongly suggest you make this a subroutine in your program and parse the arguments to it from the main thread in your program.

#include <stdio.h>
void main()
{
  int num1, num2;
  printf("Enter ur lovely number:\n");
  scanf("%d",&num1);
  num2=num1;
 while(num2)
 {
  num2=num2/10;
  if(num2!=0)
 num1=num2; 
 }
 printf("The first digit of the lovely number is %d !! :P\n ",num1);
}

edited Jun 10 '16 at 08:20

answered Jun 09 '16 at 10:20

Coding Ninja

114
12

I mean to say the time complexity of the program is more than i required. I think you understand what i mean to say. – Mayur Kharche Jun 09 '16 at 12:05
well I do understand what you say...that is the reason I have posted the code for you !! There is no point in trying easy things when you are trying to hone your skills ! As an experienced guy it is on my part to suggest things to you, however, it is up to you what you want to follow ! :) – Coding Ninja Jun 09 '16 at 12:22
This has nothing to do with finding the first digit of a product which cannot fit in memory. – Nick Matteo Jun 09 '16 at 13:33
I am very grateful to your suggestion. I just need a direction to move forward in this problem.I already implement this algorithm but it doesn't work.Please let me know if you have any other solution for this question. – Mayur Kharche Jun 09 '16 at 14:06

score 0 · Answer 4 · answered Nov 06 '16 at 20:51

Try this approach,

Take integer as input let us say int x1, now copy this in a double let us say double x2, and suppose you have previous product as double y, initially y = 1 . now use this loop,

while(x1!<10){
    x1 = x1/10;
    x2 = x2/10; //this will make double in standard form x*10^y without 10^y part
}

ex x1 = 52, then x2 will be converted to 5.2. Now let us assume y = 3 and x is 5.2. then product now is 15.6, again reduce this to 1.56 and repeat the process. in the end you will have the only digit before the decimal as the first digit of the product of all the numbers.

Track first digit during a long multiplication in c

4 Answers4