CODEWITHSUNDEEP
c#algorithmbiginteger
TheJackal
TheJackal

Reputation: 435

Dealing with large integers without BigInteger Library in Algorithm contests

Problem: Topcoder SRM 170 500

Consider a sequence {x0, x1, x2, ...}. A relation that defines some term xn in terms of previous terms is called a recurrence relation. A linear recurrence relation is one where the recurrence is of the form xn = c(k-1) * x(n-1) + c(k-2) * x(n-2) + ... + c(0) * x(n-k) where all the c(i) are real-valued constants, k is the length of the recurrence relation, and n is an arbitrary positive integer which is greater than or equal to k. You will be given a int[] coefficients, indicating, in order, c(0), c(1), ..., c(k-1). You will also be given a int[] initial, giving the values of x(0), x(1), ..., x(k-1), and an int N. Your method should return xN modulo 10.

More specifically, if coefficients is of size k, then the recurrence relation will be xn = coefficients[k - 1] * xn-1 + coefficients[k - 2] * xn-2 + ... + coefficients[0] * xn-k.

For example, if coefficients = {2,1}, initial = {9,7}, and N = 6, then our recurrence relation is xn = xn-1 + 2 * xn-2 and we have x0 = 9 and x1 = 7. Then x2 = x1 + 2 * x0 = 7 + 2 * 9 = 25, and similarly, x3 = 39, x4 = 89, x5 = 167, and x6 = 345, so your method would return (345 modulo 10) = 5.

Constraints: - Code must run in less than or equal to 2 seconds - Memory utilization must not exceed 64 MB

My attempted Solution:

class RecurrenceRelation
{

    public int moduloTen(int[] coefficients, int[] initial, int N)
    {
        double xn = 0; int j = 0;
        int K = coefficients.Length;
        List<double> xs = new List<double>(Array.ConvertAll<int, double>(initial,
        delegate(int i)
        {
            return (double)i;
        })); 
        if (N < K)
            return negativePositiveMod(xs[N]);
        while (xs.Count <= N)
        {
            for (int i = xs.Count - 1; i >= j; i--)
            {
                xn += xs[i] * coefficients[K--];
            }
            K = coefficients.Length;
            xs.Add(xn);
            xn = 0;
            j++;
        }
        return negativePositiveMod(xs[N]);
    }
    public int negativePositiveMod(double b)
    {
        while (b < 0)
        {
            b += 10;
        }
        return (int)(b % 10);
    }
}

My problem with this solution is the precision of the double representation, and since I can't use a third party library or the BigInteger library in .NET for this SRM, i need to find a way of solving it without them. I suspect I could use recursion but I'm a little clueless on how to go about that.

Here is a test case that shows when my code works and when it doesn't

{2,1}, {9,7}, 6 - Successfully returns 5 {9,8,7,6,5,4,3,2,1,0}, {1,2,3,4,5,6,7,8,9,10}, 654 - Unsuccessfully returns 8 instead of 5 due to precision of double type

Can anyone help me figure this out? I was going to consider using arrays to store the values but it is a little bit beyond me especially on how to cater for multiplication and still be within the time and space complexity set out in the problem. Perhaps my entire approach is wrong? I'd appreciate some pointers and direction (not fully fleshed out answers) answers please.

Thanks

Upvotes: 2

Views: 791

Answers (2)

shaft
shaft

Reputation: 2229

As Pham has answered, the trick is to realize that you only need to return a modulo, thereby bypassing the problem of overflow. Here is my quick attempt. I use a queue to put in the last result xN, and evict the oldest one.

    static int solve(int[] coefficients, int[] seed, int n)
    {
        int k = coefficients.Count();
        var queue = new Queue<int>(seed.Reverse().Take(k).Reverse());

        for (int i = k; i <= n; i++)
        {

            var xn = coefficients.Zip(queue, (x, y) => x * y % 10).Sum() % 10;
            queue.Enqueue(xn);
            queue.Dequeue();
        }

        return (int) (queue.Last() );

    }

Edit: Getting the same results as you expect, however I don't guarantee that there is no bug in this example.

Upvotes: 1

Pham Trung
Pham Trung

Reputation: 11294

Notice that we only need to return the modulo 10 of xn.

We also need to know that if a = b + c, we have a % 10 = (b % 10 + c % 10) %10.

And a = b*c, so we also have a % 10 = (b %10 * c % 10) % 10;

So, for 

xn = c(k-1) * x(n-1) + c(k-2) * x(n-2) + ... + c(0) * x(n-k) 
            = a0 + a1 + .... + an

(with a0 = c(k - 1)*x(n-1), a1 = ...)

we have xn % 10 = (a0 % 10 + a1 % 10 + ...)%10

And for each ai = ci*xi, so ai % 10 = (ci % 10 * xi % 10)% 10.

So by doing all of these math calculations, we can avoid to use double and keep the result in manageable size.

Upvotes: 4

Related Questions