Fraudulent Activity Notifications

  • + 0 comments

    import java.io.; import java.util.; import java.util.stream.*;

    class Result {

    public static int activityNotifications(List<Integer> expenditure, int d) {
        int notifications = 0;
        int[] count = new int[201]; // expenditure[i] <= 200
    
        for (int i = 0; i < d; i++) {
            count[expenditure.get(i)]++;
        }
    
        for (int i = d; i < expenditure.size(); i++) {
            double median = getMedian(count, d);
            if (expenditure.get(i) >= 2 * median) {
                notifications++;
            }
    
            // Slide the window
            count[expenditure.get(i - d)]--;
            count[expenditure.get(i)]++;
        }
    
        return notifications;
    }
    
    private static double getMedian(int[] count, int d) {
        int sum = 0;
        if (d % 2 == 1) {
            int mid = d / 2 + 1;
            for (int i = 0; i < count.length; i++) {
                sum += count[i];
                if (sum >= mid) return i;
            }
        } else {
            int mid1 = d / 2;
            int mid2 = mid1 + 1;
            int m1 = -1, m2 = -1;
            for (int i = 0; i < count.length; i++) {
                sum += count[i];
                if (sum >= mid1 && m1 == -1) m1 = i;
                if (sum >= mid2) {
                    m2 = i;
                    break;
                }
            }
            return (m1 + m2) / 2.0;
        }
        return 0;
    }
    

    }

    public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().trim().split(" ");
        int n = Integer.parseInt(firstMultipleInput[0]);
        int d = Integer.parseInt(firstMultipleInput[1]);
    
        List<Integer> expenditure = Arrays.stream(bufferedReader.readLine().trim().split(" "))
            .map(Integer::parseInt)
            .collect(Collectors.toList());
    
        int result = Result.activityNotifications(expenditure, d);
    
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
    
        bufferedReader.close();
        bufferedWriter.close();
    }
    

    }