3
\$\begingroup\$

Problem statement

Let us first describe a SimpleFunction:

SimpleFunction( string A,string B ){ 

   int answer = 0;    
   for( int dig = 1; dig <= 9; dig++ ){    
        if(string A contains digit dig and string B contains digit dig){    
            answer = answer * 10 + dig;    
   }    
   return answer;
}

So basically this function receives two strings as an input and returns a value.

Akshara recently gained interest in coding and she came across this interesting question. She had 2 baskets. Each basket contained a few strings. She wanted to find out what is the probability of picking up 2 strings, 1st string from the first basket and the 2nd string from the second basket, such that the value returned from the Simple function would be an even value.

Since she is not that good at Mathematics, she turns to you for help. Please help her in solving this problem!

Input: The first line contains an integer \$T\$ denoting the number of test cases. The first line of each test case contains 2 integers \$N1\$ and \$N2\$ denoting the size of first basket and second basket respectively. This is followed up by \$(N1 + N2)\$ lines. Each line contains a string. The first \$N1\$ string correspond to the first basket while the remaining to the second basket.

Output:

For each test case output the required probability correct up to 3 decimal places.

Constraints:

  • \$1 \le T \le 10\$
  • \$1 \le N1, N2 \le 1000\$
  • \$1 \le \text{Length of String} \le 1000\$

Every String is composed of digits from [1 - 9]

Sample input

1
2 2
234526
8345
333564
98847675

Sample output

0.750

Explanation

The output of all the combination will be:

Simple(234526,333564) = 3456
Simple(8345,333564) = 345
Simple(8345,98847675) = 458
Simple(234526,98847675) = 456

Since 3 of them are even, probability is \$\frac{3}{4}\$.

Time Limit: 1.0 sec(s) for each input file.

Memory Limit: 256 MB

My introduction of the algorithm:

I asked the code review for my previous solution HackerEarth - SimpleFunction, and then the feedback is "The code is hard to follow". Afterwards, I spent a few hours to work on the algorithm again, rewrite and passed all test code, and code is much simple. Here is the code link.

I learned a few lessons through the practice. Most of important is to use counting sort to find two integers' (\$1 <= N <= 1000\$) last digit, avoid using time-consuming string manipulation. And also, avoid complicated code, jagged array with 3 dimension seems to be hard to follow in my previous solution. Most of important is that the time complexity is very easy to compute \$O(N1*N2)\$, \$N1, N2\$ are two integers in two baskets, both are less than \$1000\$. The algorithm uses less memory, time is almost same as the previous one.

The current algorithm's result on hackerearth

enter image description here

The previous algorithm's result on hackerearth.com

enter image description here

I like to ask review again for the same algorithm.

   using System;
   using System.Collections.Generic;
   using System.Diagnostics;
   using System.Linq;
   using System.Text;
   using System.Threading.Tasks;

   namespace SimpleFunction
   {
      /*
       * Hackerearth.com simple function
       * https://www.hackerearth.com/problem/algorithm/simple-function/
       */
     class Program
     {
       /*
        * Use an integer array to express an integer from 1 to 1000, array size is 10. 
        * Store digit i from 1 to 9 if there is any digit i in the integer. 
        * 
        * For example, a number from 1 to 1000, 246 will be represented as int[]{0,0,1,0,1,0,1,0,0,0}.
        * 
        * Design of hashed integer: 
        * 1. Number of same digits in the integer will not be saved, the information will be losted, for example, 
        * integers 1, 11, 111 will be saved to same array {0,1,0,0,0,0,0,0,0,0}
        * 
        * 2. And also the order does not matter, 123, 213, 321 will be hashed to same array {0,1,1,1,0,0,0,0,0}
        */
       internal class HashedInteger
       {
          private static int SIZE = 10; 
          public int[] values; 

          public HashedInteger()
          {
            values = new int[SIZE]; 
          }

          /*
           * @number - a string representing an integer from 1 to 1000, 
           */
          public static HashedInteger Convert(string number)
          {                
            HashedInteger digits = new HashedInteger();
            foreach (char c in number)
            {
                digits.values[ c- '0'] = 1;
            }

            return digits;
          }

          public static HashedInteger[] ConvertAll(string[] numbers)
          {
            if (numbers == null || numbers.Length == 0)
                return new HashedInteger[] { };

            int length = numbers.Length;
            IList<HashedInteger> output = new List<HashedInteger>();
            foreach (string number in numbers)
            {
                output.Add(HashedInteger.Convert(number));
            }

            return output.ToArray();
          }      

          /*              
           * Find largest digit in two numbers expressed in Digits
           * 
           * return: last digit
           */
          public static int GetLastDigit(HashedInteger firstOne, HashedInteger 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;
       }

       /*
        * Sample test case in problem description
        */
       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;
        Debug.Assert((prob.ToString("#.000").CompareTo("0.750")) == 0);
      }

      /*
       * return value: probablity of even numbers compared to total pairs
       */
      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"));
        }
      }

     /*
      * 
      * Choose any number from each basket, compare two numbers to find largest digit in both numbers. 
      * If the largest digit is the even number, then add to the sum. Ruturn the value of sum of largest digit
      * of a pair number from two baskets. 
      */
      private static int CalculateSumOfEvenNumbers(string[] numbersA, string[] numbersB)
      {
        int count = 0;

        HashedInteger[] shortNumbers1 = HashedInteger.ConvertAll(numbersA);
        HashedInteger[] shortNumbers2 = HashedInteger.ConvertAll(numbersB);

        foreach (HashedInteger firstOne in shortNumbers1)
        {
            foreach (HashedInteger secondOne in shortNumbers2)
            {                    
                int lastDigit = HashedInteger.GetLastDigit(firstOne, secondOne);

                if (lastDigit % 2 == 0)
                    count++;
            }
        }

        return count;
      }                              

      private static int CalculateTotalCount(string[] numbersInFirst, string[] numbersInSecond)
      {
        return numbersInFirst.Length * numbersInSecond.Length;
      }
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ There is a misunderstanding regarding the constraints: not the single number that each digit string could be interpreted as is limited by 1≤N1,N2≤1000. The count of digit strings in basket1 is N1 (1, at least, and 1000, at most), the same limits apply to N2, the count of digit strings in basket2. (That and the fact that you keep all strings before turning them into sets may be responsible for the memory usage of Input #1.) \$\endgroup\$ – greybeard Jan 8 '17 at 22:52
  • \$\begingroup\$ @greybeard, you are correct. I read problem statement again, the string length is in range of [1,1000]. Sample test case string in basket 1 are 234526 and 8345, both are more than 3 digits. Good catch! \$\endgroup\$ – Jianmin Chen Jan 9 '17 at 0:07
  • \$\begingroup\$ @gretbeard, the class HashedInteger's description has to be updated, ""Use an integer array to express an integer from 1 to 1000, array size is 10. Store digit i from 1 to 9 if there is any digit i in the integer.", should be written "Use an integer array to express a string with length from 1 to 1000 containing digits from 1 to 9, and the integer array size is 10. Store digit i from 1 to 9 if there is any digit i in the string." \$\endgroup\$ – Jianmin Chen Jan 9 '17 at 0:11
  • \$\begingroup\$ string with length from 1 to 1000 sure closely follows the wording from the original problem statement. I'd avoid Use [X] to express [Y] where X cannot be reconstructed from Y. Store digit i from 1 to 9 isn't quite what is happening - (record, denote,) represent absence of digit i with a zero at index i, its presence with a non-zero value (one/1?)? See my answer to the first iteration of your question for a representation of each basket using no more than 512 integers for any number of digit strings (and time complexity O(1) +O(n) input: "online algorithm"). \$\endgroup\$ – greybeard Jan 9 '17 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.