Given an array[] of N positive integers and M queries. Each query consists of two integers L and R represented by a range. For each query, find the count of numbers that lie in the given range which can be expressed as the sum of any subset of given array.
Prerequisite : Subset Sum Queries using Bitset
Examples:
Input : arr[] = { 1, 2, 2, 3, 5 }, M = 4 L = 1, R = 2 L = 1, R = 5 L = 3, R = 6 L = 9, R = 30
Output : 2 5 4 5
Explanation : For the first query, in range [1, 2] all numbers i.e. 1 and 2 can be expressed as a subset sum, 1 as 1, 2 as 2. For the second query, in range [1, 5] all numbers i.e. 1, 2, 3, 4 and 5 can be expressed as subset sum, 1 as 1, 2 as 2, 3 as 3, 4 as 2 + 2 or 1 + 3, 5 as 5. For the third query, in range [3, 6], all numbers i.e. 3, 4, 5 and 6 can be expressed as subset sum. For the last query, only numbers 9, 10, 11, 12, 13 can be expressed as subset sum, 9 as 5 + 2 + 2, 10 as 5 + 2 + 2 + 1, 11 as 5 + 3 + 2 + 1, 12 as 5 + 3 + 2 + 2 and 13 as 5 + 3 + 2 + 2 + 1.
Approach: The idea is to use a bitset and iterate over the array to represent all possible subset sums. The current state of bitset is defined by ORing it with the previous state of bitset left shifted X times where X is the current element processed in the array. To answer the queries in O(1) time, we can precompute the count of numbers upto every number and for a range [L, R], the answer would be pre[R] – pre[L – 1], where pre[] is the precomputed array.
Below is the implementation of the above approach.
C++
// CPP Program to answer subset// sum queries in a given range#include <bits/stdc++.h>using namespace std;const int MAX = 1001;bitset<MAX> bit;// precomputation arrayint pre[MAX];// structure to represent querystruct que { int L, R;};void answerQueries(int Q, que Queries[], int N, int arr[]){ // Setting bit at 0th position as 1 bit[0] = 1; for (int i = 0; i < N; i++) bit |= (bit << arr[i]); // Precompute the array for (int i = 1; i < MAX; i++) pre[i] = pre[i - 1] + bit[i]; // Answer Queries for (int i = 0; i < Q; i++) { int l = Queries[i].L; int r = Queries[i].R; cout << pre[r] - pre[l - 1] << endl; }}// Driver Code to test above functionint main(){ int arr[] = { 1, 2, 2, 3, 5 }; int N = sizeof(arr) / sizeof(arr[0]); int M = 4; que Queries[M]; Queries[0].L = 1, Queries[0].R = 2; Queries[1].L = 1, Queries[1].R = 5; Queries[2].L = 3, Queries[2].R = 6; Queries[3].L = 9, Queries[3].R = 30; answerQueries(M, Queries, N, arr); return 0;} |
Java
import java.util.Arrays;// Class to represent queryclass Que { int L, R; Que(int L, int R) { this.L = L; this.R = R; }}public class Main { private static final int MAX = 1001; private static boolean[] bit = new boolean[MAX]; // Precomputation array private static int[] pre = new int[MAX]; public static void answerQueries(int Q, Que[] Queries, int N, int[] arr) { // Setting bit at 0th position as 1 bit[0] = true; for (int i = 0; i < N; i++) { for (int j = MAX - 1; j >= arr[i]; j--) { bit[j] |= bit[j - arr[i]]; } } // Precompute the array for (int i = 1; i < MAX; i++) { pre[i] = pre[i - 1] + (bit[i] ? 1 : 0); } // Answer Queries for (int i = 0; i < Q; i++) { int l = Queries[i].L; int r = Queries[i].R; System.out.println(pre[r] - pre[l - 1]); } } // Driver Code to test above function public static void main(String[] args) { int[] arr = {1, 2, 2, 3, 5}; int N = arr.length; int M = 4; Que[] Queries = {new Que(1, 2), new Que(1, 5), new Que(3, 6), new Que(9, 30)}; answerQueries(M, Queries, N, arr); }} |
Python3
from typing import ListMAX = 1001bit = [0] * MAX# precomputation arraypre = [0] * MAX# structure to represent queryclass Que: def __init__(self, L, R): self.L = L self.R = Rdef answerQueries(Q: int, Queries: List[Que], N: int, arr: List[int]) -> None: global bit, pre # Setting bit at 0th position as 1 bit[0] = 1 for i in range(N): bit = [b or (bit[j - arr[i]] if j - arr[i] >= 0 else 0) for j, b in enumerate(bit)] # Precompute the array for i in range(1, MAX): pre[i] = pre[i - 1] + bit[i] # Answer Queries for i in range(Q): l = Queries[i].L r = Queries[i].R print(pre[r] - pre[l - 1])# Driver Code to test above functionif __name__ == "__main__": arr = [1, 2, 2, 3, 5] N = len(arr) M = 4 Queries = [Que(1, 2), Que(1, 5), Que(3, 6), Que(9, 30)] answerQueries(M, Queries, N, arr) |
C#
using System;public class GFG{ private const int MAX = 1001; private static bool[] bit = new bool[MAX]; // Precomputation array private static int[] pre = new int[MAX]; // Class to represent query public class Que { public int L, R; public Que(int L, int R) { this.L = L; this.R = R; } } public static void answerQueries(int Q, Que[] Queries, int N, int[] arr) { // Setting bit at 0th position as 1 bit[0] = true; for (int i = 0; i < N; i++) { for (int j = MAX - 1; j >= arr[i]; j--) { bit[j] |= bit[j - arr[i]]; } } // Precompute the array for (int i = 1; i < MAX; i++) { pre[i] = pre[i - 1] + (bit[i] ? 1 : 0); } // Answer Queries for (int i = 0; i < Q; i++) { int l = Queries[i].L; int r = Queries[i].R; Console.WriteLine(pre[r] - pre[l - 1]); } } // Driver Code to test above function public static void Main(String[] args) { int[] arr = { 1, 2, 2, 3, 5 }; int N = arr.Length; int M = 4; Que[] Queries = { new Que(1, 2), new Que(1, 5), new Que(3, 6), new Que(9, 30) }; answerQueries(M, Queries, N, arr); }} |
Javascript
// JavaScript Program to answer subset// sum queries in a given rangeconst MAX = 1001;let bit = Array(MAX).fill(0);// precomputation arraylet pre = Array(MAX).fill(0);// class to represent queryclass Que {constructor(L, R) {this.L = L;this.R = R;}}function answerQueries(Q, Queries, N, arr) {// Setting bit at 0th position as 1bit[0] = 1;for (let i = 0; i < N; i++) {for (let j = MAX - 1; j >= arr[i]; j--) {bit[j] |= bit[j - arr[i]];}}// Precompute the arrayfor (let i = 1; i < MAX; i++) { pre[i] = pre[i - 1] + bit[i];}// Answer Queriesfor (let i = 0; i < Q; i++) { let l = Queries[i].L; let r = Queries[i].R; console.log(pre[r] - pre[l - 1]);}}// Driver Code to test above functionlet arr = [1, 2, 2, 3, 5];let N = arr.length;let M = 4;let Queries = [new Que(1, 2), new Que(1, 5), new Que(3, 6), new Que(9, 30)];answerQueries(M, Queries, N, arr); |
2 5 4 5
Time Complexity: Each query can be answered in O(1) time and precomputation requires O(MAX) time.
Auxiliary Space: O(MAX)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
