Given an array of positive numbers, the task is to find the number of possible contiguous subarrays having product less than a given number k. 
Example 1:
Input : 
n = 4, k = 10
a[] = {1, 2, 3, 4}
Output : 
7
Explanation:
The contiguous subarrays are {1}, {2}, {3}, {4} 
{1, 2}, {1, 2, 3} and {2, 3} whose count is 7.
Example 2:
Input:
n = 7 , k = 100
a[] = {1, 9, 2, 8, 6, 4, 3}
Output:
16
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countSubArrayProductLessThanK() which takes the array a[], its size n and an integer k as inputs and returns the count of required subarrays.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1<=n<=10^{5}
1<=k<=10^{15}
1<=a[i]<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
    def countSubArrayProductLessThanK(self, a, n, k):
        #Code here
    
    
    
    

Solutions:
class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		low = 0
		ans = 0
		mul = 1
		for i in range(n):
			mul *= a[i]
			while mul >= k and low <= i:
				mul //= a[low]
				low += 1
			if mul < k:
				c = i - low + 1
				ans += c * (c + 1) // 2 - c * (c - 1) // 2
		return ans


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		(end, strt, count) = (0, 0, 0)
		prod = 1
		while end < n:
			prod *= a[end]
			while prod >= k and strt < n:
				prod = prod // a[strt]
				strt += 1
			if prod < k:
				count += end - strt + 1
			end += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		product = 1
		count = 0
		x = 0
		total = 0
		for i in range(n):
			product *= a[i]
			count += 1
			while product >= k and x <= i:
				product /= a[x]
				x += 1
				count -= 1
			total += count
		return total


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		x = 0
		pro = 1
		cnt = 0
		s = 0
		x1 = 0
		for i in range(n):
			pro *= a[i]
			if pro < k:
				x += 1
			else:
				cnt += (x + x1) * (x + x1 + 1) // 2 - x1 * (x1 + 1) // 2
				x = 0
				while pro >= k and s < i:
					pro //= a[s]
					s += 1
				if pro < k:
					cnt += i - s + 1
					x1 = i - s + 1
		if x:
			cnt += (x + x1) * (x + x1 + 1) // 2 - x1 * (x1 + 1) // 2
			x = 0
		return cnt


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		n = len(a)
		p = 1
		res = 0
		start = 0
		end = 0
		while end < n:
			p = p * a[end]
			while start < end and p >= k:
				p = int(p // a[start])
				start += 1
			if p < k:
				l = end - start + 1
				res += l
			end += 1
		return res


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		i = 0
		j = 0
		product = 1
		count = 0
		while j < n:
			product *= a[j]
			while i <= j and product >= k:
				product /= a[i]
				i += 1
			count += j - i + 1
			j += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		start = 0
		end = 0
		p = 1
		c = 0
		if k == 1:
			return 0
		while start < n and end < n:
			p = p * a[end]
			if p < k:
				c += end - start + 1
				end += 1
			else:
				while p >= k:
					p = p // a[start]
					start += 1
					if p < k:
						if start > end:
							end += 1
						else:
							c += end - start + 1
							end += 1
		return c


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		count = 0
		left = 0
		product = 1
		for right in range(n):
			product *= a[right]
			while product >= k and left <= right:
				product /= a[left]
				left += 1
			count += right - left + 1
		return count


def product(arr):
	pro = 1
	for i in arr:
		pro = pro * i
	return pro

class Solution:

	def countSubArrayProductLessThanK(self, arr, n, k):
		(left, right) = (0, 0)
		n = len(arr)
		product = 1
		count = 0
		while right < n:
			product *= arr[right]
			while product >= k and left <= right:
				product /= arr[left]
				left += 1
			count += right - left + 1
			right += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		if k <= 1:
			return 0
		prod = 1
		res = 0
		l = 0
		r = 0
		while r < n:
			prod *= a[r]
			while prod >= k:
				prod /= a[l]
				l += 1
			res += r - l + 1
			r += 1
		return res


import numpy as np

class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		if k <= 1:
			return 0
		res = 0
		cp = 1
		left = 0
		for i in range(n):
			cp = cp * a[i]
			while cp >= k:
				cp = cp / a[left]
				left += 1
			res += i - left + 1
		return res


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		c = 0
		p = 1
		(i, j) = (0, 0)
		if k == 1:
			return 0
		while j < n:
			p *= a[j]
			while p >= k:
				p //= a[i]
				i += 1
			c += j - i + 1
			j += 1
		return c


from collections import deque

class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		count = 0
		windowstart = 0
		window = 1
		for windowend in range(len(a)):
			window *= a[windowend]
			while window >= k and windowstart < len(a):
				window = window // a[windowstart]
				windowstart += 1
			count += windowend - windowstart + 1
		return count if count > 0 else 0


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		left = 0
		ans = 0
		prod = 1
		for right in range(0, n):
			prod = prod * a[right]
			while left <= right and prod >= k:
				prod = prod // a[left]
				left += 1
			ans += right - left + 1
		return ans


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		l = 0
		r = 0
		mul = 1
		c = 0
		while r < n:
			mul = mul * a[r]
			while mul > k and l < r:
				mul = mul // a[l]
				l = l + 1
			if mul < k:
				c = c + 1 + r - l
			r = r + 1
		return c


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		p = 1
		count = 0
		(i, j) = (0, 0)
		while j < n:
			p = p * a[j]
			if p < k:
				count += j - i + 1
			else:
				while p >= k and i <= j:
					p = p // a[i]
					i += 1
				if p < k:
					count += j - i + 1
			j += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		c = 0
		pc = 0
		m = 1
		(i, j) = (0, 0)
		while i < n and j < n:
			if m * a[j] < k:
				pc += 1
				c += pc
				m *= a[j]
				j += 1
			elif i < j:
				m //= a[i]
				i += 1
				pc -= 1
			elif j <= i:
				j += 1
				i += 1
		return c


class Solution:

	def countSubArrayProductLessThanK(self, nums, n, k):
		(left, prod, count) = (0, 1, 0)
		for right in range(len(nums)):
			prod = prod * nums[right]
			while prod >= k and left <= right:
				prod = prod / nums[left]
				left += 1
			count += right - left + 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		(s, e) = (0, 0)
		p = 1
		res = 0
		for e in range(n):
			p = p * a[e]
			while s < e and p >= k:
				p = p / a[s]
				s = s + 1
			if p < k:
				length = e - s + 1
				res = res + length
		return res


class Solution:

	def countSubArrayProductLessThanK(self, arr, n, k):
		n = len(arr)
		start = 0
		end = 0
		count = 0
		prod = 1
		while end < n:
			prod *= arr[end]
			while prod >= k and start <= end:
				prod /= arr[start]
				start += 1
			count += end - start + 1
			end += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		(pdt, j, ans) = (1, 0, 0)
		if k == 1:
			return 0
		for i in range(n):
			pdt *= a[i]
			if pdt < k:
				ans += i - j + 1
			else:
				while pdt >= k:
					pdt /= a[j]
					j += 1
				ans += i - j + 1
		return ans


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		st = 0
		en = 0
		cnt = 0
		p = 1
		while en < n:
			p = p * a[en]
			while p >= k and st < en:
				p = p / a[st]
				st += 1
			if p < k:
				cnt += en - st + 1
			en += 1
		return cnt


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		i = 0
		j = 0
		mul = 1
		ans = 0
		while i < n:
			mul = a[i] * mul
			if mul < k:
				ans += i - j + 1
			else:
				while j <= i and mul >= k:
					mul = mul // a[j]
					j += 1
				ans += i - j + 1
			i += 1
		return ans


from functools import reduce

class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		(end, strt, count) = (0, 0, 0)
		prod = 1
		while end < n:
			prod *= a[end]
			while prod >= k and strt < n:
				prod = prod // a[strt]
				strt += 1
			if prod < k:
				count += end - strt + 1
			end += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		product_till_now = 1
		sub_count = 0
		ptr = 0
		total = 0
		for i in range(n):
			product_till_now *= a[i]
			sub_count += 1
			while product_till_now >= k and ptr <= i:
				product_till_now /= a[ptr]
				ptr += 1
				sub_count -= 1
			total += sub_count
		return total


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		left = 0
		right = 0
		prod = 1
		count = 0
		while right < n:
			prod *= a[right]
			while left <= right and prod >= k:
				prod /= a[left]
				left += 1
			count += right - left + 1
			right += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		if k == 1:
			return 0
		ans = 0
		si = ei = 0
		d = {}
		temp = 1
		for i in range(n):
			temp = temp * a[i]
			d[i] = temp
		while ei < n:
			if si == 0:
				product = d[ei]
			else:
				product = d[ei] / d[si - 1]
			if product < k:
				ans += ei - si + 1
				ei += 1
			else:
				while not product < k:
					si += 1
					product = d[ei] / d[si - 1]
				ans += ei - si + 1
				ei += 1
		return ans


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		start = end = res = 0
		product = 1
		for end in range(n):
			product *= a[end]
			while start < end and product >= k:
				product /= a[start]
				start += 1
			if product < k:
				length = end - start + 1
				res += length
		return res


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		i = 0
		j = 0
		pr = 1
		ans = 0
		while j < n:
			pr *= a[j]
			if pr < k:
				ans += j - i + 1
			while i < n and pr >= k:
				pr = pr // a[i]
				i += 1
				if pr < k:
					temp = j - i + 1
					ans += temp
					break
			j += 1
		return ans


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		if k == 0:
			return 0
		(start, prod, cnt) = (0, 1, 0)
		for end in range(len(a)):
			while start <= end and prod * a[end] >= k:
				prod = prod / a[start]
				start += 1
			prod = 1 if start > end else prod * a[end]
			cnt = cnt if start > end else cnt + (end - start + 1)
		return cnt


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		(l, r) = (0, 0)
		pro = 1
		count = 0
		while r < n:
			pro *= a[r]
			if pro < k:
				count += r - l + 1
				r += 1
			elif l == r:
				l += 1
				r += 1
				pro = 1
			else:
				pro //= a[l] * a[r]
				l += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, arr, n, k):
		start = 0
		count = 0
		p = 1
		for end in range(n):
			p *= arr[end]
			while p >= k and start < n:
				p = p / arr[start]
				start += 1
			if start <= end:
				count += end - start + 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		left = 0
		result = 0
		prod = 1
		for (right, val) in enumerate(a):
			prod *= val
			while left < right and prod >= k:
				prod = prod // a[left]
				left += 1
			if prod < k:
				result += right - left + 1
		return result


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		last = 0
		first = 0
		count = 0
		pd = 1
		while last < n:
			pd *= a[last]
			while pd >= k and first < n:
				pd = pd // a[first]
				first += 1
			if pd < k:
				count += last - first + 1
			last += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		l = 0
		count = 0
		mul = 1
		for r in range(len(a)):
			mul = mul * a[r]
			while l < r and mul >= k:
				mul = mul / a[l]
				l = l + 1
			if mul < k:
				length = r - l + 1
				count += length
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		(low, high) = (0, 0)
		count = 0
		product = 1
		for high in range(n):
			product *= a[high]
			while low < high and product >= k:
				product /= a[low]
				low += 1
			if product < k:
				length = high - low + 1
				count += length
		return count


