anushkanocoding's blog

TESTCASE DOUBT
By anushkanocoding, history, 3 hours 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
  • -17
  • Vote: I do not like it

»
111 minutes 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
  • »
    »
    98 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes thank you i understood this solution. But i want to figure out why my solution wont work. And I unfortunately cant find the testcase where it gives the wrong output.

    → Reply