anushkanocoding's blog

TESTCASE DOUBT
By anushkanocoding, history, 3 months ago, In English

import java.util.*; public class balanced { public static void main(String[]args){ java.util.Scanner sc=new java.util.Scanner(System.in); int t=sc.nextInt(); for(int i=0;i<t;i++){ int n=sc.nextInt(); int k=sc.nextInt(); int []arr=new int[n]; for(int j=0;j<arr.length;j++){ arr[j]=sc.nextInt(); }

int ops=0;
        Arrays.sort(arr);
        int a=0;
        int b=1;
        while(b<arr.length){ 
            if(arr[b]-arr[b-1]>k){
                int leftNums=b-a;
                int rightNums=arr.length-b;

                if(leftNums<rightNums){
                    a=b;
                    ops+=leftNums;
                }else if(leftNums>=rightNums){
                    ops+=rightNums;
                    break;
                }
            }
            b++;
        }
        System.out.println(ops);
    }
}

} For Question 1850D-BALANCED ROUND Can anyone please tell me what the problem is with the code? It Fails on TestCase 409 i cant see the particular testcase (also can we actually see particular testcases? if not, how is one supposed to know which testcase is wrong?

  • Vote: I like it
  • -24
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Logic is pretty simple for this question. take in array of length 'n', sort the array, find length 'len' of the longest subarray without violating the condition of 'difference <=k' and you got your answer 'n-len'.

here is the code


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

int main() {
    int t; 
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> v(n);
        
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        
        sort(v.begin(), v.end());
        
        int maxLen = 0, currLen = 1;
        
        for (int i = 1; i < n; i++) {
            if (v[i] - v[i-1] <= k) {
                currLen++;
            } else {
                maxLen = max(maxLen, currLen);
                currLen = 1;
            }
        }
        
        maxLen = max(maxLen, currLen);
        
        cout << n - maxLen << endl;
    }

    return 0;
}

time complexity is O(nlogn) due to sorting.

→ Reply