Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is Binary Search?
4.2.
What does lower bound mean in C++?
4.3.
What is the bitwise AND operator in C++?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Number of subsets with product less than k

Author Anju Jaiswal
0 upvote

Introduction

In this article, we will learn to solve the problem of subsets with products less than K. Array-based questions are the most popular in coding interviews and programming competitions. We will see the problem from different angles and analyze it to reach the optimal solution eventually.

Let's get started with the problem statement.

Also Read About, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Given an array of n elements, determine the number of subsets with a product of elements less than a given integer k.

Before proceeding the with the approach, we need to understand what the subset of the array means:

Subset is all the possible combinations of the array using each element (including phi) which means no array elements.

Subsets may not be contiguous and may not be in order.

Example - {2, 5, 3, 9}

Possible subsets- {}, {2}, {5}, {3}, {9}, {2,5} {2,3}, {2,9}, {5,3}, {5,9}, {3,9}, {2,5,3}, {2,5,9}, {2,3,9}, {5,3,9}, {2,5,3,9}.

An array's number of subsets is 2^N, where N is the array's Size. 

Sample Example

Input : arr[] = {2, 3, 5, 1, 6}, k = 11
Output :Number of subsets with product less than k:10
Explanation : All possible number subsets with
product less than k are:
(2), (3), (5), (1), (6), (2, 3), (2, 5), (2, 1), (3, 1), (5,1), (1,6), (2,3,1), (2,5,1)

Input : arr[] = {13, 42, 11 }, k = 1
Output : Number of subsets with product less than k: 0
Explanation : there is no possible subset such
that product of elements of each subset is less than 1

Brute Force Approach

This is the most straightforward approach for this problem: find all the subsets of the array, check their product, and count those subsets with products less than k.

Then print the count.

Pseudocode

  1. Generate all the subsets of the array and a count variable set to 0.

 

  1. For each subset, calculate the product of its elements and check whether the product is less than k or not. If yes, then increment the count.
  2. Return the count.

Implementation in C++

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int Subsets_with_product_less_than_k(vector < ll > & vect, int n, long long int k) {
  int count = 0;
  //generating all the subsets
  for (int i = 0; i < (1 << n); i++) {
    long long value = 1;
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) {
        value *= vect[j];
      }
    }
    // counting the subset with product less than k and excluding empty //subset
    if (value < k && i != 0)
      count++;
  }
  return count;
}
int main() {
  vector < long long int > vect { 2, 3, 5, 1, 6 };
  int n = vect.size();
  long long int k = 25;
  cout << "Number of Subsets with product less than k: " << Subsets_with_product_less_than_k(vect, n, k);
  return 0;
}

 

Output:

Number of Subsets with product less than k: 13

 

Complexity Analysis

Time complexity: O(n*2n) because we have to generate all possible 2n subsets, and for each of them, we have to calculate the product of elements of the subset and compare the value of the product with the given value of K.

N = Size of the array.

Space Complexity: O(1)

No extra space is used.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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*2n/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;
}

 

Output:

Number of Subsets with product less than k: 13

 

Complexity Analysis

Time Complexity: O(n*(2n/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(2n/2). Now, if we sort these two vectors (subset_1 & subset_2) with (2n/2) elements each, the time complexity will be O(2n/2*log2n/2) ≈ O(n*(2n/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*(2n/2)) once more. So, if we try to compute our complexity for this strategy, we'll get O(n*(2n/2)) .

Space Complexity: O(2n/2)

The size of each new array used to store the product of each element of possible subsets is O(2n/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 AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine 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 problemsinterview 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!!

Previous article
Find Zeroes to be Flipped, so that Number of Consecutive 1's is Maximised with K Maximum Flips
Next article
Maximize elements using another array
Live masterclass