HackerRank Fraudulent Activity Notifications problem solution

In this HackerRank Fraudulent Activity Notifications Interview preparation kit you have Given the number of trailing days d and a client’s total daily expenditures for a period of n days, find and print the number of times the client will receive a notification over all n days.

Problem solution in Python programming.

from bisect import bisect_left, insort_left

n, d = map(int, input().split())
t = list(map(int, input().split()))
noti = 0

lastd = sorted(t[:d])
def med():
    return lastd[d//2] if d % 2 == 1 else ((lastd[d//2] + lastd[d//2-1])/2)

for i in range(d, n):
    if t[i] >= 2*med():
        noti += 1
    del lastd[bisect_left(lastd,t[i-d])]
    insort_left(lastd, t[i])
print(noti)

Problem solution in Java Programming.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main implements Runnable {

    int[] cnt;

    int med(int d) {
        int[] a = Arrays.copyOf(cnt, cnt.length);
        int r = d / 2;
        if (d % 2 == 1) {
            r++;
        }
        int res = 0;
        boolean odd = d % 2 == 1;
        for (int k = 0; k <= 200; k++) {
            while (r > 0 && a[k] > 0) {
                a[k]--;
                r--;
            }
            if (r == 0) {
                res += k;
                if (d % 2 == 0) {
                    d--;
                    r++;
                    if (a[k] > 0) {
                        return 2 * k;
                    }
                } else {
                    break;
                }
            }
        }
        return res * (odd ? 2 : 1);
    }

    void solve() throws IOException {
        int n = nextInt();
        int d = nextInt();
        cnt = new int[201];
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        for (int i = 0; i < d; i++) {
            cnt[a[i]]++;
        }
        int res = 0;
        for (int i = d; i < n; i++) {
            int m = med(d);
            //out.println(m);
            if (a[i] >= m) {
                res++;
            }
            cnt[a[i - d]]--;
            cnt[a[i]]++;
        }
        out.print(res);

    }

    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

    public void run() {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);

            solve();
            br.close();
            out.flush();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(123);
        }
    }

    String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String s = br.readLine();
            if (s == null)
                return null;
            st = new StringTokenizer(s);
        }
        return st.nextToken();
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static void main(String[] args) {
        new Thread(new Main()).start();
    }
}

Problem solution in C++ programming.

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

#define MAXE 210

int A[200010];
int F[MAXE];

int median2(int D) {
  int p = 0;
  for (int i = 0; i < MAXE; i++) {
    p += F[i];
    if (p * 2 > D) {
      return 2 * i;
    } else if (p * 2 == D) {
      for (int j = i + 1; ; j++) {
        if (F[j]) {
          return i + j;
        }
      }
    }
  }
  return -1;
}

