aboutsummaryrefslogtreecommitdiff
path: root/min_num_opp_arr_cont.c
blob: 053a3022a8d5932ae6fae9d1ee9c40c4e009c836 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 2009. Minimum Number of Operations to Make Array Continuous
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * you are given an integer array 'nums'. in one operation, you can replace any
 * element in 'nums' with any integer. 'nums' is considered continuous if both
 * of the following conditions are fulfilled:
 * - all elements in 'nums' are unique
 * - the difference between the maximum element and the minimum element in
 * 'nums' equals 'nums.len - 1' return the minimum number of operations to make
 * 'nums' continuous.
 */

int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int minOperations(int *nums, int nums_size) {
  int n = nums_size, idx = 1, ans = INT_MAX, j = 0;
  qsort(nums, n, sizeof(int), cmp);
  int *arr = malloc(n * sizeof(int));
  arr[0] = nums[0];
  for (int i = 1; i < n; i++)
    if (nums[i] != nums[i - 1]) {
      arr[idx] = nums[i];
      idx++;
    }
  for (int i = 0; i < idx; i++)
    while (j < idx && arr[j] - arr[i] + 1 <= n) {
      ans = fmin(ans, n - (j - i + 1));
      j++;
    }
  return ans;
}

int main() {
  int n1[] = {4, 2, 5, 3}, n2[] = {1, 2, 3, 5, 6}, n3[] = {1, 10, 100, 1000};
  printf("%d\n", minOperations(n1, 4)); // expect: 0
  printf("%d\n", minOperations(n2, 5)); // expect: 1
  printf("%d\n", minOperations(n3, 4)); // expect: 3
}