मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी nums दी गई है। हमें उन सन्निहित उपसरणियों (subarrays) की संख्या गिननी और प्रिंट करनी है जहां उपसरणी में प्रत्येक तत्व का गुणनफल k से कम है। इसलिए यदि इनपुट [10,5,2,6] जैसा है और k := 100, तो आउटपुट 8 होगा। तो उपसरणियाँ होंगी [[10], [5], [2], [6], [10, 5], [5, 2], [2, 6] और [5, 2, 6]]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- temp := 1, j := 0 और ans := 0
- i को 0 से सरणी के आकार तक की रेंज में
- temp := temp * nums[i]
- जब तक temp >= k और j <= i, करें
- temp := temp / nums[j]
- j को 1 से बढ़ाएं
- ans := ans + (i - j + 1)
- ans लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { lli temp = 1; int j = 0; int ans = 0; for(int i = 0; i < nums.size(); i++){ temp *= nums[i]; while(temp >= k && j <= i) { temp /= nums[j]; j++; } ans += (i - j + 1); } return ans; } }; main(){ Solution ob; vector<int> v = {10,5,2,6}; cout << (ob.numSubarrayProductLessThanK(v, 100)); }इनपुट
[10,5,2,6] 100
आउटपुट
8