How to reduce the time complexity in C regarding nested loop

May 29, 2022

The code is about determining "two distinct elements" in an integer array where the index of these two aren’t same and doing the bit-wise operation between them gives "1".

"The time to execute this following program is 500ms." But since I got a nested for loop here so I’m getting TLE. How can I modify this code in order to meet the necessary requirements.

Note that this is the only way I know how to check something in the array and I can only code in C language. The code is as follows:

#include <stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, count = 0;
        scanf("%d", &n);
        int num[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if ((num[i] ^ num[j]) == 1)
                    count = 1;
            }
        }
        count == 1 ? printf("Yes\n") : printf("No\n");
    }
    return 0;
}

>Solution :

For 2 entries in the array to match the expression (num[i] ^ num[j]) == 1, they must be at most 1 apart. You could sort the array and use a linear scan, testing only consecutive elements, reducing the time complexity from O(N²) to O(N log(N)).

Here is a modified version:

#include <stdio.h>
#include <stdlib.h>

int compare_ints(const void *aa, const void *bb) {
    const int *a = aa;
    const int *b = bb;
    return (*a > *b) - (*a < *b);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t-- > 0) {
        int n, count = 0;
        scanf("%d", &n);
        int num[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);

        qsort(num, n, sizeof(*num), compare_ints);

        for (int i = 1; i < n; i++) {
            if ((num[i] ^ num[i - 1]) == 1)
                count = 1;
                break;
            }
        }
        puts(count ? "Yes" : "No");
    }
    return 0;
}

An even more efficient version would use a hash table, adding each number in a linear scan and testing if num[i] ^ 1 is already present in the hash table. This would have a time complexity of O(N) but is more complex to write.