Given an array with n numbers. The task is to print number of consecutive zero’s at the end after multiplying all the n number.
Examples :
Input : arr[] = {100, 10}
Output : 3
Explanation : 100 x 10 = 1000,
3 zero's at the end.
Input : arr[] = {100, 10, 5, 25, 35, 14}
Output : 4
Explanation :
100 x 10 x 5 x 25 x 35 x 14 = 61250000,
4 zero's at the end
Naive Approach :
First multiple all the number and save into the string(because if the multiplicative number is big as 2^64 then it give wrong, so store every multiple in string) and then count the number of zero’s.
Efficient approach :
First count the 2’s factor of n numbers and then count the 5’s factor of all n number then print the smallest one.
For Example –
n_number's | 2's factor | 5's factor
100 | 2 | 2
10 | 1 | 1
5 | 0 | 1
25 | 0 | 2
35 | 0 | 1
14 | 1 | 0
Total | 4 | 7
we can take a minimum so there number of
zero's is 4
Below is the implementation of above approach :
C++
// CPP program to find the number of consecutive zero// at the end after multiplying n numbers#include<iostream>using namespace std;// Function to count two's factorint two_factor(int n) { // Count number of 2s present in n int twocount = 0; while (n % 2 == 0) { twocount++; n = n / 2; } return twocount;}// Function to count five's factorint five_factor(int n) { int fivecount = 0; while (n % 5 == 0) { fivecount++; n = n / 5; } return fivecount;}// Function to count number of zerosint find_con_zero(int arr[], int n){ int twocount = 0; int fivecount = 0; for (int i = 0; i < n; i++) { // Count the two's factor of n number twocount += two_factor(arr[i]); // Count the five's factor of n number fivecount += five_factor(arr[i]); } // Return the minimum if (twocount < fivecount) return twocount; else return fivecount;}// Driver Codeint main(){ int arr[] = { 100, 10, 5, 25, 35, 14 }; int n = 6; cout << find_con_zero(arr, n);} |
Java
// Java program to find the number // of consecutive zero at the end// after multiplying n numberspublic class GfG{ // Function to count two's factor static int two_factor(int n) { // Count number of 2s // present in n int twocount = 0; while (n % 2 == 0) { twocount++; n = n / 2; } return twocount; } // Function to count five's // factor static int five_factor(int n) { int fivecount = 0; while (n % 5 == 0) { fivecount++; n = n / 5; } return fivecount; } // Function to count number of zeros static int find_con_zero(int arr[], int n) { int twocount = 0; int fivecount = 0; for (int i = 0; i < n; i++) { // Count the two's factor // of n number twocount += two_factor(arr[i]); // Count the five's factor // of n number fivecount += five_factor(arr[i]); } // Return the minimum if (twocount < fivecount) return twocount; else return fivecount; } // driver function public static void main(String s[]) { int arr[] = { 100, 10, 5, 25, 35, 14 }; int n = 6; System.out.println(find_con_zero(arr, n)); }}// This code is contributed by Gitanjali |
Python3
# Python3 code to find the number of consecutive zero# at the end after multiplying n numbers# Function to count two's factordef two_factor( n ): # Count number of 2s present in n twocount = 0 while n % 2 == 0: twocount+=1 n =int( n / 2) return twocount # Function to count five's factordef five_factor( n ): fivecount = 0 while n % 5 == 0: fivecount+=1 n = int(n / 5) return fivecount# Function to count number of zerosdef find_con_zero( arr, n ): twocount = 0 fivecount = 0 for i in range(n): # Count the two's factor of n number twocount += two_factor(arr[i]) # Count the five's factor of n number fivecount += five_factor(arr[i]) # Return the minimum if twocount < fivecount: return twocount else: return fivecount# Driver Codearr = [ 100, 10, 5, 25, 35, 14 ]n = 6print(find_con_zero(arr, n))# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to find the number // of consecutive zero at the end// after multiplying n numbersusing System;public class GfG { // Function to count two's factor static int two_factor(int n) { // Count number of 2s // present in n int twocount = 0; while (n % 2 == 0) { twocount++; n = n / 2; } return twocount; } // Function to count five's // factor static int five_factor(int n) { int fivecount = 0; while (n % 5 == 0) { fivecount++; n = n / 5; } return fivecount; } // Function to count number of zeros static int find_con_zero(int []arr, int n) { int twocount = 0; int fivecount = 0; for (int i = 0; i < n; i++) { // Count the two's factor // of n number twocount += two_factor(arr[i]); // Count the five's factor // of n number fivecount += five_factor(arr[i]); } // Return the minimum if (twocount < fivecount) return twocount; else return fivecount; } // driver function public static void Main() { int []arr = { 100, 10, 5, 25, 35, 14 }; int n = 6; Console.WriteLine(find_con_zero(arr, n)); }}// This code is contributed by vt_m. |
Javascript
<script>// JavaScript program to find the number // of consecutive zero at the end// after multiplying n numbers // Function to count two's factor function two_factor(n) { // Count number of 2s // present in n let twocount = 0; while (n % 2 == 0) { twocount++; n = n / 2; } return twocount; } // Function to count five's // factor function five_factor(n) { let fivecount = 0; while (n % 5 == 0) { fivecount++; n = n / 5; } return fivecount; } // Function to count number of zeros function find_con_zero(arr, n) { let twocount = 0; let fivecount = 0; for (let i = 0; i < n; i++) { // Count the two's factor // of n number twocount += two_factor(arr[i]); // Count the five's factor // of n number fivecount += five_factor(arr[i]); } // Return the minimum if (twocount < fivecount) return twocount; else return fivecount; } // Driver code let arr = [ 100, 10, 5, 25, 35, 14 ]; let n = 6; document.write(find_con_zero(arr, n)); // This code is contributed by code_hunt.</script> |
PHP
<?php// PHP program to find the number // of consecutive zero at the end // after multiplying n numbers// Function to count two's factorfunction two_factor($n) { // Count number of // 2s present in n $twocount = 0; while ($n % 2 == 0) { $twocount++; $n = (int)($n / 2); } return $twocount;}// Function to count // five's factorfunction five_factor($n) { $fivecount = 0; while ($n % 5 == 0) { $fivecount++; $n = (int)($n / 5); } return $fivecount;}// Function to count// number of zerosfunction find_con_zero($arr, $n){ $twocount = 0; $fivecount = 0; for ($i = 0; $i < $n; $i++) { // Count the two's // factor of n number $twocount += two_factor($arr[$i]); // Count the five's // factor of n number $fivecount += five_factor($arr[$i]); } // Return the minimum if ($twocount < $fivecount) return $twocount; else return $fivecount;}// Driver Code$arr= array(100, 10, 5, 25, 35, 14);$n = 6;echo find_con_zero($arr, $n);// This code is contributed by mits?> |
Output :
4
Approach#2: Using for and while
Multiply all the numbers and count the number of trailing zeros.
Algorithm
1. Initialize a variable “prod” to 1.
2. Traverse the given array and for each number:
a. Multiply it with “prod”.
3. Count the number of trailing zeros in “prod”.
4. Return the count.
C++
// c++ code addition #include <iostream>#include <vector>using namespace std;// count zeros function int count_zeros(vector<int> arr) { // finding product of all elements in the array. int prod = 1; for (int num : arr) { prod *= num; } // find count of trailing zeros. int count = 0; while (prod % 10 == 0) { count++; prod /= 10; } return count;}// Driver code int main() { vector<int> arr = { 100, 10, 5, 25, 35, 14 }; cout << count_zeros(arr) << endl; return 0;}// The code is contributed by Anjali goel. |
Java
// Java Code import java.io.*;class GFG { // count zeros function static int count_zeros(int[] arr) { // finding product of all elements in the array. int prod = 1; for (int num : arr) { prod *= num; } // find count of trailing zeros. int count = 0; while (prod % 10 == 0) { count++; prod /= 10; } return count; } public static void main(String[] args) { int[] arr = { 100, 10, 5, 25, 35, 14 }; System.out.println(count_zeros(arr)); }} |
Python3
def count_zeros(arr): prod = 1 for num in arr: prod *= num count = 0 while prod % 10 == 0: count += 1 prod //= 10 return countarr = [ 100, 10, 5, 25, 35, 14 ]print(count_zeros(arr)) |
C#
using System;class GFG{ // Count zeros function static int CountZeros(int[] arr) { // Finding the product of all elements in the array. int prod = 1; foreach (int num in arr) { prod *= num; } // Find the count of trailing zeros. int count = 0; while (prod % 10 == 0) { count++; prod /= 10; } return count; } public static void Main(string[] args) { int[] arr = { 100, 10, 5, 25, 35, 14 }; Console.WriteLine(CountZeros(arr)); }} |
Javascript
// JS code addition // count zeros function function count_zeros(arr) { // finding product of all elements in the array. let prod = 1; for (let num of arr) { prod *= num; } // find count of trailing zeros. let count = 0; while (prod % 10 == 0) { count++; prod = Math.floor(prod/10); } return count;}// Driver code let arr = [ 100, 10, 5, 25, 35, 14 ];console.log(count_zeros(arr)); |
Output
4
Time Complexity: O(N*log_10(max_num)) where N is the number of elements in the array and max_num is the maximum element in the array.
Auxiliary Space: O(1).
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!
