Sum of minimum number of elements equal to K

#1

Question: Sum of minimum number of elements equal to K.
input:first line contains n and k,second line contains n number of elements.
6 15
2 4 5 6 7 8
ans : 2
explanation : 7+8=15 i.e minimum no of elements.
also 4+5+6 =15 but minimum no is 2 (7,8)

#2

Please reply :roll_eyes::roll_eyes::roll_eyes::roll_eyes::roll_eyes:

#3

I am stuck since yesterday,please reply

#4

I posted doubt last night at 9p.m. still I didn’t get any reply, I heard TA’s reply within 10,15 mins but its more than 15 hours now?

#5

hey @samardeep
sorry for the delay .what help do you need with this question exactly?

#6

I dont know the apprach for the problem? help me with the approach.

#7

the idea is to use Dynamic Programming to solve this problem. Create a [DP table]of N * K to store the pre-computed answer for the previous sequence that is the minimum length sequence required to get the sum as K – arr[i] and in this way the finally after calculating for every value of the array, the answer to the problem will be dp[N][K]
see this:

#8

n,k : 8 76 array elements: 7 6 6 9 9 10 19 20 acc to your approach it gives 4 as output but should give 7

#9

why? 19+19+19+19=76 ,so 4

#10

u chosed 1 element 4 times na, 19+19+19+19 but u can’t do this way na,ans is 7( 6 6 9 9 10 19 20)

#11

okay you didnt mention that about the question.please share the question link

#12

we have use those number which are present in array as many time as the are pressent in array …like …we can use “7 " 3 times only …” 10" 1 time only.I dot have question link ,it is share in one of my college whatsapp group.

#13

Dont*…

#14

pleeaaaassseee reply

#15

you mean for this test case wecan not repeat the element right?coz there is 7 only once ?
also please tag me in your replies so that i get a notification

#16

@Abha Agrawal you can use the elements as many times they are given in the array

#17

@samardeep
The idea is to use a sliding window and variables j initialize it to 0, min_num to store the answer and sum to store the current sum. Keep on adding the elements of the array to the variable sum , till it becomes greater than or equal to k, if it is equal to k, then update the min_num as minimum of min_num and (i+1) -j where i is the current index, else if it is greater than k, then start decrementing the sum by removing the values of the array from sum till the sum becomes less than or equal to k and also increment the value of j , if sum is equal to k, then once again update min_num

#18

could you please send me the code, i am getting wrong answer

#19

Share your approach with me. I ll help you correct it