You will be given an array A of N non-negative integers. Your task is to find the rightmost non-zero digit in the product of array elements.
Example 1:
Input:
N = 4, A = {3, 23, 30, 45}
Output:
5
Explanation:
Product of these numbers 
are 93150.Rightmost 
non-zero digit is 5.
Example 2:
Input:
N = 5, A = {1, 2, 3, 4, 5}
Output:
2
Explanation:
Product of these numbers 
are 120. Rightmost 
non-zero digit is 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function rightmostNonZeroDigit() which takes an array A and returns the rightmost non-zero digit in the product of array elements, if there is no right most non zero digit, then return -1.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3



class Solution:

    def rightmostNonZeroDigit (self, N, A):

        # code here 

        

Solutions:
class Solution:

	def rightmostNonZeroDigit(self, n, a):
		cnt5 = 0
		cnt2 = 0
		r = 1
		for i in range(n):
			if a[i] == 0:
				r = 0
				break
			while a[i] % 5 == 0:
				a[i] = a[i] // 5
				cnt5 += 1
			while a[i] % 2 == 0:
				a[i] //= 2
				cnt2 += 1
			r = r * a[i] % 10
		if r == 0:
			return -1
		k = min(cnt2, cnt5)
		cnt2 -= k
		cnt5 -= k
		while cnt5 > 0:
			r = r * 5 % 10
			cnt5 -= 1
		while cnt2 > 0:
			r = r * 2 % 10
			cnt2 -= 1
		return r


class Solution:

	def rightmostNonZeroDigit(self, n, a):
		c5 = 0
		for i in range(n):
			z = a[i]
			while z > 0 and z % 5 == 0:
				c5 += 1
				z = z // 5
			a[i] = z
		for i in range(n):
			z = a[i]
			while z > 0 and z % 2 == 0 and (c5 > 0):
				c5 -= 1
				z = z // 2
			a[i] = z
		ans = 1
		for j in a:
			ans = ans * j % 10 % 10
		if c5 != 0:
			ans = ans * 5 ** c5 % 10 % 10
		if ans == 0:
			return -1
		return ans


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		c5 = 0
		a = A
		n = N
		for i in range(n):
			while a[i] > 0 and a[i] % 5 == 0:
				a[i] //= 5
				c5 += 1
		for i in range(n):
			while c5 and a[i] > 0 and (a[i] & 1 == 0):
				a[i] >>= 1
				c5 -= 1
			ans = 1
		for i in range(n):
			ans = ans * a[i] % 10 % 10
		if c5:
			ans = ans * 5 % 10
		if ans:
			return ans
		return -1


class Solution:

	def rightmostNonZeroDigit(self, n, arr):
		count5 = 0
		count2 = 0
		rem = 1
		for i in range(n):
			if arr[i] == 0:
				rem = 0
				break
			while arr[i] % 5 == 0:
				count5 += 1
				arr[i] = arr[i] // 5
			while arr[i] % 2 == 0:
				count2 += 1
				arr[i] = arr[i] // 2
			rem = rem * arr[i] % 10
		if rem == 0:
			return -1
		k = min(count5, count2)
		count2 -= k
		count5 -= k
		while count5 > 0:
			rem = rem * 5 % 10
			count5 -= 1
		while count2 > 0:
			rem = rem * 2 % 10
			count2 -= 1
		return rem