from functools import reduce

class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		(i, j, ans, s) = (0, 0, 0, 1)
		while j < n:
			s *= a[j]
			if s < k:
				ans += j - i + 1
				j += 1
			else:
				while s >= k and i < n:
					s = s // a[i]
					i += 1
				if s < k:
					ans += j - i + 1
				j += 1
		return ans


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		left = 0
		right = 0
		count = 0
		running = 1
		while right < len(a):
			running *= a[right]
			while left <= right and running >= k:
				running //= a[left]
				left += 1
			count += right - left + 1
			right += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		s = e = r = 0
		prod = 1
		for e in range(n):
			prod *= a[e]
			while s < e and prod >= k:
				prod /= a[s]
				s += 1
			if prod < k:
				len = e - s + 1
				r += len
		return r


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		count = 0
		product = 1
		left = 0
		right = 0
		while right < n:
			product *= a[right]
			while product >= k and left <= right:
				product /= a[left]
				left += 1
			if product < k:
				count += right - left + 1
			right += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		product_so_far = 1
		min_i = 0
		subarray = 0
		total = 0
		for i in range(len(a)):
			product_so_far *= a[i]
			subarray += 1
			while product_so_far >= k and min_i <= i:
				product_so_far /= a[min_i]
				min_i += 1
				subarray -= 1
			if product_so_far < k:
				total += subarray
		return total


