IN The basic O(N) solution for the problem that given a sorted array of no.s,find the smallest no. which cannot be formed by any subset of no.s from the array.
If we asssume that the smallest unachievable sum is res till arr[i-1] then it is the answer if arr[i]>res
That part is quite clear…
But the fact that :
the new res = res + arr[i] if arr[i] <= res is not clearly proven… How can we say that the new res cannot also be formed by some elements from index 0…i-1 from the array…
If we can say that it cannot be achieved by any subset from 0…i-1 then it is definitely the new res…
int main()
{
std::cout.sync_with_stdio(false);
unsigned long long int t;
cin>>t;
while(t--)
{
unsigned long long int n,k;
cin>>n>>k;
unsigned long long int res=1;
unsigned long long int a[k],b[n-k];
for(unsigned long long int i=0;i<k;i++) cin>>a[i];
sort(a,a+k);
unsigned long long int i=1,j=0,x=0;
while(i<=n)
{
if(a[j]==i)
{
i++;
j++;
}
else
{
b[x]=i;
i++;
x++;
}
}
sort(b,b+n-k);
for(i=0;i<n-k&&b[i]<=res;i++)
res+=b[i];
//cout<<res<<endl;
if(res%2==0)
cout<<"Mom"<<endl;
else
cout<<"Chef"<<endl;
}
return 0;
}
I am getting run-time error(SIGSEGV) in task 3 only can you tell me why?