CODEWITHSUNDEEP
cfor-loop
user14278719
user14278719

Reputation:

I want 2 for loop -> 1 for loop C

I am solving algorithm problem.

It is elements in array, pair -> one value;

I input array's size and add value.

i solve this problem but i meet time complexity problem at biggggg number - n

how can i solve this time complexity problem?

i try to solve one for loop but can't well

plz help me

#include <stdio.h>

int main(void){
    int n,m,i,j;
    int count=0;
    scanf("%d %d",&n, &m);
    int array[n];
    for(i=0;i<n;i++){
        scanf("%d",&array[i]);
    }
    for(i=0;i<n;i++){
        for(j=i;j<n;j++){
            if(m==array[i]+array[j]){
                count++;
        }}
    }
    printf("%d",count);
    return 0;
}

Upvotes: 0

Views: 68

Answers (1)

Damien
Damien

Reputation: 4864

Here is a simple two-pointer technique, after sorting.
It will work as it is because there is no duplicate.

In practice, two indices are used, one from the start of the array, one from the end of the array. We increase the first or decrease the second one, depending on the value of the sum.

Complexity: O(n logn) for sorting, and O(n) for the second step.

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

int compare_ints(const void* a, const void* b)
{
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;
 
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}

int count_sum (int* A, int n, int target) {
    int count = 0;
    qsort(A, n, sizeof(int), compare_ints);
    int left = 0;
    int right = n-1;
    
    while (left < right) {
        int sum = A[left] + A[right];
        if (sum == target) {
            count++;
            left++;
            right--;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return count;
}

int main() {
    int A[] = {8, 2, 7, 5, 3, 1};
    int target = 10;
    int n = sizeof(A)/sizeof(A[0]);
    
    int ans = count_sum (A, n, target);
    printf ("count = %d\n", ans);
    
    return 0;
}

Upvotes: 1

Related Questions