int main() {
  int N, D;
  cin >> N >> D;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  int result = 0;
  for (int i = 0; i < N; i++) {
    if (i >= D) { 
      if (A[i] >= median2(D)) {
        ++result;
      }
      F[A[i - D]]--;
    }
    F[A[i]]++;
  }
  cout << result << endl;
  return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int compfunc(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int findPos (int *arr, int len, int val) {
    if (val >= *(arr+len-1))
        return len-1;
    if (val <= *arr)
        return 0;
    int dis = len/2;
    int pos = dis-1;
    while (dis > 1) {
        dis = (dis+1)/2;
        if (*(arr+pos) > val)
            pos -= dis;
        else if (*(arr+pos) < val)
            pos += dis;
		else return pos;
    }
    return pos;
}

void removeAndAdd(int *arr, int len, int val1, int val2) {
    int pos1 = findPos(arr, len, val1);
    int pos2 = findPos(arr, len, val2);
    if (pos1 < pos2)
        memmove(arr+pos1, arr+pos1+1, (pos2-pos1)*sizeof(int));
    else if (pos1 > pos2)
        memmove(arr+pos2+1, arr+pos2, (pos1-pos2)*sizeof(int));
    *(arr+pos2)=val2;
}

int main() {
    int n, d;
    scanf("%d %d", &n, &d);
    
    int *arr = (int *) calloc(n, sizeof(int));
    int *arrcpy = (int *) calloc(d, sizeof(int));
    int counter=0;

    for (int i=0; i<d; i++)
        scanf("%d", arr+i);

    memcpy(arrcpy, arr, d*sizeof(int));
    qsort(arrcpy, d, sizeof(int), compfunc);

    for (int i=d; i<n; i++) {
        int medianx2;
        scanf("%d", arr+i);
        medianx2 = *(arrcpy+(d-1)/2) + *(arrcpy+(d-1)/2+(d+1)%2);
        if (*(arr+i) >= medianx2)
            counter++;

        removeAndAdd(arrcpy, d, *(arr+i-d), *(arr+i));
    }
    printf("%dn", counter);
        
    return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
    var arrIn = input.split('n');
    var currLine = 0;
    var TOTAL = 0, MEDIAN = 1;
    var days = arrIn[currLine++].split(' ').map(function(x) { return parseInt(x); });
    var numFraudDays = days[MEDIAN];
    var exps = arrIn[currLine++].split(' ').map(function(x) { return parseInt(x); });
    var notifs = 0;
    var compare_fn = function(a, b) {
        return a - b;
    };
    //console.log(days);
    //console.log(exps);
    
    var expDays = [...exps.slice(0, days[MEDIAN])];
    expDays.sort(function(a, b) { return a - b; });
    //console.log(expDays);
    //console.log('....TESTING....');
    
    for ( let i = days[MEDIAN]; i < days[TOTAL]; ++i ) {
        //process.stdout.write('old expDays=');
        //console.log(expDays);
        
        // get median for even
        let med = 0;
        if ( numFraudDays % 2 === 0 ) {
            med = (expDays[days[MEDIAN]/2] + expDays[(days[MEDIAN]/2)-1]);
        // get median for odd
        } else {
            med = expDays[Math.trunc(days[MEDIAN]/2)]*2;
        }
        
        // test if this day is greater than median and get notified
        if ( exps[i] >= med ) {
            notifs++;
//            if ( days[MEDIAN] % 2 === 0 ) {
//                console.log('med['+days[MEDIAN]/2+','+(days[MEDIAN]/2-1)+']=('+
//                    expDays[days[MEDIAN]/2]+' + '+expDays[(days[MEDIAN]/2)-1]+
//                    ')/2 = '+med);
//            } else {
//                console.log('med['+Math.floor(days[MEDIAN]/2)+']='+
//                    expDays[Math.floor(days[MEDIAN]/2)]); 
//            }
            //console.log('med='+med+', i='+i+', exps[i]='+exps[i]);
            //console.log('notifs='+notifs);
            //process.stdout.write('new expDays=');
            //console.log(JSON.stringify(expDays));
            //console.log('');
        }
        
        // update expDays, no need to sort... binary search where the new number goes
        // remove the last val of the original 
        var index = binarySearch(expDays, exps[i-numFraudDays], compare_fn);
        expDays.splice(index, 1);
        
        let val = exps[i];
        if ( val <= expDays[0] ) {
            expDays.unshift(val);
        } else if ( val > expDays[expDays.length-1] ) {
            expDays.push(val);
        } else {
            // binary search where to put new value
            let result = binarySearch(expDays, val, compare_fn);
            //console.log('val='+val+', result='+result);

            if ( result >= 0 ) {
                // value was found, insert into index result
                expDays.splice(result, 0, val);
            } else {
                // value wasn't found, insert into -m -1 return from binarySearch
                expDays.splice(-(result+1), 0, val);
            }
        }
        //console.log('med='+med+', i='+i+', exps[i]='+exps[i]);
        //console.log('notifs='+notifs);
        //process.stdout.write('new expDays=');
        //console.log(expDays);
        //console.log('');
    }
    console.log(notifs);
}

function binarySearch(ar, el, compare_fn) {
    var m = 0;
    var n = ar.length - 1;
    while ( m <= n ) {
        var k = ( n + m ) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if ( cmp > 0 ) {
            m = k + 1;
        } else if ( cmp < 0 ) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});