Help me in solving PERMREACH problem

help
,
1

My issue

In the 4th test case in input sample 1:
6
2 1 3 4 6 5
The given output is 3. I think it is not possible to make this k-sortable and the answer should be zero, like in previous test case.

My code

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

int main() {
	// your code goes here
	int t;
	cin >> t;
	while (t--) {
	    int n;
	    cin >> n;
	    vector <int> a(n,0);
	    for (int i = 0; i < n; i++) {
	        cin >> a[i];
	    }
	    int count = 0;
	    int ref = a[0];
	    int diff = 0;
	    for (int i = 0; i < n; i++) {
	        if(a[i] >= ref) {
	            ref = a[i];
	        }
	        else{
	            diff = ref - a[i];
	            count++;
	        }
	    }
	    if (count>1) {
	        cout << 0 << endl;
	        continue;
	    }
	    int ans= 0;
	    if(diff>n){
	        cout << 0 << endl;
	        continue;
	    }
	    else{
	        for(int i = diff;i<=n;i++){
	            ans = ans + i;
	        }
	    }
	    cout << ans << endl;
	    
	}

}

Problem Link: Sort Perm Practice Coding Problem

2

@ankitanand1265
choose index 2 and 6 (considering 1 based indexing ) and add 1,2(as value of k) to them will give you increasing array .
so the answer would be 3(1+2).

1 Like