C Program to Find Four Elements Whose Sum is Equal to S

  • Write a program to find four numbers whose sum is equal to given number.
  • How to find four array elements whose sum id equal to S.

Given an integer array of size N and an integer S. We have to find four elements whose sum is S. There may be multiple set of four numbers whose sum is S but we have to print only one such set.
For Example :

Input Array : 3 7 1 9 15 14 6 2 5 7
S = 24
Output : 3, 7, 9, 5
We can solve this problem in multiple ways. Here we are going to discuss two approaches of O(n4) and O(n3) time complexity.

Let inputArray be an integer array of size N and we want to find 4 elements whose sum is equal to S.

Brute Force Method : O(n4)
  • Using four loops, generate all possible combinations of four elements and array and check if their sum is equal to S.
Time Complexity : O(n4)

C program to find four array elements whose sum is equal to given number.

#include <stdio.h>

/* This function prints four elements whose sum is equal to SUM */
void getFourElementSum(int *array, int size, int SUM) {
    /* Using four for loop, generate all possible combinations 
    of four elements and array and check if their 
    sum is equal to SUM */
    int i, j, k, l;
    
    for(i = 0; i < size-3; i++) {
     for(j =i+1; j < size-2; j++){
         for(k = j+1; k < size-1; k++){
                for(l=k+1; l<size; l++){
                   if(array[i] + array[j] + array[k] + array[l] == SUM){
                     /* Found four elements whose sum is equal to SUM */
                     printf("%d, %d, %d, %d\n", array[i],array[j],array[k],array[l]);
                     return;
                   }
                }
            }
        }
    }
    printf("Not Found\n");
}
 
int main() {
    int array[10] = {3, 7, 1, 9, 15, 14, 6, 2, 5, 7};
    getFourElementSum(array, 10, 24);
    return 0;
}
Output
3, 7, 9, 5
By Sorting Input Array : O(n3)
  • Sort inputArray using any O(nLogn) time complexity algorithm like quick sort or merge sort.
  • Using two for loops, fix first two elements. Let it is be A and B.
  • Now, we have to find two elements whose sum is equal to S-(A+B).
  • We will use the second method of this post to find two number of a sorted array whose sum is equal to S-(A+B).
Time Complexity : O(n3)
#include <stdio.h>
#include <stdlib.h>

/* This function will be used as a comparator 
function by qsort function */
int compare(const void* one, const void* two) {
    return *(int*)one > *(int*)two;
}

/* This function prints four elements whose sum is equal to SUM */
void getFourElementSum(int *array, int size, int SUM) {
    int left, right, i, j, remainingSum;
    /* sort input array */
    qsort(array, size, sizeof(int), compare);
 
    /* Fix two elements using two for loops  */
    for (i = 0; i < size-3; i++) {
        for (j = i+1; j < size-2; j++){
            /* Now this problem reduceto problem of finding
            a pair in a sorted array(from index j+1 to size-1) 
            whose sum is equal to SUM-array[i]-array[j] */
            left = j+1;
            right = size-1;
            remainingSum = SUM - array[i] - array[j];
 
            while(left < right) {
                if(array[left] + array[right] == remainingSum) {
                   printf("%d, %d, %d, %d\n", array[i], array[j],
                        array[left], array[right]);
                   return;
                } else if (array[left] + array[right] < remainingSum) {
                    left++;
                } else {
                    right--;
                }
            } 
        } 
    }
}
 
int main() {
    int array[10] = {3, 7, 1, 9, 15, 14, 6, 2, 5, 7};
    getFourElementSum(array, 10, 15);
    return 0;
}
Output
3, 1, 5, 6
Posted by
Labels: ,