Skip to content

Instantly share code, notes, and snippets.

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/a5b94d6b1bd61aca13bb488badc31805 to your computer and use it in GitHub Desktop.
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
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