Alok Kumar - 5 months ago 19

C Question

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:

- do not sort the array
- 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`

`3,2`

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)