## Append to Divide – ICPC 2011 Amritapuri Online Round

Problem Statement:Honeydukes’ Sweet Shop has donated buckets of Bertie Bott’s Every Flavor Beans (a kind of jelly bean) to the students of Hogwarts School of Witchcraft and Wizardry, one basket per House. But when the baskets (each labeled with the House number i) were delivered to the school, it was discovered that the number of sweets in each bucket were not exactly divisible by the number of students in that house A[i], and quarrels broke out about who got the extra sweets.

Harry Potter to the rescue! Harry suggested using magic to make sure that every bucket contained a number of sweets that were exactly divisible by the number of students in the corresponding House.

Can you tell us how many sweets were in the last bucket, given the way Harry’s spell worked:Given the number of students A[i] in each of the N houses, we define the array B[0..N] as follows. Initialize B[0] = 1 and for i = 1 to N, set B[i] to the smallest integer obtained by appending one or more digits (0-9) to B[i-1] such that B[i] is divisible by A[i]. Find the value of B[N] modulo 1000000007.

Huh? Did you get the problem? If not, read through it again. It is pretty simple to understand what they want you to do. If you still can’t, here is an example:

For input 2, 3, 4 answer will be 1020. Why? Because:

A[1..3] = {2,3,4}, B[0..3] = {1, 10, 102, 1020}.

Hope you understand it now. (Call me up if you still don’t)

So how do we solve this? Well, here it is:

You start with 1 and start appending zeros. For each position i of B (starting with i>1), you check if the number formed is divisible by A[i-1] (Hence, starts with A[0]). If yes, this is the number you require for B[i]. If not, then find the modulus of the number formed with A[i-1], subtract this modulus from A[i-1], and add it to the number formed IFF the number of zeros added is less than or equal to the number of digits in the (A[i]-modulus) figure you obtained. Otherwise, add another zero to the end of the number formed earlier. Keep repeating the process and you’ll get the answer 🙂

Here is how this would work for the example specified above,

A[0..2]={2,3,4}, B[0] = 1

Now forming numbers for B[1],

appending 0 to B[0], we get 10, which is divisible by A[i-1] (2). Hence, B[1]=10

Now forming numbers for B[2],

appending 0 to B[1], we get 100, which leaves modulus = 1, And A[i]-mod=2. As number of digits (1) is less than or equal to the number of zeros added (1), add 2 to 100, which gives, B[2]=102

Similarly, for B[3]=1020. And hence the answer!

But oh wait! The question isn’t over. We had somewhat mistaken the limits assuming the answer would fit in “long long”. The limts were as follows,

**1 <= T <= 10**

**1 <= N <= 1000**

**1 <= A[i] <= 1,000,000**

If you think about it properly, your answer (before modulus 1000000007) can end up being more than 1000 digits long. Which will be difficult to handle in C/C++. Hence, we needed to use **BigInteger to solve this**. Which I did! 🙂

If you went through the solution properly, you would have understood it. 😉

*PS: I can mail the JAVA code in BigInteger if someone wants. Leave a comment with your correct email-id in the field.*

## BigInteger – Dealing with huge numbers. (Explained with factorial 500)

Alrighty! So we are deviating away a bit from algorithms but I need to write a post on this to go on to explain one of the questions from this year’s ICPC Amritapuri Online Round. I’ll be talking about BigIntegers in this one.

So tell me, what do you do when someone asks you to find the **factorial of 500**. Most of you will write a factorial program in C++ with long long as your data type and then try to run it for 500. It is then that you realize the factorial of 500 will be too large for any integer data type in C/C++. So unless you plan to store numbers in strings and manipulate then), you will have to go for BigInteger in Java or BigNum in Python. I’ll show you a simple code in Java for calculating the factorial of 500 using BigInteger (Java).

import java.lang.*;

import java.math.*;

import java.io.*;

import java.util.*;

class WhateverYourFileName{

public static void main(String args[])

{

BigInteger number = new BigInteger(“500”);

BigInteger fact = new BigInteger(“1”);

while(!number.equals(BigInteger.ZERO)

{

fact=fact.multiply(number);

number=number.subtract(BigInteger.ONE);

}

System.out.println(fact);

}

}

Yes, as simple as that! For more details about BigInteger, you can visit the documentation here. No worries about huge numbers now, eh?! Enjoy with your newfound wisdom! 🙂