### v0rtex's blog

By v0rtex, history, 2 years ago,

An array of size N is given and a value K. You have to find the minimum subset size so that subset sum is exactly equal to K, if not print -1. 0 < K, a[i], N < 10^6.

• +6

| Write comment?
 » 2 years ago, # |   0 Isn't this the famous coin change problem? You can easily find the solution online.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 Sorry, can you explain how?In problem which mentioned in post constraints for $N, K, a_i$ to high for stupid knapsack.Other solution with sqrt opt works $O(n * log(max(a_i)) * sqrt(K))$, thats too much.
•  » » » 2 years ago, # ^ |   0 This problem came in Colortoken placement exam. Can you please tell me how can it be solved?
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Can you say the time limit, and you sure that constraint is 10^6?
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 ![ ]()The sample output were: 2 and -1
•  » » » » » » 2 years ago, # ^ |   +11 Are you sure that they ask about finding subset?You tried submit solution for subsegment?
•  » » » » » » » 2 years ago, # ^ |   +10 I think so too. Since the output for the second case is -1 they are probably asking for a subsegment (even if that is not clear in the statement). This could be solved in O(n) by using two pointers as well, which explains the constraints.
•  » » » » » » 2 years ago, # ^ |   +9 nice statement awesome task
•  » » » 2 years ago, # ^ |   0 Could you elaborate on this sqrt optmization (or provide links)? Depending on what it is maybe the solution is using it with bitset
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Or can't we do fft here? Binary search on no of boxes. Complexity will be $O(N*logN*log(max a_i))$
•  » » » » 2 years ago, # ^ |   0 How do you check that you can collect this amount or not by FFT with fixed amount of items?
•  » » » » » 2 years ago, # ^ |   -18 I mean Like we do "Fast subset transform" in a similar way if possible lets say $s$ will be the smallest size of some subset such that it's sum is $K$. then polynomial raise to power $s$ will contains non-zero coefficient for $x^K$ term right.
 » 2 years ago, # |   0 I encountered a similar problem recently, can someone suggest some solution: Given an array A of size N, find the number of subsets of size exactly K that add up to S. e.g: A = [1,1,1,2,3,4] K=3, S=6 answer: 6 explanation (0 based indexing) [0,1,5] [0,2,5] [1,2,5] [0,3,4] [1,3,4] [2,3,4] I don't remember the constraints, but let's say 1 <= N,S <= 1000and would it really be possible to solve under normal time-limits i.e. 1 or 2 sec if N,S were 10^5?
•  » » 2 years ago, # ^ |   0 I dont know anything better than $O(NS)$. You can submit it here https://www.geeksforgeeks.org/count-of-subsets-with-sum-equal-to-x/
•  » » » 2 years ago, # ^ |   0 you missed out on the point Subsets of length exactly K with sum S. The link only talks about subsets with sum S which is quite a standard problem.
 » 2 months ago, # |   0 So you got the answer? if yes can you please share.