Alok Kumar - 1 year ago 40
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.

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.

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)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download