How to reduce the time complexity in C regarding nested loop

Question

The code is about determining "two distinct elements" in an integer array where the index of these two aren't the 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, I'm getting TLE. How can I modify this code to meet the 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;
}

chqrlie · Accepted Answer · 2022-05-29 12:25:37Z

3

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.

edited May 29, 2022 at 12:25

answered May 29, 2022 at 11:13

chqrlie

152k12 gold badges145 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Nazmus Sakib Sibly Over a year ago

I think you missed some syntax error in the code but after getting rid of the bug it worked. the modified code is : ... ... ... ... ... ... for (int i = 1; i < n; i++) { if ((num[i] ^ num[i - 1]) == 1){ count = 1; break; } } puts(count ? "Yes" : "No"); } return 0; }

Nazmus Sakib Sibly Over a year ago

Is there any special purpose writing while(t-- > 0) instead of while(t--) ?

chqrlie Over a year ago

@NazmusSakibSibly: yes, while (t-- > 0) avoids the pathological case where t is negative. I actually like to write while (t --> 0) but it is not idiomatic and frowned upon here.

Nazmus Sakib Sibly Over a year ago

Can you clarify this statement how is it working ? puts(count ? "Yes" : "No"); As far as I know it would first check a condition and then execute. But I can't see any visible condition here

chqrlie Over a year ago

@NazmusSakibSibly: the condition is count, implicitly evaluated as count != 0, the ternary operator determines which argument is passed to puts, either "Yes"` is count != 0 or "No" otherwise.

Collectives™ on Stack Overflow

How to reduce the time complexity in C regarding nested loop

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related