aboutsummaryrefslogtreecommitdiff
path: root/create_sorted_arr_instr.c
blob: 2a3624d49f50a37ab713500c49953c4f01c119be (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
43
44
45
46
47
48
49
50
51
// 1649. Create Sorted Array through Instructions
#include "leetcode.h"

/*
 * given an integer array 'instructions', you are asked to create a sorted array
 * from the elements in 'instructions'. you start with an empty container
 * 'nums'. for each element from left to right in 'instructions', insert it into
 * 'nums'. the cost of each insertion is the minimum of the following: the
 * number of elements currently in 'nums' that are strictly less than
 * 'instructions[i]', the number of elements currently in 'nums' that are
 * strictly greater than 'instructions[i]'. return the total cost to insert all
 * elements from 'instructions' into 'nums'. since the answer may be large,
 * return it modulo 10^9 + 7
 */

static int arr[10001];

void update(int x) {
  while (x < 10001) {
    arr[x]++;
    x += x & -x;
  }
}

int get(int x) {
  int res = 0;
  while (x > 0) {
    res += arr[x];
    x -= x & -x;
  }
  return res;
}

int createSortedArray(int *instructions, int instructionsSize) {
  memset(arr, 0, sizeof(arr));
  int ans = 0, mod = 1e9 + 7;
  for (int i = 0; i < instructionsSize; i++) {
    ans =
        (ans + fmin(get(instructions[i] - 1), i - get(instructions[i]))) % mod;
    update(instructions[i]);
  }
  return ans;
}

int main() {
  int i1[] = {1, 5, 6, 2}, i2[] = {1, 2, 3, 6, 5, 4},
      i3[] = {1, 2, 3, 3, 2, 4, 2, 1, 2};
  printf("%d\n", createSortedArray(i1, ARRAY_SIZE(i1))); // expect: 1
  printf("%d\n", createSortedArray(i2, ARRAY_SIZE(i2))); // expect: 3
  printf("%d\n", createSortedArray(i3, ARRAY_SIZE(i3))); // expect: 4
}