Write a function to find number of subarrays with product less than K

1.	Write a function to find number of subarrays with product less than K
Answer» Input: arr = [1, 6, 2, 3, 2, 1], k = 12 Output: 11 int numSubarrayProductLessThanK(vector<int>& nums, int k) { int ans=0; int pdt=1; int left=0,right=0; while(right<=nums.size()-1){ pdt=nums[right]; while(pdt>=k and left<nums.size()){ pdt/=nums[left]; left++; } if(right-left>=0) ans+=right-left+1;//since on adding a new element new subarrays formed is r-i+1; right++; } return ans; } Time Complexity:* O(n) Space Complexity: O(1)

Answer»

Input: arr = [1, 6, 2, 3, 2, 1], k = 12

Output: 11

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int ans=0;
int pdt=1;
int left=0,right=0;
while(right<=nums.size()-1){

pdt*=nums[right];
while(pdt>=k and left<nums.size()){
pdt/=nums[left];
left++;

}
if(right-left>=0)
ans+=right-left+1;//since on adding a new element new subarrays formed is r-i+1;
right++;

}
return ans;
}

Time Complexity: O(n)

Space Complexity: O(1)

Discussion

No Comment Found

Related InterviewSolutions

What is topological sorting in a graph?
Given an m x n 2D grid map of '1’s which represents land and '0’s that represents water return the number of islands (surrounded by water and formed by connecting adjacent lands in 2 directions - vertically or horizontally).
Print Left view of any binary trees.
Write Java code to count number of nodes in a binary tree
Write a recursive function to calculate the height of a binary tree in Java.
Write a function to determine whether duplicate elements in a given array are within a given distance of each other.
Implement LRU(Least Recently Used) Cache
Write a function to find number of structurally unique binary trees are possible
Write a function to connect nodes at the same level of a binary tree
Write a function to implement Quicksort on Doubly Linked List

Write a function to find number of subarrays with product less than K

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment