Hackwithinfyi | Infosys | OA Coding Questions and Solutions | Set - 3 | 2022

Question

Answer 1

C++ code :  O(NlogN) Time and O(1) extra space used. 

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll ; 

int main() {
    vector <int> a ; 
    int n ; 
    cin>>n ; 
    int i = 1 ; 
    while(i<=n)
    {
        int x ; 
        cin>>x ; 
        a.push_back(x);
        i++;
    }
    int k = 0 ; 
    int r = 0 ; 
    sort(a.begin(),a.end());
    i = n - 1 ; 
    while(i>=0)
    {
        int answer = a[i] - k ;
        if(answer>0)
        {
            r = r + answer ; 
        }
        k++;
        i--;
    }
    cout<<r ; 
    return 0 ; 
}

Comments

Time Complexity is NlogN
Because you are using sort function

---

Thanks for the correction :)