Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 7, 2017 22:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/7a8a335b47aaf8483740c90390399bf1 to your computer and use it in GitHub Desktop.
Save jianminchen/7a8a335b47aaf8483740c90390399bf1 to your computer and use it in GitHub Desktop.
Hackerearth simple function - cannot pass last test case
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