Finding the non zero digit after mutiplying each element in array-CodePudding

Input: N = 4 arr = {3, 23, 30, 45} Output: 5 Explanation: Product of these numbers is 93150. Rightmost non-zero digit is 5.

can u solve this question in c and run this code for input i give u.enter image description here

// my code for this question
int rightmostNonZeroDigit(int N,arr[])
{
    // Write your code here.
    long int t = 1;
    for (int i = 0; i < N; i  )
    {
        t = t * arr[i];
    }
    while (t > 0)
    {
        if ((t % 10) != 0)
        {
            return (t % 10);
        }
        t = t / 10;
    }
     return -1;
}
// what changes should i make in this code

CodePudding user response：

This is actually a nice little challenge. You are multiplying (based from a short estimation on your input image) about 500 numbers with 3 digits each. The product of all these number will never fit into any standard integer type provided by C .

Suppose your variable t holds some four digit number "abcd". You can write it like

t = a * 1000   b * 100   c * 10   d

Now if you multiply t with any other number x you get

t * x = a * x * 1000   b * x * 100   c * x * 10   d * x

As you can see the last digit of t*x is only determined by d*x. All the other components have trailing zeros since they are some multiple of a power of ten. That means to get the last digit of any multiplication, you just have to multiply the two last digits of the numbers.

Now you are not interested in the last digit, but in the last non-zero digit. You will get the right result if you only ever keep the last non-zero digit in t while calculating the product of all the numbers. In your code you could do something like this:

for (int i = 0; i < N; i  ) {
    t = t * arr[i];

    // the following will remove all trailing zeros
    while ( t != 0 && t % 10 == 0 ) {
        t = t / 10;
    }
   
    // the following will remove all but the last digit
    t = t % 10;
}

This works because trailing zeros in the intermediate result will never influence anything but the number of trailing zeros in the final result. And digits before the last non-zero digit will also never contribute to the last non-zero digit in the final result.

Addition
On godbolt you can find a live example with your test input arr = {3,23,30,45}.

CodePudding user response：

The trick is to retain only the final non-zero digit on each step.

#include <iostream>
int main() {
    int arr[] = {3, 23, 30, 45};
    int n = 1;
    for (auto&& i : arr){
        if (!(n *= i)) break; // Zero in input needs special treatment
        for (; !(n % 10); n /= 10); // Remove trailing zeros
        n %= 10; // Retain single digit
    }
    std::cout << n;
}

is one way.