Skip to content

Instantly share code, notes, and snippets.

@robertpi
Created April 2, 2020 16:17
Show Gist options
  • Save robertpi/1818d79e548d1a134ec5a4d50d6164dd to your computer and use it in GitHub Desktop.
Save robertpi/1818d79e548d1a134ec5a4d50d6164dd to your computer and use it in GitHub Desktop.
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
public class Solution
{
public static void CountSort(int[] arr, int[] output, int[] count)
{
int n = arr.Length;
for (int i = 0; i < count.Length; i++)
{
count[i] = 0;
}
// store count of each character
for (int i = 0; i < n; ++i)
{
++count[arr[i]];
}
// Change count[i] so that count[i]
// now contains actual position of
// this character in output array
for (int i = 1; i < count.Length; ++i)
count[i] += count[i - 1];
// Build the output character array
// To make it stable we are operating in reverse order.
for (int i = n - 1; i >= 0; i--)
{
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
}
// Complete the activityNotifications function below.
static int activityNotifications_CountSort(int[] expenditure, int d)
{
int alerts = 0;
int[] subSection = new int[d];
int[] sortedSubSection = new int[d];
int[] count = new int[200];
int mid = d / 2;
Array.Copy(expenditure, 0, subSection, 0, d);
if (d % 2 == 0)
{
for (int i = d; i < expenditure.Length; i++)
{
subSection[d - (i % d) - 1] = expenditure[i];
CountSort(subSection, sortedSubSection, count);
int median = (sortedSubSection[mid] + sortedSubSection[mid + 1]) / 2;
if (expenditure[i] >= (median * 2))
{
alerts++;
}
}
}
else
{
for (int i = d; i < expenditure.Length; i++)
{
subSection[d - (i % d) - 1] = expenditure[i];
CountSort(subSection, sortedSubSection, count);
int median = sortedSubSection[mid];
if (expenditure[i] >= (median * 2))
{
alerts++;
}
}
}
return alerts;
}
static int activityNotifications_FirstAttempt(int[] expenditure, int d)
{
int alerts = 0;
int[] subSection = new int[d];
int mid = d / 2;
for (int i = d; i < expenditure.Length; i++)
{
Array.Copy(expenditure, i - d, subSection, 0, d);
Array.Sort(subSection);
int median;
if (d % 2 == 0)
{
median = (subSection[mid] + subSection[mid + 1]) / 2;
}
else
{
median = subSection[mid];
}
if (expenditure[i] >= (median * 2))
{
alerts++;
}
}
return alerts;
}
public static void PseduoMain(string[] args)
{
// this bit is given by HackerRank, but optimizations here will help too
var lines = File.ReadAllLines(@"C:\code\TestSorting\input01.txt");
string[] nd = lines[0].Split(' ');
int n = Convert.ToInt32(nd[0]);
int d = Convert.ToInt32(nd[1]);
string[] items = lines[1].Split(' ');
int[] expenditure = new int[items.Length];
for (int i = 0; i < items.Length; i++)
{
expenditure[i] = Convert.ToInt32(items[i]);
}
int result = activityNotifications_CountSort(expenditure, d);
Console.WriteLine("Result: " + result);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment