4
\$\begingroup\$

I have solved the given assignment below is the question and getting correct answer. but my question is is there any way to reduce the complexity of my code or there is any other efficient way to write the code?

Given two arrays of integers output the smallest number in the first array not present in the second one.

Input Specification:

The first line contains the size N1 of the first array. Next line give the contents of the first array. Next line contains the size N2 of the second array. Next line give the contents of the second array.

Output Format:

Output must be a single number which is the smallest number occurring in the first array that does not occur in the second. In case there is no such number, output NO.

Variable Constraints:

The sizes of the arrays are smaller than 20. Each array entry is an integer which fits an int data type.

Example Input:

3
2 3 4
4
1 3 5 7

Output: 2

Example Input:

1
1
2
1 2

Output: NO

Here is the code.

#include<stdio.h>
int main(void)
{
    int a[10],b[10];
    int small=0,l1,l2,i,flag=0;
    scanf("%d",&l1);
    for(i=0;i<l1;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&l2);
    for(i=0;i<l2;i++)
    {
        scanf("%d",&b[i]);
    }
    small=a[0];
    for(i=1;i<l1;i++)
    {
        if(small>a[i])
          small=a[i];
    }
    for(i=0;i<l2;i++)
    {
        if(small==b[i])
          flag=1;
    }
        if(flag==1)
        {
            printf("NO");
        }
        else
        {
            printf("%d",small);
        } 
   return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The sample arrays are in ascending order - is that a property you can rely on? \$\endgroup\$ – Toby Speight Aug 31 '17 at 15:05
3
\$\begingroup\$

Why do you make your arrays only 10 elements large when the task explicitly says 20?

Even worse, you don't protect the program from writing outside the array. The C programming language doesn't protect against this wrong behavior, therefore you as the programmer must do this.

Before every write to an array you must check that the array index is valid. For example:

assert(0 <= idx && idx < arr_len);
arr[idx] = value;

Only if you can prove mathematically that the assert condition is always true, can you leave out the assert. Follow this advice, and your programs will be better than 80% of the existing C programs.


To reduce the complexity of the main function, you should define a function like this:

bool intarray_contains(const int *arr, size_t arr_len, int value) {
    ...
}

Then you don't need to write this code in main.


After that, to ensure that your program works correctly (it currently doesn't), you should extract the calculation into a separate function:

int min_not_present_in(const int *arr1, size_t arr1_len, const int *arr2, size_t arr2_len) {
    ...
}

This function definition allows you to do the calculation without entering the values every time. Like this:

int positive[] = { 1, 2, 3 };
int odd[] = { 1, 3, -1 };
int even[] = { -2, 0, 2 };

assert(min_not_present_in(positive, 3, odd, 3) == 2);
assert(min_not_present_in(positive, 3, even, 3) == 1);

To make all this work, you need the following lines at the top of your file:

#include <assert.h>
#include <stdbool.h>
\$\endgroup\$
2
\$\begingroup\$

For starters, in the last iteration of the code,you can modify the loop such that, whenver small!=b[i] the loop stops and prints the answer, thus saving you iteration time in larger test cases.

for(i=0;i<l2;i++)
{
    if(small!=b[i])
    {
        printf("%d",small);
        return 0;
    }
}

From the looks of the input cases, i have a speculation that, both the input arrays are sorted in ascending order. If it is true, then you can further modify the program like this:

for(i=0;i<l1;i++)
{
    small=a[i];
    for(j=0;j<l2;j++)
    {
        if(small!=b[j])
        {
            printf("%d",small);
            return 0;
        }
    }
}
printf("NO");
return 0;

This is basically a modified bubble sort like program.

You can also declare the arrays after taking the l1 and l2 values to avoid unnecessary memory consumption. Then,your whole code would look like this:

#include<stdio.h>
int main(void)
{
    int small=0,l1,l2,i,j;
    scanf("%d",&l1);
    int a[l1];
    for(i=0;i<l1;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&l2);
    int b[l2];
    for(i=0;i<l2;i++)
    {
        scanf("%d",&b[i]);
    }
    for(i=0;i<l1;i++)
    {
        small=a[i];
        for(j=0;j<l2;j++)
        {
            if(small!=b[j])
            {
                printf("%d",small);
                return 0;
            }
        }
    }
    printf("NO");
    return 0;
}
\$\endgroup\$
2
\$\begingroup\$

There would be a problem in your code for following inputs:

10
1 2 3 4 5 6 7 8 9 10
5
3 2 1 10 9

The answer which would show is NO while the answer should be 4.

This is because once flag is set to 1, the program will not move to next smallest number (here 2) but instead would print "NO".

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.