using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; using System.Threading.Tasks; using System.IO; using System.Xml; using System.Text.RegularExpressions; public interface ICodeRush { int? FindLeastFrequentNumber(IList list); } public class Solution : ICodeRush { public int? FindLeastFrequentNumber(IList list) { if (list == null || list.Count == 0) { return null; } CountMap map = new CountMap(list.Count); for (int index = 0; index < list.Count; ++index) { // Only need to call increment here // The data structure is customized to initialize to 1 if not found // Reduces the amount of hashing required int current = list[index]; map.Increment(current); } int smallest = 0; int smallestVal = int.MaxValue; for (int index = 0; index < map.entries.Length; ++index) { var current = map.entries[index]; if (current.value < smallestVal) { // If we ever find a count of 1, it will be the minimum, so return here if (current.value == 1) { return current.key; } else if (current.value != 0) { smallest = current.key; smallestVal = current.value; } } } return smallest; } ///

/// This is a stripped down version of the .NET Dictionary class optimized for this task. /// The .NET Dictionary code used was found here: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs /// This is not suitable for general usage. It cannot resize like a normal Dictionary, /// Nor can you modify or insert custom values - it only inserts 1 or increments. /// class CountMap { internal const Int32 HashPrime = 101; public static readonly int[] primes = { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369}; public struct Entry { public int hashCode; public int next; public int key; public int value; } private IEqualityComparer comparer; private int[] buckets; public Entry[] entries; private int count; public CountMap(int capacity) { Initialize(capacity); } public void Increment(int index) { int hashCode = comparer.GetHashCode(index) & 0x7FFFFFFF; int target = hashCode % buckets.Length; for (int i = buckets[target]; i >= 0; i = entries[i].next) { if (entries[i].hashCode == hashCode && entries[i].key == index) { ++entries[i].value; return; } } Add(index, 1, hashCode, target); } private void Add(int key, int value, int hashCode, int targetBucket) { int index = count; count++; entries[index].hashCode = hashCode; entries[index].next = buckets[targetBucket]; entries[index].key = key; entries[index].value = value; buckets[targetBucket] = index; } private void Initialize(int capacity) { int size = GetPrime(capacity); buckets = new int[size]; entries = new Entry[size]; for (int i = 0; i < buckets.Length; i++) { buckets[i] = -1; } comparer = EqualityComparer.Default; } private static int GetPrime(int min) { for (int i = 0; i < primes.Length; i++) { int prime = primes[i]; if (prime >= min) return prime; } for (int i = (min | 1); i < Int32.MaxValue; i += 2) { if (IsPrime(i) && ((i - 1) % HashPrime != 0)) return i; } return min; } private static bool IsPrime(int candidate) { if ((candidate & 1) != 0) { int limit = (int)Math.Sqrt(candidate); for (int divisor = 3; divisor <= limit; divisor += 2) { if ((candidate % divisor) == 0) return false; } return true; } return (candidate == 2); } } }