Created
January 7, 2017 22:38
-
-
Save jianminchen/7a8a335b47aaf8483740c90390399bf1 to your computer and use it in GitHub Desktop.
Hackerearth simple function - cannot pass last test case
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace SimpleFunction | |
{ | |
class Program | |
{ | |
public static Dictionary<string, HashSet<int>> digitsDict = new Dictionary<string, HashSet<int>>(); | |
static void Main(string[] args) | |
{ | |
ProcessInputs(); | |
//RunSampleTestCase(); | |
} | |
private static int RunSampleTestCase2() | |
{ | |
return 0; | |
} | |
private static void RunSampleTestCase() | |
{ | |
int[] baskets = new int[]{2,2}; | |
int numberInFirstBasket = baskets[0]; | |
int numberInSecondBaseket = baskets[1]; | |
string[] numbersInFirst = new string[]{"234526","8345"}; | |
string[] numbersInSecond = new string[] { "333564", "98847675" }; | |
//int count = CalculateSumOfEvenNumbers(numbersInFirst, numbersInSecond); | |
int count = CalculateSumOfEvenNumbers(numbersInFirst, numbersInSecond); | |
int totalCount = CalculateTotalCount(numbersInFirst, numbersInSecond); | |
double prob = count * 1.0 / totalCount; | |
Console.WriteLine(prob.ToString("#.000")); | |
} | |
private static void ProcessInputs() | |
{ | |
int queries = Convert.ToInt32(Console.ReadLine()); | |
for (int no = 0; no < queries; no++) | |
{ | |
int[] baskets = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); | |
int numberInFirstBasket = baskets[0]; | |
int numberInSecondBaseket = baskets[1]; | |
string[] numbersInFirst = new string[numberInFirstBasket]; | |
string[] numbersInSecond = new string[numberInSecondBaseket]; | |
for (int i = 0; i < numberInFirstBasket; i++) | |
numbersInFirst[i] = Console.ReadLine(); | |
for (int i = 0; i < numberInSecondBaseket; i++) | |
numbersInSecond[i] = Console.ReadLine(); | |
int count = CalculateSumOfEvenNumbers(numbersInFirst, numbersInSecond); | |
int totalCount = CalculateTotalCount(numbersInFirst, numbersInSecond); | |
double prob = count * 1.0 / totalCount; | |
Console.WriteLine(prob.ToString("N3")); | |
} | |
} | |
/* | |
* use this version | |
* Choose any number from each basket, compare two numbers using digits, descreasing order, | |
* 9, 8, ..., to 0, if found one, then stop, if the digit is even number, then add one. | |
* Otherwise, skip | |
*/ | |
private static int CalculateSumOfEvenNumbers(string[] numbersA, string[] numbersB) | |
{ | |
int count = 0; | |
string[] shortNumbers1 = PreprocessStrings(numbersA); | |
string[] shortNumbers2 = PreprocessStrings(numbersB); | |
foreach (string firstOne in shortNumbers1) | |
foreach (string secondOne in shortNumbers2) | |
{ | |
int lastDigit = 0; | |
lastDigit = GetLastDigit(firstOne, secondOne); | |
if (lastDigit % 2 == 0) | |
count++; | |
} | |
return count; | |
} | |
private static string GetKey(string s1, string s2) | |
{ | |
return (s1.CompareTo(s2) <= 0) ? (s1 + "-" + s2) : (s2 + "-" + s1); | |
} | |
/* | |
* warning: string should be preprocessed first. | |
* | |
* string length <= 1000, and >=1 | |
* Every string is composed of digits from [1-9] | |
* if two number, 345 and 357, | |
* then number is 35, return last digit 5; | |
* To save time, only check first digit matching in two numbers, using decreasing order | |
* | |
* @firstOne - string should be processed by function - PreprocessStrings() first. | |
* @secondOne - preprocessed first | |
* | |
* return: last digit | |
*/ | |
private static int GetLastDigit(string firstOne, string secondOne) | |
{ | |
int lastDigit = 0; | |
HashSet<int> setOne = GetDigits(firstOne); | |
HashSet<int> setTwo = GetDigits(secondOne); | |
int[] numbers = new int[]{9,8,7,6,5,4,3,2,1}; | |
foreach(int digit in numbers) | |
{ | |
if(setOne.Contains(digit) && setTwo.Contains(digit)) | |
{ | |
lastDigit = digit; | |
break; | |
} | |
} | |
return lastDigit; | |
} | |
/* | |
* preprocess the string array, and then, prepare for cache - | |
* avoid time out - cache the string | |
*/ | |
private static string[] PreprocessStrings(string[] numbers) | |
{ | |
if (numbers == null || numbers.Length == 0) | |
return new string[] { }; | |
int length = numbers.Length; | |
IList<string> output = new List<string>(); | |
foreach(string number in numbers) | |
{ | |
output.Add(RemoveDuplicatesAndSort(number)); | |
} | |
return output.ToArray(); | |
} | |
/* | |
* 112233 -> 321 | |
* spec: | |
* 1. String is short, not duplicate digit 1 - 9 | |
* 2. String is in descending order, big digit is in the left side of small digt | |
* if string contains 1 and 2, then string should be 21, not 12 | |
*/ | |
private static string RemoveDuplicatesAndSort(string number) | |
{ | |
HashSet<int> output = GetDigits(number); | |
int[] numbers = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 }; | |
StringBuilder simpleString = new StringBuilder(); | |
foreach (int digit in numbers) | |
{ | |
if (output.Contains(digit) ) | |
{ | |
simpleString.Append((char)(digit + '0')); | |
} | |
} | |
return simpleString.ToString(); | |
} | |
/* | |
* Test case: | |
* 1112233, | |
* output: 321 | |
* minimum length is 1, "1" or "9" | |
* maximum lenght is 9, "987654321" | |
*/ | |
private static HashSet<int> GetDigits(string number) | |
{ | |
if (digitsDict.ContainsKey(number)) | |
return digitsDict[number]; | |
HashSet<int> digits = new HashSet<int>(); | |
for (int i = 0; i < number.Length; i++ ) | |
{ | |
int current = number[i] - '0'; | |
if (digits.Count >= 9) | |
break; | |
digits.Add(current); | |
} | |
digitsDict.Add(number, digits); | |
return digits; | |
} | |
private static int CalculateTotalCount(string[] numbersInFirst, string[] numbersInSecond) | |
{ | |
return numbersInFirst.Length * numbersInSecond.Length; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment