Cetiri

Question

https://open.kattis.com/problems/cetiriopen.kattis.com

Solution

Idea

This is basically a math problem.

1. Sort the array using any sorting algorithm you like

2. Find the correct common difference: This is done by first finding the difference between first two elements (first_diff) and the difference between the last two elements (last_diff). Note that either one of them will be the correct common difference for this arithmetic progression.

   1. If first_diff == last_diff, that means both of them are the correct common difference.

   2. If first_diff > last_diff, that means the second element is missing, and it should be the third element minus last_diff, which is the correct common difference.

   3. If first_diff < last_diff, that means the third element is missing, and it should be the second element plus the first_diff, which is the correct common difference.

Code

https://github.com/mendax1234/Coding-Problems/blob/main/kattis/cetiri/cetiri.c

#include <stdio.h>

void swap(int a[], int tar, int src)
{
  int temp = a[tar];
  a[tar] = a[src];
  a[src] = temp;
}

void bubble_pass(int last, int a[])
{
  for (int i = 0; i < last; i += 1)
  {
    if (a[i] > a[i+1])
    {
      swap(a, i, i+1);
    }
  }
}

void bubble_sort(int n, int a[n])
{
  for (int last = n - 1; last > 0; last -= 1)
  {
    bubble_pass(last, a);
  }
}

int find_missing(int n, int a[n])
{
  int first_diff = a[1] - a[0];
  int last_diff = a[2] - a[1];
  if (first_diff == last_diff)
  {
    return a[2] + last_diff;
  }
  if (first_diff > last_diff)
  {
    return a[1] - last_diff;
  }
  return a[1] + first_diff;
}

int main()
{
  int a[3] = { 0 };
  for (int i = 0; i < 3; i += 1)
  {
    scanf("%d", &a[i]);
  }
  bubble_sort(3, a);
  int missing = find_missing(3, a);
  printf("%d\n", missing);
}