Help me in solving MEXARR problem

help
,
1

My issue

hii everyone,

can anyone explain me the logic to solve this question

My code

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    int cost = 0;

    int data;
    vector < int > arr(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    sort(arr.begin(), arr.end());
    for(int i = 0; i < n;i++) {
        cost+= abs(arr[i] - i);
    }
    cout<<cost<<endl;
}

int main() {
    // your code goes here
    int t;
    cin >> t;

    while (t--) {
        solve();
    }
}

Problem Link: MEXimize the Array Practice Coding Problem - CodeChef

2

Change the data type “int” to “long long”. Otherwise, integer overflow may occur. For your convenience, consider an array like {1, 1, 1, …, 100000}. Think now.

1 Like
3

At worst, we could’ve had an array of N = 200,000 made out of only ‘1’
So your “cost” variable will be 1.999*(10^10), overflowing your int that only can store numbers up to 10^9 (moreless)

Try always using long long in every problem.

1 Like
4

thnks buddy, i have solved it after the contest

1 Like