Buying Sweets (BUYING2) - Codechef

Question

As the problem statement is long I am attachng the link: https://www.codechef.com/problems/BUYING2

Code:

#include <stdio.h>

int main() {

    int t;
    scanf("%d",&t);
    int n, x, a[101];
    int i, j, temp;
    int s, r;
    while(t--)
    {
        int sum1;
        scanf("%d %d", &n, &x);

        if(n>1)    
        {    
            sum1 = 0;
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
                sum1 += a[i];
            }

            for(i=0;i<n;i++)
            {
                for(j=i;j<n;j++)
                {
                    if(a[j] < a[i])
                    {
                        temp = a[j];
                        a[j] = a[i];
                        a[i] = temp;
                    }
                }
            }
            s = sum1 / x;
            r = sum1 - x*s;
            if(r > a[0]) printf("-1\n");
            else printf("%d\n", s);
        }

        if(n==1)
        {
            scanf("%d",&a[0]);
            s = a[0]/x;
            if (s>=1) printf("%d\n", s);
            else printf("-1\n");
        }
    }
    return 0;
}

Output:

3
4 7
10 4 8 5
-1
2 10
20 50
7
1 10
12
1

Error: Codechef is saying my answer is wrong. Is there any test cases that I might be missing in this problem. Also I am just a beginner could you sugguest any optimisations.

Answer 1

The error is in this statement:

if(r > a[0]) printf("-1\n");`

The correct condition should be:

if(r >= a[0]) printf("-1\n");`// See even if it is equal then also he is inadequate

But overall for better efficiency following code is better:

Code:

#include <stdio.h>

int main() {

    int t;
    scanf("%d",&t);
    int n, x, a[1000];
    int i, r;
    while(t--)
    {
        int sum = 0;
        int j = 0;
        scanf("%d %d", &n, &x);

        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum += a[i];
        }

        if(sum%x == 0)
        {
            printf("%d\n",sum/x);
        }

        else
        {
            r = sum - ((sum/x)*x);

            for(i=0;i<n;i++)
            {
                if(r >= a[i]) j++;
            }

            if(j>0) printf("%d\n",-1);
            else printf("%d\n", sum/x);
        }
    }           

    return 0;
}

Explanation: This removes any sorting of array which costs heavily.