乘积小于k的子集数

给定n个元素的数组，必须找到元素乘积小于或等于给定整数k的子集的数目。

例如：

Input : arr[] = {2, 4, 5, 3}, k = 12
Output : 8
Explanation : All possible subsets whose 
products are less than 12 are:
(2), (4), (5), (3), (2, 4), (2, 5), (2, 3), (4, 3)

Input : arr[] = {12, 32, 21 }, k = 1
Output : 0
Explanation : there is not any subset such 
that product of elements is less than 1

方法： 如果我们通过基本方法来解决这个问题，那么我们必须生成所有可能的2 ^N 对于每一个子集，我们必须计算子集元素的乘积，并将乘积值与给定值进行比较。但这种方法的缺点是时间复杂度太高，即O（n*2） ^N )现在，我们可以看到它将是指数时间复杂度，在竞争编码的情况下应该避免。 先进方法： 我们将使用 在中间相遇。 通过使用这个概念，我们可以降低O（n*2）方法的复杂性 ^n/2 ).

如何使用中相遇法： 首先，我们简单地将给定的数组分成两个相等的部分，然后我们为数组的两个部分生成所有可能的子集，并将每个子集的元素积值分别存储到两个向量中（比如subset1和subset2）。现在这将花费O（2） ^n/2 )时间复杂性。现在，如果我们对这两个向量（subset1和subset2）进行排序 ^n/2 )每个元素的成本为O（2 ^n/2 *日志2 ^n/2 )&ap；O（n*（2） ^n/2 ))时间复杂性。在下一步中，我们用2遍历一个向量子集1 ^n/2 元素，并在第二个向量中找到k/subset1[i]的上界，这将告诉我们其乘积小于或等于k的元素总数。因此，对于subset1中的每个元素，我们将尝试在subset2中以上界的形式执行二进制搜索，再次导致时间复杂度为O（n*（2） ^n/2 )). 因此，如果我们试图计算这种方法的总体复杂度，我们将得到O（n*（2） ^n/2 )+n*（2） ^n/2 )+n*（2） ^n/2 ))&ap；O（n*（2） ^n/2 ))由于我们的时间复杂性，这比我们的蛮力方法有效得多。

算法：

1. 将数组分成两个相等的部分。
2. 生成所有子集，并为每个子集计算元素的乘积，并将其推送到向量。对数组的两个部分都尝试这个方法。
3. 对包含每个可能子集元素乘积的两个新向量进行排序。
4. 遍历任意一个向量，找到元素k/向量[i]的上界，以找到元素乘积小于k的向量[i]有多少子集。

提高复杂性的一些关键点：

• 如果大于k，则忽略数组中的元素。
• 如果大于k，则忽略要推入向量（subset1或subset2）的元素的乘积。

  以下是上述方法的实施情况：

  C++

  // CPP to find the count subset having product // less than k #include <bits/stdc++.h> using namespace std; int findSubset( long long int arr[], int n, long long int k) { // declare four vector for dividing array into // two halves and storing product value of // possible subsets for them vector< long long int > vect1, vect2, subset1, subset2; // ignore element greater than k and divide // array into 2 halves for ( int i = 0; i < n; i++) { // ignore element if greater than k if (arr[i] > k) continue ; if (i <= n / 2) vect1.push_back(arr[i]); else vect2.push_back(arr[i]); } // generate all subsets for 1st half (vect1) for ( int i = 0; i < (1 << vect1.size()); i++) { long long value = 1; for ( int j = 0; j < vect1.size(); j++) { if (i & (1 << j)) value *= vect1[j]; } // push only in case subset product is less // than equal to k if (value <= k) subset1.push_back(value); } // generate all subsets for 2nd half (vect2) for ( int i = 0; i < (1 << vect2.size()); i++) { long long value = 1; for ( int j = 0; j < vect2.size(); j++) { if (i & (1 << j)) value *= vect2[j]; } // push only in case subset product is // less than equal to k if (value <= k) subset2.push_back(value); } // sort subset2 sort(subset2.begin(), subset2.end()); long long count = 0; for ( int i = 0; i < subset1.size(); i++) count += upper_bound(subset2.begin(), subset2.end(), (k / subset1[i])) - subset2.begin(); // for null subset decrement the value of count count--; // return count return count; } // driver program int main() { long long int arr[] = { 4, 2, 3, 6, 5 }; int n = sizeof (arr) / sizeof (arr[0]); long long int k = 25; cout << findSubset(arr, n, k); return 0; }

  Python3

  # Python3 to find the count subset # having product less than k import bisect def findSubset(arr, n, k): # declare four vector for dividing # array into two halves and storing # product value of possible subsets # for them vect1, vect2, subset1, subset2 = [], [], [], [] # ignore element greater than k and # divide array into 2 halves for i in range ( 0 , n): # ignore element if greater than k if arr[i] > k: continue if i < = n / / 2 : vect1.append(arr[i]) else : vect2.append(arr[i]) # generate all subsets for 1st half (vect1) for i in range ( 0 , ( 1 << len (vect1))): value = 1 for j in range ( 0 , len (vect1)): if i & ( 1 << j): value * = vect1[j] # push only in case subset product # is less than equal to k if value < = k: subset1.append(value) # generate all subsets for 2nd half (vect2) for i in range ( 0 , ( 1 << len (vect2))): value = 1 for j in range ( 0 , len (vect2)): if i & ( 1 << j): value * = vect2[j] # push only in case subset product # is less than equal to k if value < = k: subset2.append(value) # sort subset2 subset2.sort() count = 0 for i in range ( 0 , len (subset1)): count + = bisect.bisect(subset2, (k / / subset1[i])) # for null subset decrement the # value of count count - = 1 # return count return count # Driver Code if __name__ = = "__main__" : arr = [ 4 , 2 , 3 , 6 , 5 ] n = len (arr) k = 25 print (findSubset(arr, n, k)) # This code is contributed by Rituraj Jain

  输出：

  15