design an algorithm to determine whether there exists such a key which is equal to the summation of other two keys in the array

Question

i'm trying to solve this problem: given an array containing n keys determine whether there exists such a key that is equal to sum of other two keys in array. if yes, print them out. I'm using mergesort to sort the array and then checking for keys. but (for loop) inside summation function somehow fails to increment every time. i've tried (while loop) and several other ways. nothing works. any ideas?

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

void merge_sort(int input_array[], int first_element, int last_element);
void merge(int input_array[], int first_element, int middle_element,
           int last_element);
void find_summation(int input_array[], int first_element, int last_element);

int total_elements;
int main() {
  int input_array[100];
  printf("\nEnter number of elements in the array : ");
  scanf("%d", &total_elements);

  int i = 0;
  printf("\nEnter %d array elements: ", total_elements);
  while (i < total_elements) {
    scanf("%d", &input_array[i]);
    i++;
  }
  merge_sort(input_array, 0, total_elements - 1);

  printf("\nSorted Array: ");
  for (int i = 0; i < total_elements; i++) {
    printf("%d ", input_array[i]);
  }

  printf("\n");
  find_summation(input_array, 0, total_elements - 1);
  printf("\n");
  return 0;
}

void find_summation(int input_array[], int first_element, int last_element) {
  bool found;

  last_element = total_elements - 1;
  int j = 2;
  int current_num;

  for (int j = 2; j <= last_element;) {
    current_num = input_array[j];
    while ((first_element < last_element)) {
      int a = input_array[first_element];
      int b = input_array[last_element];
      int summation = a + b;
      printf("summation %d\n", summation);
      if (summation == current_num) {
        found = true;

      } else if (summation > current_num) {
        last_element--;

      } else if (summation < current_num) {
        first_element++;
      }
      if (found) {
        printf("\nKey: %d > sum of Keys: %d & %d", current_num, a,
               current_num - a);
        break;
      }
    }
  }
}

void merge(int input_array[], int first_element, int middle_element,
           int last_element) {
  int m = (middle_element - first_element) + 1;
  int n = last_element - middle_element;

  int left_array[m];
  int right_array[n];

  for (int i = 0; i < m; i++) {
    left_array[i] = input_array[first_element + i];
  }

  for (int j = 0; j < n; j++) {
    right_array[j] = input_array[(middle_element + 1) + j];
  }

  int i = 0, j = 0, k = 0;
  k = first_element;
  while (i < m && j < n) {
    if (left_array[i] <= right_array[j]) {
      input_array[k] = left_array[i++];

    } else {
      input_array[k] = right_array[j++];
    }
    k++;
  }

  while (i < m) {
    input_array[k++] = left_array[i++];
  }

  while (j < n) {
    input_array[k++] = right_array[j++];
  }
}

void merge_sort(int input_array[], int first_element, int last_element) {
  if (first_element < last_element) {
    int middle_element = (first_element + last_element) / 2;

    merge_sort(input_array, first_element, middle_element);
    merge_sort(input_array, middle_element + 1, last_element);

    merge(input_array, first_element, middle_element, last_element);
  } else
    return;
}

Answer 1

Thank you everyone for guidance and support. Finally got the code to work on all the cases. original code had a lot of mistakes. including control flow and logical errors. i have fixed the code now. solution is posted below: Test Case: 18 23 4 35 99 67 198 20 38 55 2 19 487 11 40 10 13 27 22

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

void merge_sort(int input_array[], int first_element, int last_element);
void merge(int input_array[], int first_element, int middle_element,
           int last_element);
void find_summation(int input_array[], int first_element, int last_element);
int binary_search(int input_array[], int first_element, int last_element,
                  int difference);


int main() {
  int total_elements;
  int input_array[100];
  printf("\nEnter number of elements in the array : ");
  scanf("%d", &total_elements);

  int i = 0;
  printf("\nEnter %d array elements: ", total_elements);
  while (i < total_elements) {
    scanf("%d", &input_array[i]);
    i++;
  }
  merge_sort(input_array, 0, total_elements - 1);

  printf("\nSorted Array: ");
  for (int i = 0; i < total_elements; i++) {
    printf("%d ", input_array[i]);
  }

  printf("\n");
  find_summation(input_array, 0, total_elements);
  printf("\n");
  return 0;
}

void find_summation(int input_array[], int first_element, int last_element) {
  for (int j = 0; j <= last_element; j++) {
    int current_num = input_array[j];

    // printf("current_num and j: %d %d\n", current_num, j);

    for (int i = 0; i < j; i++) {
      int element = input_array[i];
      int element_found =
          binary_search(input_array, first_element, j, (current_num - element));

      if (element_found > 0) {
        if (element != (current_num - element))
          printf("\nKey: %d > sum of Keys: %d & %d", current_num, element,
                 current_num - element);

      }  
    }    
  }
}
int binary_search(int input_array[], int first_element, int last_element,
                  int difference) {
  bool found;
  int current_num;

  int middle_element = (first_element + last_element) / 2;
  if ((last_element >= first_element) && (first_element < middle_element)) {
    // int middle_element = (first_element + last_element) / 2;
    /*
        while ((last_element - first_element) <= 2) {
          return binary_search(input_array, middle_element + 1, last_element,
                               difference);
        }*/
    if (input_array[middle_element] == difference) {
      return middle_element;
    }

    if (input_array[middle_element] > difference) {
      return binary_search(input_array, first_element, middle_element - 1,
                           difference);
    }

    return binary_search(input_array, middle_element + 1, last_element,
                         difference);
  }
  return -1;
}
void merge(int input_array[], int first_element, int middle_element,
           int last_element) {
  int m = (middle_element - first_element) + 1;
  int n = last_element - middle_element;

  int left_array[m];
  int right_array[n];

  for (int i = 0; i < m; i++) {
    left_array[i] = input_array[first_element + i];
  }

  for (int j = 0; j < n; j++) {
    right_array[j] = input_array[(middle_element + 1) + j];
  }

  int i = 0, j = 0, k = 0;
  k = first_element;
  while (i < m && j < n) {
    if (left_array[i] <= right_array[j]) {
      input_array[k] = left_array[i++];

    } else {
      input_array[k] = right_array[j++];
    }
    k++;
  }

  while (i < m) {
    input_array[k++] = left_array[i++];
  }

  while (j < n) {
    input_array[k++] = right_array[j++];
  }
}

void merge_sort(int input_array[], int first_element, int last_element) {
  if (first_element < last_element) {
    int middle_element = (first_element + last_element) / 2;

    merge_sort(input_array, first_element, middle_element);
    merge_sort(input_array, middle_element + 1, last_element);

    merge(input_array, first_element, middle_element, last_element);
  } else
    return;
}