v0rtex's blog

Minimum subset size for target sum.
By v0rtex, history, 3 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't this the famous coin change problem? You can easily find the solution online.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This problem came in Colortoken placement exam. Can you please tell me how can it be solved?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Can you say the time limit, and you sure that constraint is 10^6?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          ![ ](6305047218306002650-121)

          The sample output were: 2 and -1

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            Are you sure that they ask about finding subset?You tried submit solution for subsegment?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              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.

              → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

            nice statement awesome task

            → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you elaborate on this sqrt optmization (or provide links)? Depending on what it is maybe the solution is using it with bitset

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Or can't we do fft here? Binary search on no of boxes. Complexity will be $$$O(N*logN*log(max a_i))$$$

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How do you check that you can collect this amount or not by FFT with fixed amount of items?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -18 Vote: I do not like it

          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.

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 <= 1000

and would it really be possible to solve under normal time-limits i.e. 1 or 2 sec if N,S were 10^5?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So you got the answer? if yes can you please share.

→ Reply