# 2023/02/05 Mock interview Candidate:阿呀呀
###### tags: `mock interview`
---

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="700" height="400" style="display: block; margin: 0px auto; border: 0px;" src="http://zbryikt.github.io/quick-timer"></iframe>

# 題目講解
//time: 8:43

Nancy has a huge collection of n positive integers a1, a2, · · · , an. Unfortunately, she is not
satisfied since there are duplicate integers in them.

To make Nancy happy, you can perform the following operation any number of times (possibly
zero): Select any integer ai
from a1, a2, . . . , an, and add 1 to ai
.
What is the minimum number of operations required so that all the integers in a1, a2, · · · , an
are distinct (in other words, all integers are different)

ready!!
n positive int a1, a2...an,

I think maybe i need list a example to check my idead is correct.

# 作法講解
//time: 8:45

7
3 1 4 1 5 9 2
ops = 5

first: sort the array
array = 1, 1, 2, 3, 4, 5, 9

if array[i] is equal to array[i-1], then we can know, array[i] is duplicate number with array[i-1].
and we can add 1 to array[i].
do above step for each index in array.

then we can calculate minimum operation we need.

first: sort the array

array = 1, 1, 2, 3, 4, 5, 9
i = 0, we don't do anything, because last value not exist.
i = 1, array[i] == array[i-1], min_operation = 1, array[i] = 2
array = 1, 2, 2, 3, 4, 5, 9

i = 2, array[i] (2)== array[i-1] (2), min_operation = 2
array = 1, 2, 3, 3, 4, 5, 9

i = 3, array[i] (3)== array[i-1] (3), min_operation = 3
array = 1, 2, 3, 4, 4, 5, 9

i = 4, array[i] (4)== array[i-1] (4), min_operation = 4
array = 1, 2, 3, 4, 5, 5, 9

i = 5, array[i] (5)== array[i-1] (5), min_operation = 5
array = 1, 2, 3, 4, 5, 6, 9

i = 6, we don't do anything, becaus array[i] != array[i-1]

TC: O(nlogn) SC: O(1)

1 1 1

after sorted, the array is the same as before,
1 1 1
i = 0=> 1, 1, 1
i = 1=> 1, 2, 1

i think i need to check value range to think approach.

the value range is in 10^5?
the value range is very big.

1, 3 2, 3, 3, 4
I think i have the new idea to finish it.

step 1, we can sort array,
step 2, we can build new array<pair<int,int>> val_cnt,
val_cnt first is val, second is cnt
step 3, sort val_cnt by first,

step 4, case 1: val_cnt[i] val is val_cnt[i-1] val
that means val_cnt[i] val is equal val_cnt[i-1] val + 1

add min_operation with val_cnt[i-1].cnt - 1
add val_cnt[i].cnt with val_cnt[i-1].cnt - 1
case 2: val_cnt[i] val is bigger than val_cnt[i-1] val + 1
we can put some value in range between val_cnt[i-1] val ~ val_cnt[i] val
val_cnt[i-1] cnt -= val_cnt[i] val - val_cnt[i-1] val
if val_cnt[i-1] cnt > 1
we need add min_operation with val_cnt[i-1].cnt - 1
add val_cnt[i].cnt with val_cnt[i-1].cnt - 1

1, 1, 1, 2, 2, 5,
step 1, after sorted, A = [1, 1, 1, 2, 2, 5]
step 2, val_cnt = [1, 3] [2, 2] [5, 1]

step 3 we can skip this step

step 4
i = 0, we don't do any thing
i = 1, step 4, case 1,
min_step += val_cnt[0] cnt (3) => 3 - 1 => 2

val_cnt = [1, 1] [2, 4] [5, 1]

i = 2, step 4, case 2
we can put some val into (2~5), we have two space in there,
val_cnt[i-1] cnt(4) = val_cnt[i-1] cnt - 2
=> val_cnt[i-1] cnt = 2

min_step += 1 (val_cnt[i-1] cnt - 1)
val_cnt[i] cnt += val_cnt[i-1] cnt - 1.
=> 2

final, we need last element cnt - 1
TC: O(nlogn), SC: O(n)

# coding
//time: 9:14 (+5 min)

void find_min_operation(vector<int> &nums) 
{
    int n = nums.size();
    vector<pair<int, int>> v;
    
    
    //first sort
    sort(nums.begin(), nums.end());
    
    int val = -1;
    int cnt = 0;
    int min_operation = 0;
    
    //i think i need to explain my code,
    
    //second, we build v pair<int, int>, v => val_cnt
    //we use val, cnt to record traversaled val,
    for(int i = 0 ; i < n ; i++) {
        if(val == nums[i]) {
            cnt++;
        }
        else {
            if(val >= 0) {
                v.push_back({val, cnt});
            }
            val = nums[i];
            cnt = 1;
        }
    }
    v.push_back({val, cnt});
    // v = {val, cnt}
    
    // v = {1: 6}, {4, }
    //       1,2,3
    //       1->2, 1->3  -> formula
    //
    for(int i = 1 ; i < val.size(); i++) {
        //3,  5 => res = 1
        int res = v[i].first - v[i-1].first - 1;
        //mistake!!!
        v[i-1].second -= min(res, v[i-1].second-1);
        
        min_operation += (v[i-1].second - 1);
        v[i].second += (v[i-1].second - 1);
    }
    //
    min_operation += v.back().second - 1;
    
    return min_operation;
}

# 完成
//time: 21:29

# comment
// 21:34

一開始的方向很正確
但新的case給了之後有點歪掉
方法二比較不好實作
但整體的想法是很棒的
9:20 (+10 mins)

https://codeforces.com/gym/425267/attachments/download/18909/main.pdf
第Ｎ題

講解
https://hackmd.io/@iris2617/2023pcca_editorial#/3