Last non-zero digit of nPm

Trying to solve this problem, which is basically finding the last non-zero digit of nPm. I got the answer by working with 2-s and 5-s, but here’s an easier solution by using 10 directly.

Can anyone explain why this works? How taking modulo 10^9 does not make it wrong?

    for (int n, m;
         cin >> n >> m;) {

        long long ans = 1;
        for (int i = 0; i < m; i++) {
            int x = n - i;
            ans *= x;

            while (ans % 10 == 0)
                ans /= 10;

            ans %= (int) 1e9;
        }

        cout << ans % 10 << 'n';
    }

Thanks.

Source: Windows Questions C++

LEAVE A COMMENT