class Solution:

	def countSubArrayProductLessThanK(self, arr, n, k):
		l = 0
		r = 0
		prod = 1
		count = 0
		for r in range(n):
			prod = prod * arr[r]
			while l < r and prod > k:
				prod = prod / arr[l]
				l += 1
			if prod < k:
				ans = r - l + 1
				count += ans
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		l = 0
		res = 0
		product = 1
		nums = a
		for r in range(len(nums)):
			product *= nums[r]
			while product >= k and l <= r:
				product /= nums[l]
				l += 1
			res += r - l + 1
		return res


class Solution:

	def countSubArrayProductLessThanK(self, arr, n, k):
		product = 1
		cnt = 0
		start = end = 0
		while end <= n - 1:
			product *= arr[end]
			while product >= k and start <= end:
				product /= arr[start]
				start += 1
			cnt += end - start + 1
			end += 1
		return cnt


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		till = 1
		c = 0
		ptr = 0
		total = 0
		for i in range(n):
			till *= a[i]
			c += 1
			while till >= k and ptr <= i:
				till /= a[ptr]
				c -= 1
				ptr += 1
			total += c
		return total


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		count = 0
		total = 1
		(i, j) = (0, 0)
		remElem = 0
		while i < n:
			total *= a[i]
			if total < k:
				count += 1 + remElem * 1
				remElem += 1
			elif total >= k:
				temp = total
				while j < i:
					temp = int(temp / a[j])
					remElem -= 1
					if temp < k:
						count += 1 + remElem * 1
						total = temp
						remElem += 1
						j += 1
						break
					j += 1
				if j >= i and temp >= k:
					j += 1
					total = 1
					remElem = 0
			i += 1
		return count


class Solution:

	def countSubArrayProductLessThanK(self, a, n, k):
		left = right = res = 0
		prod = 1
		while right < n:
			prod *= a[right]
			while left < n and prod >= k:
				prod /= a[left]
				left += 1
			if prod < k:
				res += right - left + 1
			right += 1
		return res