Given an unordered array A of size n and integer x, What is best complexity to find two elements in A whose sum is x?

Question

Given an unordered array A of size n and integer x. What is the best complexity to find two elements in A whose sum is x?
Share the algo, its complexity and if possible C code.

Answer 1

Hi! :)

Not the best I've made, but you can make it better :D. The main idea is working, but my code, of course, has some deficiencies. You can complete if if you want ;).

#include <stdio.h>
#include <limits.h>
typedef struct
{
    int a;
    int b;
    int indexA;
    int indexB;
} ret;

ret SrcSum(int Arr[], int N, int x)
{
    ret src;
    src.a = src.b = INT_MIN;
    printf("size: %d\n", N);
    int i = 0, j = 0;
    int index_a = -1, index_b = -1;

    while( i < N )
    {
        j = 0;
        while( Arr[i]+Arr[j] != x)
            j++;
        if(j<N)
        {
            src.a = Arr[i];
            src.b = Arr[j];
            src.indexA = i;
            src.indexB = j;
            break;
        }
        i++;
    }
return src;
}

void main()
{
    int size = 10;
    int t[size];
    int index;
    for( index = 0; index < size; index++)
        t[index] = index;
    int sr;
    printf("\nWhat num to search: "); scanf("%d",&sr);

    ret nums = SrcSum(t, size, sr);
    if( nums.b == INT_MIN )
        printf("\nSorry, no matches found.\n\n");
    else printf("\n%d + %d = %d, index: %d %d", nums.a, nums.b, sr, nums.indexA, nums.indexB );
}

I hope I could help you.