class Solution:

	def rightmostNonZeroDigit(self, N, a):
		c5 = 0
		c2 = 0
		r = 1
		for i in range(N):
			if a[i] == 0:
				r = 0
				break
			while a[i] % 5 == 0:
				a[i] = a[i] // 5
				c5 += 1
			while a[i] % 2 == 0:
				a[i] = a[i] // 2
				c2 += 1
			r = r * a[i] % 10
		if r == 0:
			return -1
		k = min(c2, c5)
		c2 -= k
		c5 -= k
		while c5 > 0:
			r = r * 5 % 10
			c5 -= 1
		while c2 > 0:
			r = r * 2 % 10
			c2 -= 1
		return r


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		ctwo = 0
		cfive = 0
		res = 1
		for i in range(N):
			if A[i] == 0:
				return -1
			while A[i] % 5 == 0:
				A[i] = A[i] // 5
				cfive += 1
			while A[i] % 2 == 0:
				A[i] = A[i] // 2
				ctwo += 1
			res = res * A[i] % 10
		minM = min(ctwo, cfive)
		ctwo -= minM
		cfive -= minM
		while cfive > 0:
			res = res * 5 % 10
			cfive -= 1
		while ctwo > 0:
			res = res * 2 % 10
			ctwo -= 1
		return res


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		prod = 1
		cnt = 0
		for i in range(N):
			while A[i] > 0 and A[i] % 5 == 0:
				A[i] //= 5
				cnt += 1
		for i in range(N):
			while cnt > 0 and A[i] > 0 and (A[i] % 2 == 0):
				A[i] //= 2
				cnt -= 1
		for i in A:
			prod = prod * i % 10 % 10
		while cnt > 0:
			prod = prod * 5 % 10
			cnt -= 1
		if prod > 0:
			return prod
		return -1


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		l = A
		n = N
		p2 = p5 = 0
		for i in l:
			val = i
			if val == 0:
				return -1
			while val % 5 == 0:
				val //= 5
				p5 += 1
			while val % 2 == 0:
				val //= 2
				p2 += 1
		red2 = red5 = min(p2, p5)
		for i in range(0, n):
			while l[i] % 2 == 0 and red2 > 0:
				red2 -= 1
				l[i] //= 2
			while l[i] % 5 == 0 and red5 > 0:
				red5 -= 1
				l[i] //= 5
		ans = 1
		for i in l:
			i %= 10
			ans = ans * i
			ans %= 10
		return ans


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		product = 1
		count2 = 0
		count5 = 0
		for i in range(N):
			if A[i] == 0:
				return -1
			while A[i] % 2 == 0:
				count2 += 1
				A[i] //= 2
			while A[i] % 5 == 0:
				count5 += 1
				A[i] //= 5
			product *= A[i] % 10
			product %= 10
		smaller = count2 if count2 < count5 else count5
		count2 -= smaller
		count5 -= smaller
		for i in range(count2):
			product *= 2
			product %= 10
		for i in range(count5):
			product *= 5
			product %= 10
		return product


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		c5 = 0
		for i in range(N):
			while A[i] > 0 and A[i] % 5 == 0:
				A[i] = A[i] // 5
				c5 += 1
		for i in range(N):
			while c5 > 0 and A[i] and (A[i] % 2 == 0):
				A[i] = A[i] // 2
				c5 -= 1
		product = 1
		for i in range(N):
			product = product * A[i] % 10 % 10
		while c5 > 0:
			product = product * 5 % 10
			c5 -= 1
		if product > 0:
			return product
		return -1


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		c5 = 0
		for i in range(len(A)):
			while A[i] > 0 and A[i] % 5 == 0:
				A[i] = A[i] // 5
				c5 += 1
		for i in range(len(A)):
			while c5 > 0 and A[i] > 0 and (A[i] % 2 == 0):
				A[i] = A[i] // 2
				c5 -= 1
		prod = 1
		for i in range(len(A)):
			prod = prod * A[i] % 10 % 10
		while c5 > 0:
			prod = prod * 5 % 10
			c5 -= 1
		if prod > 0:
			return prod
		else:
			return -1


class Solution:

	def rightmostNonZeroDigit(self, N, A):
		count = 0
		if 0 in A:
			return -1
		res = 1
		for i in range(N):
			while A[i] > 0 and A[i] % 5 == 0:
				A[i] = A[i] // 5
				count = count + 1
		for i in range(N):
			while A[i] > 0 and count > 0 and (A[i] % 2 == 0):
				A[i] = A[i] // 2
				count = count - 1
		for i in range(N):
			res = res * (A[i] % 10) % 10
		for i in range(count):
			res = res * 5 % 10
		return res