Unique pairs with equal sum in C

Question

The question at hand is:

Q8. Given an unsorted array A[]. The task is to print all unique pairs in the unsorted array with equal sum. Consider the Input: A[] = {6, 4, 12, 10, 22, 54, 32, 42, 21, 11}
Explain the approach of solving the above problem, and write the code in any one programming language C/C++/Python/Java. What is the time complexity of the above problem?

Here is my solution to the above problem (in C) :

#include <stdio.h>
int main(){
    int arr[]={6,4,12,10,22,54,32,42,21,11};
    int len=sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<len;i++)
        for(int j=i+1;j<len;j++)
            for(int k=i+1;k<len;k++)
                for(int l=k+1;l<len;l++)
                    if(arr[i]+arr[j]==arr[l]+arr[k])
                        printf("(%d,%d),(%d,%d)\n",arr[i],arr[j],arr[k],arr[l]);
    return 0;
}

My logic is to take one element at a time, and take its sum with every other element, and for each such iteration, compare the sum of two other unique pair of elements to it. For example, when i=0, j=3, arr[i]+arr[j]=16. When k=1,l=2, arr[k]+arr[l]=16. Since the pairs are unique (6,10) and (4,12) and their sum is equal, I print them. Note that the pairs are assumed to be unordered pairs so that (a,b) is the same as (b,a) and so we don't need to repeat that, as they have to be unique.

My question is : I know that my code is almost O(n^4). How can I improve/optimise it further?

Answer 1

Here is a Java solution:

import java.util.*;

class Duplicate {
  public static void main(String[] args) {
    
    int [] a = {5,3,1,4,5,6,3,7,0,10,6,4,9,1};
    
    List<Integer> li = new ArrayList<Integer>();
    
    int p1=0, p2=0;
    
    for(int i=0; i<a.length;i++) {
      for(int j=i+1; j<a.length;j++){
        
        if(a[i]+a[j] == 10) {
          
          p1 = a[i];
          p2 = a[j];
          
          if(!li.contains(Math.abs(p2-p1))) {
              
            li.add(Math.abs(p2-p1));
            
            System.out.println("Pairs" + ":" + p1 + "," + p2);
          }
        }
        p1=0;
        p2=0;
      }
    }
    
  }
}

Answer 2

It can be done in O(N^2 * log(N^2) * M), where M is the maximum number of pairs(i, j) that have the same sum, so in worst case it would be O(N^3 * log(N)).

Lets iterate for every pair 0 <= i,j < N in order (increasing or decreasing), we have to save the sum of all the previous pairs(i, j) (to know which previous pairs have a certain sum) this can be done with a map with a integer key and a vector of pairs for the mapped value; then for every pair(i, j) you search in the map for it's sum (key = A[i] + A[j]), then al the pairs store in map[sum] are answers to this pair(i, j).

You don't have to worry about for the following pairs to (i, j) that have the sum because the following pairs when they be processed they will count it.

Answer 3

C code for calculating all the sums and storing the sums with indexes inside an array of structures. Then we sort the structures and print adjacent structure elements with the same sum.

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <errno.h>
#include <assert.h>

// for debugging
#define debug(...)  ((void)0) // printf(__VA_ARGS__)

// two indexes and a sum
struct is_s {
    // one index inside the array
    size_t i;
    // the other index also inside the array
    size_t j;
    // no idea, must be random
    int sum;
};

// used for qsoring the struct is_s
static int is_qsort_compare_sum(const void *a0, const void *b0) {
    const struct is_s * const a = a0;
    const struct is_s * const b = b0;
    return a->sum - b->sum;
}

int unique_pairs(const size_t len, const int arr[len]) {
    if (len <= 1) return 0;
    // The number of unsorted combinations must be n!/(2!*(n-2)!)
    const size_t islen = len * (len - 1) / 2; // @MOehm
    debug("%zu\n", islen);

    struct is_s * const is = malloc(islen * sizeof(*is));
    if (is == NULL) {
        return -ENOMEM;
    }

    size_t isidx = 0;
    for (size_t i = 0; i < len; ++i) {
        for (size_t j = i + 1; j < len; ++j) {
            assert(isidx < islen); // just for safety
            struct is_s * const p = &is[isidx++];
            p->i = i;
            p->j = j;
            p->sum = arr[i] + arr[j];
            debug("[%zu]=[%zu]=%d [%zu]=%d %d\n", isidx, p->i, arr[p->i], p->j, arr[p->j], p->sum);
        }
    }

    qsort(is, islen, sizeof(*is), is_qsort_compare_sum);

    for (size_t i = 0; i < islen - 1; ++i) {
        debug("([%zu]=%d,[%zu]=%d)%d = ([%zu]=%d,[%zu]=%d)%d\n", 
            is[i].i, arr[is[i].i], is[i].j, arr[is[i].j], is[i].sum,
            is[i+1].i, arr[is[i+1].i], is[i+1].j, arr[is[i+1].j], is[i+1].sum
        );
        if (is[i].sum == is[i + 1].sum) {
            printf("(%d,%d),(%d,%d) = %d\n",
                arr[is[i].i], arr[is[i].j],
                arr[is[i+1].i], arr[is[i+1].j], is[i].sum);
        }
    }

    free(is);

    return 0;
}

