Created
January 8, 2017 02:14
-
-
Save jianminchen/a5b94d6b1bd61aca13bb488badc31805 to your computer and use it in GitHub Desktop.
HackerEarth simple function - study code - using int[] to store integer number with digits, instead of building a substring without duplicate digit/ ascending order
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 | |
{ | |
internal class Digits | |
{ | |
public int[] values; | |
public Digits() | |
{ | |
values = new int[10]; | |
} | |
/* | |
* 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 | |
*/ | |
public static Digits Save(string number) | |
{ | |
Digits digits = new Digits(); | |
foreach (char c in number) | |
{ | |
digits.values[ c- '0'] = 1; | |
} | |
return digits; | |
} | |
/* | |
* 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 | |
*/ | |
public static int GetLastDigit(Digits firstOne, Digits secondOne) | |
{ | |
int lastDigit = 0; | |
for (int i = 9; i >= 0; i--) | |
{ | |
if (firstOne.values[i] == 1 && secondOne.values[i] == 1) | |
{ | |
lastDigit = i; | |
break; | |
} | |
} | |
return lastDigit; | |
} | |
} | |
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 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; | |
Digits[] shortNumbers1 = PreprocessStrings(numbersA); | |
Digits[] shortNumbers2 = PreprocessStrings(numbersB); | |
foreach (Digits firstOne in shortNumbers1) | |
{ | |
foreach (Digits secondOne in shortNumbers2) | |
{ | |
int lastDigit = 0; | |
lastDigit = Digits.GetLastDigit(firstOne, secondOne); | |
if (lastDigit % 2 == 0) | |
count++; | |
} | |
} | |
return count; | |
} | |
/* | |
* preprocess the string array, and then, prepare for cache - | |
* avoid time out - cache the string | |
*/ | |
private static Digits[] PreprocessStrings(string[] numbers) | |
{ | |
if (numbers == null || numbers.Length == 0) | |
return new Digits[] { }; | |
int length = numbers.Length; | |
IList<Digits> output = new List<Digits>(); | |
foreach (string number in numbers) | |
{ | |
output.Add(Digits.Save(number)); | |
} | |
return output.ToArray(); | |
} | |
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