Given problem statment
HackerLand National Bank has a simple policy for warning clients about possible fraudulent account activity. If the amount spent by a client on a particular day is greater than or equal to 2 X the client’s median spending for a trailing number of days, they send the client a notification about potential fraud. The bank doesn’t send the client any notifications until they have at least that trailing number of prior days’ transaction data.
Given the number of trailing days d and a client’s total daily expenditures for a period of n days, determine the number of times the client will receive a notification over all n days.
constrains
- 1 <= n <= 2 x 10 power 5
- 1 <= d <= n
- 0 <= expenditure[i] <= 200
Explanation
Use count sort as other sorting methods will cause a timeout on bigger test cases.
Link to the problem on hackerrank
Solution in java
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int d = sc.nextInt();
boolean isEven = true;
if (d % 2 != 0)
isEven = false;
int warning_count = 0;
int[] expenditure = new int[n];
for (int i = 0; i < n; i++) {
expenditure[i] = sc.nextInt();
}
int[] data = new int[201];
for (int i = 0; i < d; i++) {
data[expenditure[i]]++;
}
for (int i = d; i < expenditure.length; i++) {
double median_double = 0;
if (isEven) {
int m1 = -1;
int m2 = -1;
int count = 0;
for (int j = 0; j < data.length; j++) {
count += data[j];
if (m1 < 0 && count >= d / 2) {
m1 = j;
}
if (m2 < 0 && count >= d / 2 + 1) {
m2 = j;
break;
}
}
median_double = m1 + m2;
} else {
int count = 0;
for (int j = 0; j < data.length; j++) {
count += data[j];
if (count > d / 2) {
median_double = j * 2;
break;
}
}
}
if (expenditure[i] >= median_double) {
warning_count++;
}
data[expenditure[i]]++;
data[expenditure[i - d]]--;
}
System.out.println(warning_count);
sc.close();
}
}