Simple Minded Hashing

All of you know a bit or two about hashing. It involves mapping an element into a numerical value using some mathematical function. In this problem we will consider a very ‘simple minded hashing’. It involves assigning numerical value to the alphabets and summing these values of the characters.

For example, the string “acm” is mapped to 1 + 3 + 13 = 17. Unfortunately, this method does not give one-to-one mapping. The string “adl” also maps to 17 (1 + 4 + 12). This is called collision.

In this problem you will have to find the number of strings of length L, which maps to an integer S, using the above hash function. You have to consider strings that have only lowercase letters in strictly ascending order.

Suppose L = 3 and S = 10, there are 4 such strings.

  1. abg
  2. acf
  3. ade
  4. bce

agb also produces 10 but the letters are not strictly in ascending order.

bh also produces 10 but it has 2 letters.

Input

There will be several cases. Each case consists of 2 integers L and S(0 < L, S < 10000). Input is terminated with 2 zeros.

Output

For each case, output Case #: where # is replaced by case number. Then output the result. Follow the sample for exact format. The result will fit in 32 bit signed integers.

Sample Input Output for Sample Input
3 10
2 3
0 0
Case 1: 4
Case 2: 1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string charSet = "abcdefghijklmnopqrstuvwxyz";
            int stringLength = 3;
            int collisionSum = 10;
            int counter = 0;
            int maxLimit = (int)Math.Pow(2, charSet.Length) - 1;
            for (int i = 1; i <= maxLimit; i++)
            {
                string binary = Convert.ToString(i, 2);
                if (NumberOfOnes(binary) == stringLength)
                {
                    int charSum = 0;
                    string combination = "";
                    binary = binary.PadLeft(charSet.Length, '0');
                    for (int j = 0; j < binary.Length; j++)
                    {
                        if (binary[j] != '0')
                        {
                            combination = combination + charSet[j];
                            charSum = charSum + j + 1;
                            if (charSum > collisionSum)
                            {
                                break;
                            }
                        }
                    }
                    if (charSum == collisionSum)
                    {
                        Console.WriteLine(combination);
                        counter++;
                    }
                }
            }
            Console.WriteLine("Number of collision = " + counter);
        }
        public static int NumberOfOnes(string num)
        {
            int count = 0;
            for (int i = 0; i < num.Length; i++)
            {
                if (num[i] == '1')
                {
                    count++;
                }
            }
            return count;
        }
    }
}
Output:
==============================
bce
ade
acf
abg
Number of collision = 4
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s