Alok Kumar Alok Kumar - 1 month ago 6
C Question

Printing pairs which matches the user defined sum number in C programming language

Well I'm involving myself taking on challenges in coding and I'm doing it. I have one more thing that came up during my journey. I've been doing a code in which problem statement goes like this:


You have been provided an unsorted array and a sum by the user. What you have to do is to make a pair of those elements which equals to the user defined sum.
For example:

Input given:

Enter some array: 3 1 2 4
Enter the sum: 5


Output:

The pairs are:
1,4
3,2



I have already done this successfully in my code and getting the desired result. The code is here:

#include<stdio.h>
//global function to call for sorting purpose
void bubbleSort(int*, int);

void main() {
int a[10];
int arr_size;
int sum, k;

//input the sum which has to be totalled to
printf("Please enter a number that the pairs should total to:");
scanf(" %d", &sum);

printf("Please enter the size of the array:");
scanf(" %d", &arr_size);

printf("Please enter as many numbers to run the program on:");
for (k = 0; k < arr_size; k++)
scanf("%d", &a[k]);

printf("Pairs to be totalled to: %d", sum);

printf("\nPairs found: \n");

//this funtion sorts the unsorted array to increasing order
bubbleSort(a, arr_size);

//this is used as pointers i.e., *l and *r
int l = 0;
int r = arr_size - 1;

//this loop will run until l becomes >= r
while (l < r) {

//if the element at lth position in the array a[] when added
//to rth position of a[] equals to sum
if (a[l] + a[r] == sum) {
printf("%d,%d\n", a[l], a[r]);
l++; //l is incremented after doing the operation
r--; //r is decremented by one after doing the operation
}
//if the sum is smaller then sum
else if (a[l] + a[r] < sum)
l++; //only l is incremented and points to the next one
//operation is done again

//if a[l]+a[r]>sum then
else
r--; //r is decremented and then compared again
}
getch();
}

void bubbleSort(int a[], int arr_size) {
int i, j, temp = 0;

//the i pointer remains at 0th position and run upto n-1
for (i = 0; i < arr_size; i++) {
//the j pointer is also at 0th position but runs upto arr_size-i-1 for comparison
for (j = 0; j <arr_size - i - 1; j++) {
if (a[j] > a[j + 1]) {
//meant for swapping the values only
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}


Now here is the challenge what I'll have to do:


  1. do not sort the array

  2. do not do it with nested loop



for which what I did was:

#include <stdio.h>

int main() {

int a[10], i, l = 1, r, arr_size, sum;

printf("Enter the size of an array:");
scanf(" %d", &arr_size);

printf("Enter the required sum of an array:");
scanf("%d", &sum);

printf("Enter the array:");
for (i = 0; i < arr_size; i++)
scanf(" %d", &a[i]);

r = arr_size;

while (l <= r || l >= r) {
if (a[l] + a[r] == sum) {
printf("%d,%d\n", a[l], a[r]);
l++;
r--;
} else
if (a[l] + a[r] < sum) {
l++;
} else
r--;
}
return 0;
}


Here the output is coming in a very ambiguous manner.

The output of the new above code

You can see that clearly
5,0
came up unknowingly and
3,2
is not given.
I'll be glad if someone would help me with this, I'm close to the result.

Answer Source

I would do this without nested loops and sorting in the following way:

  • Keep the current element index constant until

    a) searching index has reached the upper limit

    int l=0, r=1;// l is the index of the element in array and r searches for its compliment
    
    
    while(l<(arr_size-1)){// increment current element index upto array size-2
    
        if(a[l]+a[r]==sum){
            printf("%d,%d\n",a[l],a[r]);
    
            r++; //increment r however
        }
    
        else{
            r++;//keep l constant until the complement is found or r is equal to array size
        }
            if(r==arr_size){
               l++;
               r=l+1;
            }
        }
    }
    

Time Complexity= (n(n-1))/2==> O(n^2)




Alternate solution with better time complexity

Let sum be 5

  • Let original array be int a.

  • Make a complement array of numbers <=sum.

  • Make a bool array which will have value at indices contained in complement array as true.

Let array a be

int a={-1,2,3,4,6}

Implies complement array will be:

int comp={6,3,2,1}

And bool array will be

bool check={0,1,1,1,0,0,1}

if a[i]>=0 and bool[a[i]] is equal to 1, this implies complement exist else no!

#include<stdio.h>
#include<stdbool.h>
#define MAX 100// this means that max compliment of a number could be 100, which is the limitation


int main() {

    int a[10], i, l = 1, r, arr_size, sum;

    printf("Enter the size of an array:");
    scanf(" %d", &arr_size);

    printf("Enter the required sum of an array:");
    scanf("%d", &sum);

    printf("Enter the array:");
    for (i = 0; i < arr_size; i++)
        scanf(" %d", &a[i]);

    int k=0;
    int comp[10]={0};
    int j=0;
    for(i=0;i<arr_size;i++){
        if(a[i]<=sum){ //only check for elements lesser or equal to sum, do not take higher elements
            if(a[i]==sum/2 && k==0){// if only one instance of half sum value exists do not consider it
                k++;//this means that there is at least one instance of half sum value(if sum=6 reaching this line would mean at least one 3 exists)

            }
            else{
                comp[j]=sum-a[i];//comp array will contain the complements of elements <= sum
                j++;
            }

        }
    }

    bool check[MAX]={false};

    for(i=0;i<j;i++){
        check[comp[i]]=true;// make only those indices true whose value is contained in complement array
    }




    for(i=0;i<arr_size;i++){
        if(a[i]>=0){
            if(check[a[i]]==true){
                printf("\n%d %d\n",a[i],sum-a[i]);
                check[sum-a[i]]=false;//to remove redundancy
                check[a[i]]=false;//to remove redundancy
            }
        }
    }


    return 0;
}

Time complexity: O(n)