Saw this problem yesterday in GFG daily code... However, the problem showed time limit exceed. Time Limit Exceed: ------------------------------ < Your code > Accepted Code: ------------------------- for (int i = 0; i < n && a[i]
Look like some misunderstanding..consider this example [1,2,3,5]. Your implementation look like return 4 where as 1+3 is 4. Is it your implementation wrong.? Or my understanding.?
Hello yashvi , Sorry to know that , the video was recorded live while I was solving the problem , Maybe that's the reason the video is short and you couldn't understand . Will try to give longer and simpler explanations going further.. Thanks for the feedback
@@yashvisoni5819 Two parts to this problem. First part is.. sorting is required in ascending order... so he's using quick sort which takes O(n logn). Once the sorting is done, the minimum answer is 1, because 0 is neutral, it's not positive or negative. Now... say this is your array A{1,1,1} right ? so, as you could see... 1 is already present in the array.... the questions asks for minimum for any possible sum right ? NOTE: If you have a array, then each individual element is also a subset of the actual array. Based on this 1 is also a subset, so 1 cannot be the answer, infact none of the elements in the array is your answer. So, what is the answer then ? Because we sorted earlier, what we could do is find the gaps... so for this example A {1,2,12,13} .... As none of the elements could be the answer, forget all the individual elements, we are interested in the sum. By default we assumed answer is 1, but 1 is one of the element, so it cannot be the answer. So, we added the a[0] to our variable "ans", whose initial value is 1. so... "ans" is now "ans"+a[0] = 2 Now, 2 is also present in the array, so it cannot be the answer. so... "ans" is now ''ans"+a[i] = 4 Now... what's the next element? It's 12 right? which is bigger than the last value of "ans" which is 4. now we don't care about the rest of the elements in the array. Because the elements are sorted everything else will be bigger only. Our last value for "ans" was 4. Now what 2 elements have we covered already? a[0] and a[1] right ? NOT a[2]. because it was bigger than "ans" so what possible sum can we get from a[0] and a[1] a[0] = 1 and a[1] = 2 so, it cannot be 1, it cannot be 2, because they are elements, it cannot be 3 also, because we can make 3 by adding a[0] and a[1]. Therefore, it cannot be 1, 2 or 3. So, the smallest positive integer that cannot be represented as sum of any subset is our "ans" which is 4.
Can you please the for loop.. i couldn't get it. How it worked? 😕🥺 Please. With an example.🙏thank you
Hello Akhil,
I suggest you to have a look at python loops documentation
Saw this problem yesterday in GFG daily code... However, the problem showed time limit exceed.
Time Limit Exceed:
------------------------------
< Your code >
Accepted Code:
-------------------------
for (int i = 0; i < n && a[i]
Look like some misunderstanding..consider this example [1,2,3,5]. Your implementation look like return 4 where as 1+3 is 4. Is it your implementation wrong.? Or my understanding.?
Please provide it in c++
Hello Kunal,
Will try to implement in py and cpp for further videos 👍👍 . The Motive was to focus on the algorithm rather than implementation ...
i cant understand problem
Hello yashvi ,
Sorry to know that , the video was recorded live while I was solving the problem , Maybe that's the reason the video is short and you couldn't understand . Will try to give longer and simpler explanations going further.. Thanks for the feedback
@@SaiprakashReddy yaa thanks but can you explain me this problem????
@@yashvisoni5819 Two parts to this problem.
First part is.. sorting is required in ascending order... so he's using quick sort which takes O(n logn).
Once the sorting is done, the minimum answer is 1, because 0 is neutral, it's not positive or negative.
Now... say this is your array A{1,1,1} right ? so, as you could see... 1 is already present in the array.... the questions asks for minimum for any possible sum right ?
NOTE: If you have a array, then each individual element is also a subset of the actual array.
Based on this 1 is also a subset, so 1 cannot be the answer, infact none of the elements in the array is your answer.
So, what is the answer then ?
Because we sorted earlier, what we could do is find the gaps... so for this example
A {1,2,12,13} .... As none of the elements could be the answer, forget all the individual elements, we are interested in the sum.
By default we assumed answer is 1, but 1 is one of the element, so it cannot be the answer.
So, we added the a[0] to our variable "ans", whose initial value is 1.
so... "ans" is now "ans"+a[0] = 2
Now, 2 is also present in the array, so it cannot be the answer.
so... "ans" is now ''ans"+a[i] = 4
Now... what's the next element? It's 12 right? which is bigger than the last value of "ans" which is 4.
now we don't care about the rest of the elements in the array. Because the elements are sorted everything else will be bigger only.
Our last value for "ans" was 4.
Now what 2 elements have we covered already? a[0] and a[1] right ? NOT a[2]. because it was bigger than "ans"
so what possible sum can we get from a[0] and a[1]
a[0] = 1 and a[1] = 2
so, it cannot be 1, it cannot be 2, because they are elements, it cannot be 3 also, because we can make 3 by adding a[0] and a[1].
Therefore, it cannot be 1, 2 or 3.
So, the smallest positive integer that cannot be represented as sum of any subset is our "ans" which is 4.
Please
Can speak in Hindi
Hello Nandini ,
I understand you , but I don't speak Hindi . Hope you understand .