एक सरणी arr[] और एक पूर्णांक k इनपुट के रूप में दिया गया है। लक्ष्य arr[] के उन सबएरे की संख्या ढूंढना है जिनके एलिमेंट्स का गुणनफल k से विभाज्य है।
उदाहरण के लिए
इनपुट
arr[] = {2, 1, 5, 8} k=4 आउटपुट
Count of sub-arrays whose product is divisible by k are: 4
व्याख्या
सबएरे होंगे: [ 8 ], [ 5,8 ], [ 1,5,8 ], [ 2,1,5,8 ]।
इनपुट
arr[] = {7,1,9,7} k=9 आउटपुट
Count of sub-arrays whose product is divisible by k are: 6
व्याख्या
सबएरे होंगे: [ 9 ], [ 9,7 ], [ 1,9 ], [ 1,9,7 ], [ 7,1,9 ], [ 7,1,9,7 ]।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
नाइव दृष्टिकोण
हम इस समस्या को दो दृष्टिकोणों का उपयोग करके हल करेंगे। नाइव दृष्टिकोण में, बस दो फॉर लूप का उपयोग करके सरणी को ट्रैवर्स करें और प्रत्येक सबएरे के लिए इंडेक्स i और j के बीच जांचें कि क्या एलिमेंट्स का गुणनफल k से विभाज्य है। यदि हां तो गिनती बढ़ाएं।
एक पूर्णांक सरणी arr[] और k को इनपुट के रूप में लें।
फ़ंक्शन product_k(int arr[], int size, int k) एक सरणी और k लेता है और k से विभाज्य गुणनफल वाले सबएरे की संख्या लौटाता है।
प्रारंभिक गिनती को इनपुट के रूप में लें।
i=0 से i
प्रत्येक सबएरे arr[i से j] के लिए, arr[k] को temp से गुणा करें।
यदि गुणनफल temp k से विभाज्य है तो गिनती बढ़ाएं।
सभी तीन लूप के अंत में, परिणाम के रूप में गिनती लौटाएं।
कुशल दृष्टिकोण
इस दृष्टिकोण में प्रत्येक सबएरे को ट्रैवर्स करने के बजाय, हम सेगमेंट ट्री में गुणनफल स्टोर करेंगे। अब इस ट्री से उन गुणनफल का उपयोग करें जो k से विभाज्य हैं। और तदनुसार गिनती बढ़ाएं।
एक पूर्णांक सरणी arr[] और k को इनपुट के रूप में लें।
हम सेगमेंट ट्री को एक सरणी arr_2[4 * size_2] के रूप में लागू करेंगे।
फ़ंक्शन set_in(int fit, int first, int last, const int* arr, int k) का उपयोग गुणनफल के लिए सेगमेंट ट्री बनाने के लिए किया जाता है।
फ़ंक्शन check(int fit, int first, int last, int start, int end, int k) का उपयोग start और end के बीच सबएरे का गुणनफल ढूंढने के लिए किया जाता है।
यदि first>last या first>end या last
यदि first>=start और last<=end तो arr_2[fir]%k लौटाएं।
level=first+last >> 1 सेट करें (2 से विभाजित करें)।
अब level और level+1 के लिए check() को रिकर्सिवली कॉल करें और set_1 और set_2 में स्टोर करें।
count=set_1+set_2 सेट करें और count लौटाएं।
फ़ंक्शन product_k(int arr[], int size, int k) arr[] और k लेता है और k से विभाज्य गुणनफल वाले सबएरे की संख्या लौटाता है।
प्रारंभिक गिनती को 0 के रूप में लें।
प्रारंभिक गिनती को 0 के रूप में सेट करें।
i=0 से i
यदि यह temp 0 है तो गिनती बढ़ाएं।
अंतिम परिणाम के रूप में गिनती लौटाएं।
उदाहरण
#include <bits/stdc++.h> using namespace std; int product_k(int arr[], int size, int k){ int count = 0; for (int i = 0; i < size; i++){ for (int j = i; j < size; j++){ int temp = 1; for (int k = i; k <= j; k++){ temp = temp * arr[k]; } if(temp % k == 0){ count++; } } } return count; } int main(){ int arr[] = {2, 1, 5, 8, 10, 12 }; int size = sizeof(arr) / sizeof(arr[0]); int k = 2; cout<<"Count of sub-arrays whose product is divisible by k are: "<<product_k(arr, size, k); return 0; } आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Count of sub-arrays whose product is divisible by k are: 18
उदाहरण (कुशल दृष्टिकोण)
#include <bits/stdc++.h> using namespace std; #define size_2 100002 int arr_2[4 * size_2]; void set_in(int fit, int first, int last, const int* arr, int k){ if (first == last){ arr_2[fit] = (1LL * arr[first]) % k; return; } int level = (first + last) >> 1; set_in(2 * fit, first, level, arr, k); set_in(2 * fit + 1, level + 1, last, arr, k); arr_2[fit] = (arr_2[2 * fit] * arr_2[2 * fit + 1]) % k; } int check(int fit, int first, int last, int start, int end, int k){ if(first > last){ return 1; } if(first > end){ return 1; } if(last < start){ return 1; } if (first >= start){ if(last <= end){ return arr_2[fit] % k; } } int level = (first + last) >> 1; int set_1 = check(2 * fit, first, level, start, end, k); int set_2 = check(2 * fit + 1, level + 1, last, start, end, k); int count = (set_1 * set_2) % k; return count; } int product_k(int arr[], int size, int k){ int count = 0; for (int i = 0; i < size; i++){ for (int j = i; j < size; j++){ int temp = check(1, 0, size - 1, i, j, k); if (temp == 0){ count++; } } } return count; } int main(){ int arr[] = {2, 1, 5, 8, 10, 12}; int size = sizeof(arr) / sizeof(arr[0]); int k = 2; set_in(1, 0, size - 1, arr, k); cout<<"Count of sub-arrays whose product is divisible by k are: "<<product_k(arr, size, k); return 0; } आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Count of sub-arrays whose product is divisible by k are: 18
