Given an array arr[] of N non-negative integers. The task is to find the rightmost non-zero digit in the product of array elements.
Examples:
Input: arr[] = {3, 5, 6, 90909009}
Output: 7
Input: arr[] = {7, 42, 11, 64}
Output: 6
Result of multiplication is 206976
So the rightmost digit is 6
Approach:
- The question is too simple if you know basic maths. It is given that you have to find the rightmost positive digit. Now a digit is made multiple of 10 if there are 2 and 5. They produce a number with last digit 0.
- Now what we can do is divide each array element into its shortest divisible form by 5 and increase count of such occurrences.
- Now divide each array element into its shortest divisible form by 2 and decrease count of such occurrences. This way we are not considering the multiplication of 2 and a 5 in our multiplication.
- Set the multiplier value as either 1 or 5 in case count of 5 is not 0 after above two loops.
- Multiply each array variable now and store just last digit by taking remainder by 10
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the rightmost non-zero// digit in the multiplication// of the array elementsint rightmostNonZero(int a[], int n){ // To store the count of times 5 can // divide the array elements int c5 = 0; // Divide the array elements by 5 // as much as possible for (int i = 0; i < n; i++) { while (a[i] > 0 && a[i] % 5 == 0) { a[i] /= 5; // increase count of 5 c5++; } } // Divide the array elements by // 2 as much as possible for (int i = 0; i < n; i++) { while (c5 && a[i] > 0 && !(a[i] & 1)) { a[i] >>= 1; // Decrease count of 5, because a '2' and // a '5' makes a number with last digit '0' c5--; } } long long ans = 1; for (int i = 0; i < n; i++) { ans = (ans * a[i] % 10) % 10; } // If c5 is more than the multiplier // should be taken as 5 if (c5) ans = (ans * 5) % 10; if (ans) return ans; return -1;}// Driver codeint main(){ int a[] = { 7, 42, 11, 64 }; int n = sizeof(a) / sizeof(a[0]); cout << rightmostNonZero(a, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function to return the rightmost non-zero// digit in the multiplication// of the array elementsstatic int rightmostNonZero(int a[], int n){ // To store the count of times 5 can // divide the array elements int c5 = 0; // Divide the array elements by 5 // as much as possible for (int i = 0; i < n; i++) { while (a[i] > 0 && a[i] % 5 == 0) { a[i] /= 5; // increase count of 5 c5++; } } // Divide the array elements by // 2 as much as possible for (int i = 0; i < n; i++) { while (c5 != 0 && a[i] > 0 && (a[i] & 1) == 0) { a[i] >>= 1; // Decrease count of 5, because a '2' and // a '5' makes a number with last digit '0' c5--; } } int ans = 1; for (int i = 0; i < n; i++) { ans = (ans * a[i] % 10) % 10; } // If c5 is more than the multiplier // should be taken as 5 if (c5 != 0) ans = (ans * 5) % 10; if (ans != 0) return ans; return -1;}// Driver codepublic static void main(String args[]){ int a[] = { 7, 42, 11, 64 }; int n = a.length; System.out.println(rightmostNonZero(a, n));}}// This code is contributed by// Surendra_Gangwar |
Python3
# Python3 implementation of the approach# Function to return the rightmost non-zero# digit in the multiplication# of the array elementsdef rightmostNonZero(a, n): # To store the count of times 5 can # divide the array elements c5 = 0 # Divide the array elements by 5 # as much as possible for i in range(n): while (a[i] > 0 and a[i] % 5 == 0): a[i] //= 5 # increase count of 5 c5 += 1 # Divide the array elements by # 2 as much as possible for i in range(n): while (c5 and a[i] > 0 and (a[i] & 1) == 0): a[i] >>= 1 # Decrease count of 5, because a '2' and # a '5' makes a number with last digit '0' c5 -= 1 ans = 1 for i in range(n): ans = (ans * a[i] % 10) % 10 # If c5 is more than the multiplier # should be taken as 5 if (c5): ans = (ans * 5) % 10 if (ans): return ans return -1# Driver codea = [7, 42, 11, 64]n = len(a)print(rightmostNonZero(a, n))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the rightmost non-zero// digit in the multiplication// of the array elementsstatic int rightmostNonZero(int[] a, int n){ // To store the count of times 5 can // divide the array elements int c5 = 0; // Divide the array elements by 5 // as much as possible for (int i = 0; i < n; i++) { while (a[i] > 0 && a[i] % 5 == 0) { a[i] /= 5; // increase count of 5 c5++; } } // Divide the array elements by // 2 as much as possible for (int i = 0; i < n; i++) { while (c5 != 0 && a[i] > 0 && (a[i] & 1) == 0) { a[i] >>= 1; // Decrease count of 5, because a '2' and // a '5' makes a number with last digit '0' c5--; } } int ans = 1; for (int i = 0; i < n; i++) { ans = (ans * a[i] % 10) % 10; } // If c5 is more than the multiplier // should be taken as 5 if (c5 != 0) ans = (ans * 5) % 10; if (ans != 0) return ans; return -1;}// Driver codepublic static void Main(){ int[] a = { 7, 42, 11, 64 }; int n = a.Length; Console.WriteLine(rightmostNonZero(a, n));}}// This code is contributed by// Code_@Mech |
Javascript
<script>// Javascript implementation of the approach // Function to return the rightmost non-zero // digit in the multiplication // of the array elements function rightmostNonZero(a , n) { // To store the count of times 5 can // divide the array elements var c5 = 0; // Divide the array elements by 5 // as much as possible for (i = 0; i < n; i++) { while (a[i] > 0 && a[i] % 5 == 0) { a[i] /= 5; // increase count of 5 c5++; } } // Divide the array elements by // 2 as much as possible for (i = 0; i < n; i++) { while (c5 != 0 && a[i] > 0 && (a[i] & 1) == 0) { a[i] >>= 1; // Decrease count of 5, // because a '2' and // a '5' makes a number with // last digit '0' c5--; } } var ans = 1; for (i = 0; i < n; i++) { ans = (ans * a[i] % 10) % 10; } // If c5 is more than the multiplier // should be taken as 5 if (c5 != 0) ans = (ans * 5) % 10; if (ans != 0) return ans; return -1; } // Driver code var a = [ 7, 42, 11, 64 ]; var n = a.length; document.write(rightmostNonZero(a, n));// This code contributed by aashish1995 </script> |
Output:
6
Time Complexity: O(N)
Here, N is the number of elements in the array. The rightmostNonZero() function iterates over the array once and takes constant time for each iteration.
Space Complexity: O(1)
No extra space is required.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
