Finding the non zero digit after mutiplying each element in array

Question

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

Answer 1

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

Important Edit
As @MohammedfaizKhan pointed out there are cases where the above code fails. For example if we take the numbers arr = {15,2}. The code from above yields 1 because it truncates the 1 in 15 before multiplying it with 2. If we call D the operation that tuncates a number to the first non zero digit, the above program could be written like:

	code from above produces
step one	t = D(1 * 15) = 5
step two	t = D(5 * 2 ) = 1

The correct result would be 3. Apparently we cannot remove all leading digits. We could try to increase the number of leading nonzero digits that are kept in each step. For example in the code above, we could use t = t % 100 instead of t = t % 10. There is however a counter example for each number of digits we are trying to keep:

The numbers 2^n and 5^n don't have trailing zeros because they are no multiple of ten because a multiple of 10 must have 2 and 5 in its prime factorization. Their product 2^n * 5^n = (2*5)^n = 10^n however has exactly n trailing zeros.

In conclusion we should keep as many leading nonzero digits as we can fit into our data type. For an 64bit unsigned int this would be for example 19 digits. However we also must not overflow while doing the multiplication with the array elements. Because your array elements are all no longer than 3 digits, we should be safe if we keep the leading 15 digits or something like that.

So in conclusion the following program should do the correct thing:

unsigned long long int t = 1;
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 15 digits
    t = t % 1000000000000000;
}

Answer 2

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.