int main(void) {
    const int arr[] = {6,4,12,10,22,54,32,42,21,11};
    return unique_pairs(sizeof(arr)/sizeof(*arr), arr);
}

The result I get is:

(6,10),(4,12) = 16
(10,22),(21,11) = 32
(12,21),(22,11) = 33
(22,21),(32,11) = 43
(32,21),(42,11) = 53
(12,42),(22,32) = 54
(10,54),(22,42) = 64

As I wonder if this is correct, as @Bathsheba noted, I think the worst case is O(n*n).

Answer 4

It would be easier in C++, Python, or Java because those languages provide high level containers. In Python, you could use a defaultdict(list) where the key would be the sums and the value a list of pairs giving that sum.

Then you only have to process unique pairs (N² / 2)

result = collections.defaultdict(list)
for i, a in enumerate(A):
    for b in A[i+1:]:
        result[a+b].append((a,b))

It will be slightly more complex in C because you do not have the high-level direct access dict. If you can waste some memory and only have small numbers like here, you can say that the highest sum will be less than twice the biggest number in the input array, and directly allocate an array of that size. That way you ensure direct access from a sum. From there, you just use a linked list of pairs and that is all. As a bonus you even get a sorted list of sums.

I you cannot assume that numbers are small you will have to build a direct access container. A hash type container using N*N/2 as size (N being the length of A) and sum%size as hash function should be enough.

For completeness, here is a possible C code not doing the small numbers assumption (this code displays all pairs not only the ones with duplicated sums):

#include <stdio.h>
#include <stdlib.h>

// a node in a linked list of pairs
struct pair_node {
    int first;
    int second;
    struct pair_node *next;
};

// a slot for a hash type containers of pairs indexed by their sum
struct slot {
    int number;
    struct pair_node *nodes;
    struct slot *next;
};

// utility function to find (or create) a slot for a sum
struct slot* find_slot(struct slot **slots, int size, int sum) {
    struct slot *slt = slots[sum%size];
    while (slt != NULL) {
        if (slt->number == sum) {
            return slt;
        }
        slt = slt->next;
    }
    slt = malloc(sizeof(struct slot));
    slt->number = sum;
    slt->nodes = NULL;
    slt->next = slots[sum%size];
    slots[sum%size] = slt;
    return slt;
}

int main() {
    int A[] = {6,4,12,10,22,54,32,42,21,11};  // the array of numbers
    int N = sizeof(A) / sizeof(A[0]);

    int arr_size = N * N / 2;   // size of the hash table of pairs
    struct slot** result = malloc(arr_size * sizeof(struct slot *));
    for (int i=0; i<arr_size; i++) {
        result[i] = NULL;
    }

    // process unique pairs
    for (int i=0; i<N-1; i++) {
        for (int j=i+1; j<N; j++) {
            int sum = A[i] + A[j];
            // allocate and initialize a node
            struct pair_node *node = malloc(sizeof(*node));
            node->first = A[i];
            node->second = A[j];

            // store the node in the hash container
            struct slot *slt = find_slot(result, arr_size, sum);
            node->next = slt->nodes;
            slt->nodes = node;
        }
    }

    // display the result
    for (int i=0; i<arr_size; i++) {
        for (struct slot* slt=result[i]; slt != NULL;) {
            printf("%d :", slt->number);
            struct pair_node *node = slt->nodes;
            while(node != NULL) {
                printf(" (%d,%d)", node->first, node->second);
                node = node->next;
                free(node);                // free what has been allocated
            }
            printf("\n");
            struct slot *old = slt;
            slt = slt->next;
            free(old);
        }
    }
    free(result);
    return EXIT_SUCCESS;
}

Answer 5

FIrst you precompute the sum of each pair and keep the result in a matrix PAIRSUM.

PAIRSUM(0, 0) = 12
PAIRSUM(0, 1) = 10 a s o

Next, you loop over the PAIRSUM and see where 2 entries are similar.

So you reduced the big problem to a smaller one, in which you check the equality of 2 numbers, not of 2 sums of numbers.

For this you keep a vector PAIR in which at index X you keep the entries in PAIRSUM where the sum was X.

For example, PAIR(10) = { {0, 1} }.

You can also consider in PAIRSUM only the matrix above the diagonal, so for which the indexes (i,j) have i>j.