Factorial frequencies

In an attempt to bolster her sagging palm-reading business, Madam Phoenix has decided to offer several numerological treats to her customers. She has been able to convince them that the frequency of occurrence of the digits in the decimal representations of factorials bears witness to their futures. Unlike palm-reading, however, she can’t just conjure up these frequencies, so she has employed you to determine these values.

Recall that the definitions of n! is 1*2 …*n. As she expects to use either the day of the week, the day of the month, or the day of the year as the value of n, you must be able to determine the number of occurrences of each decimal digit in numbers as large as 366 factorial (366!), which has 781 digits.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DigitFrequency
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Console.Write("Enter a positive integer: ");
                int inputNum = int.Parse(Console.ReadLine());
                int[] num = new int[800];
                int[] count = new int[10];
                num[799] = 1;
                for (int mul = 1; mul <= inputNum; mul++)
                {
                    num = multiply(num, mul);
                }
                //Determine the first non zero element in num array
                int i = 0;
                for (i = 0; i < num.Length; i++)
                {
                    if (num[i] != 0)
                    {
                        break;
                    }
                }
                //Display the array elements
                while (i <= 799)
                {
                    Console.Write(num[i]);
                    count[num[i]]++;
                    i++;
                }
                Console.WriteLine();
                for (i = 0; i < count.Length; i++)
                {
                    Console.WriteLine(i + " –> " + count[i]);
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
        }
        public static int[] multiply(int[] num, int mul)
        {
            int[] carry = new int[800];
            int[] prod = new int[800];
            int i = 0, j = 0, temp = 0;
            //Determine the first non zero element in num array
            for (i = 0; i < num.Length; i++)
            {
                if (num[i] != 0)
                {
                    break;
                }
            }
            //Perform element wise multiplication
            for (j = 799; j >= i; j–)
            {
                temp = (mul * num[j]) + carry[j];
                prod[j] = temp % 10;
                carry[j – 1] = (temp – prod[j]) / 10;
            }
            //Prefix carry to the product
            while (carry[j] != 0)
            {
                prod[j] = carry[j] % 10;
                carry[j-1] = (carry[j] – prod[j]) / 10;
                j–;
            }
            return prod;
        }
    }
}

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