QUESTION DOUBT

Revision en1, by anushkanocoding, 2024-10-08 22:18:43

Click Here for the question

this solution is wrong for testcase 2 can someone please tell me why

import java.util.*;
public class B_Collecting_Game{
    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();
            
            long [][]arr=new long[n][2];
            
            long []prefix=new long[n];
            for(int j=0;j<n;j++){
                arr[j][0]=sc.nextLong();
                arr[j][1]=j;
            }
            Arrays.sort(arr, (a, b) -> Long.compare(a[0], b[0]));
            prefix[0]=arr[0][0];
            for(int j=1;j<n;j++){
                prefix[j]=arr[j][0]+prefix[j-1];
            }
            long []answer=new long[n];

            for(int index=0;index<arr.length-1;index++){
                if(prefix[index]<arr[index+1][0]){
                    answer[(int)arr[index][1]]=index;
                }
                else{
                    int left=index+1;
                    int right=arr.length-1;
                    int couldBe=index;
                    while(left<=right){
                        int mid = left + (right - left) / 2;


                        if(arr[mid][0]<=prefix[mid-1]){
                            couldBe=mid;
                            left=mid+1;
                        }
                        else{
                            right=mid-1;
                        }
                    }
                    answer[(int)arr[index][1]]=couldBe;
                }
            }
            answer[(int)arr[arr.length-1][1]]=arr.length-1;
            for(int j=0;j<answer.length;j++){
                System.out.print(answer[j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English anushkanocoding 2024-10-08 22:18:43 1993 Initial revision (published)