Number of subsets with product less than k

Optimized Approach

We are going to use the strategy of meeting in the middle. Using this concept, we can optimize the complexity of our approach to O(n*2^n/2).

Meet in the middle is a technique for searching when the input is not as small as brute force can handle. It divides the problem into two halves, solves each separately, and then merges them. However, because we don't have the same structure as the original problem, we can't use meet in the middle techniques like divide and conquer.

Pseudocode

1. Divide the array into two pieces of equal size.
2. Create all subsets, then calculate the product of elements for each subset and save it as a vector. This should work for both parts of the array.

1. Sort both new vectors containing element products for each possible subgroup.
2. To find how many subsets exist for vector[i] whose product of elements is more or less than k, traverse any one vector and find the upper bound of element k/vector[i].

Some key points to improve complexity :

• If the element value in the array is more than k, ignore them.
• If k is more significant than 1, ignore the product of elements to push into a vector (subset1 or subset2).

Implementation in C++

#include <bits/stdc++.h>

#define ll long long int
using namespace std;

int Subsets_with_product_less_than_k(vector < ll > vect, int n, ll k) {
  //first divide the array in two halves and store the product value of //possible subsets.
  vector < ll > v1_half, v2_half, subset_1, subset_2;

  for (int i = 0; i < n; i++) {
    // ignore element if greater than k
    if (vect[i] > k)
      continue;
    if (i <= n / 2)
      v1_half.push_back(vect[i]);
    else
      v2_half.push_back(vect[i]);
  }

  // generate all subsets for 1st half (v1)
  for (int i = 0; i < (1 << v1_half.size()); i++) {
    ll value = 1;
    for (int j = 0; j < v1_half.size(); j++) {
      if (i & (1 << j))
        value *= v1_half[j];
    }
    // push only those Subsets with product less than k

    if (value < k)
      subset_1.push_back(value);
  }

  // generate all the  subsets for 2nd half (v2)
  for (int i = 0; i < (1 << v2_half.size()); i++) {
    ll value = 1;
    for (int j = 0; j < v2_half.size(); j++) {
      if (i & (1 << j))
        value *= v2_half[j];
    }

    // push only those Subsets with product less than k

    if (value < k)
      subset_2.push_back(value);
  }

  // sort the subset2
  sort(subset_2.begin(), subset_2.end());

  ll count = 0;
  for (int i = 0; i < subset_1.size(); i++)
    count += upper_bound(subset_2.begin(), subset_2.end(),
      (k / subset_1[i])) - subset_2.begin();

  // for null subset decrement the value of count
  count--;

  // return the count
  return count;
}
int main() {
  vector < long long int > vect { 2, 3, 5, 1, 6 };
  int n = vect.size();
  long long int k = 11;
  cout << "Number of Subsets with product less than k: " << Subsets_with_product_less_than_k(vect, n, k);
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Number of Subsets with product less than k: 13

Complexity Analysis

Time Complexity: O(n*(2^n/2))

Explanation: First, we partition the provided array into two equal parts, then produce all possible subsets for both parts of the array and store the value of each subset's elements separately in two vectors (say subset_1 & subset_2). This now has a temporal complexity of O(2^n/2). Now, if we sort these two vectors (subset_1 & subset_2) with (2^n/2) elements each, the time complexity will be O(2^n/2*log2^n/2) ≈ O(n*(2^n/2)). The next step is to traverse one vector subset_1 with 2n/2 members and discover the upper bound of k/subset_1[i] in the second vector, which will tell us how many total elements have products less than or equal to k.

Thus, for each member in subset_1, we will attempt to execute a binary search in subset_2 in the form of an upper bound, resulting in a Time complexity of O(n*(2^n/2)) once more. So, if we try to compute our complexity for this strategy, we'll get O(n*(2^n/2)) .

Space Complexity: O(2^n/2)

The size of each new array used to store the product of each element of possible subsets is O(2^n/2).

Must Read Lower Bound in C++

Frequently Asked Questions

What is Binary Search?

A binary search is a quick approach to finding a specific item in a sorted list of items. It works by halving the list section that could contain the item until you've narrowed the selections down to just one.

What does lower bound mean in C++?

In C++, the lower bound() method returns an iterator pointing to the first element in the range [first, last) with a value greater than or equal to value. This indicates that the method returns an iterator pointing to the following smallest number that is just greater than or equal to the current number.

What is the bitwise AND operator in C++?

In C or C++, the & (bitwise AND) operator accepts two numbers as operands and performs AND on each bit of the two numbers. Only if both bits are 1 is the outcome of AND.

Conclusion

This article discussed the different approaches to finding the number of subsets with a product less than k, starting with the brute first approach and then the efficient approach with examples and its C++ code.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Read about Bitwise Operators in C here.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!