Finding the multiples in form of 0 and 1

Question

I was trying to solve http://poj.org/problem?id=1426 (2002 dhaka regional) . Though I was not able to come up with the exact algorithm required but as n varied from 1 to 200 I precomputed all the values by generating binary numbers and checking for divisibility. Now I have a constant time algorithm :) but I am sure this is not the correct approach for the problem. I don't want use graph search algos as this problem was under basic math in a site so I think there must be a mathematical solution to this problem which does not give TLE.

Answer 1

It's a simple trick on the remainder.

Having to write every multiple with only 0 and 1, means that you want a multiple that is sum of some powers of 10, that means x=\sum{10^a(i)} for some {a(i)}. To find the proper index we want to keep, you must remember that, being a multiple of a number n means that x mon n = 0.

So, it's all about writing the powers of 10 mod n, and find a subset which sum is 0 mod n. Let's try with 19:

Num -> Num mod 19
1 -> 1
10 -> 10
10^2 -> 5
10^3 -> 12
10^4 -> 6
10^5 -> 3

now, we can see that 10^1 + 10^4 + 10^5 = 19 that is 0 mod 19, so our solution is 110010 . To find the reminder mod 19 you don't have to calculate every single power, you just can multiply the previous value mod 19 per 10, and then calculate the module.

For instance, 10^4 mod 10 = 10^3 * 10 mod 19 = 12*10 mod 19 = 6 , that is way easier than calculate 10^4 (maybe it's not for small powers, but imagine having to calculato 100^100 before making it mod 19).

EDIT

The only problem left is find a subset that sums to 0 mod n, assuming such a subset exist.

EDIT

Ok, I have got the idea that works up to n = 200 and solve the problem on linear time. Basically, you exploit the fact that sums mod n sooner or later will overlap. This is true because of hte pigeot principle, BUT in the specific case, having only 100 integers, having it working is just a mere case. Anyway, given the list of reminders calculated as shown before, you start calculatin the partial sums. If you meet a value that you already had, you have the solution (i-1 1's followed by j 0). If you meet a reminder 0, you are as well done.

Here is the C# code I've written to test it:

for (int n = 2; n <= 200; n++)
{
    int[] reminder = new int[100];
    reminder[0] = 1;
    for (int i = 1; i < 100; i++)
    {
        reminder[i] = (10 * reminder[i - 1]) % n; 
    }
    var lst = reminder.Select((x, y) => new TenPower { Reminder = x, Pow = y })
        .ToList();

    bool cont = true;
    for (int i = 1; (i < 100)&&cont; i++)
    {
        if (lst[i].Reminder == 0)
        {
            cont = false;
            Console.WriteLine(n +" :: " + Math.Pow(10, lst[i].Pow));
        }
        else
        {
            lst[i].Reminder = (lst[i].Reminder + lst[i - 1].Reminder) % n;
            if (lst[i].Reminder == 0)
            {
                cont = false;
                Console.WriteLine(n + " :: " + Math.Pow(10, lst[i].Pow));
            }
            for (int j = i - 1; (j > 0) && cont; j--)
            {
                if (lst[i].Reminder == lst[j].Reminder)
                {
                    cont = false;
                    Console.Write(n + " :: ");
                    for (int k = 0; k < i - j; k++)
                    {
                        Console.Write("1");
                    }
                    for (int k = i - j-1; k < i; k++)
                    {
                        Console.Write("0");
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}