aboutsummaryrefslogtreecommitdiff
path: root/min_replacement_array.c
blob: 160f046a81781deb3d38c0af0eeb3008fde171ee (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
// 2366. Minimum Replacements to Sort the Array
#include <stdio.h>

/*
 * given a 0-indexed array 'nums'. in one operation you can replace any element
 * of the array with any two elements that sum to it.
 * - for example consider 'nums = [5,6,7]'. in one operation we can replace
 * 'nums[1]' with 2 and 4 and convert 'nums' to '[5,2,4,7]'. return the minimum
 * number of operations to make an array that is sorted in non-decreasing order.
 */

long long minimumReplacement(int *nums, int nums_size) {
  long long ans = 0;
  int max = nums[nums_size - 1], divisor;
  for (int i = nums_size - 2; i >= 0; i--) {
    if (nums[i] > max) {
      if (!(nums[i] % max))
        ans += (nums[i] / max) - 1;
      else {
        ans += (nums[i] / max);
        divisor = (nums[i] / max) + 1;
        max = nums[i] / divisor;
      }
    } else
      max = nums[i];
  }
  return ans;
}

int main() {
  int n1[] = {3, 9, 3}, n2[] = {1, 2, 3, 4, 5};
  printf("%lld\n", minimumReplacement(n1, 3)); // expect: 2
  printf("%lld\n", minimumReplacement(n2, 5)); // expect: 0
}