CODEWITHSUNDEEP
c#algorithm
user9035668
user9035668

Reputation:

Make Algorithm more efficient

Two (2 digit) numbers are written together, so they form one 4 digit number. This 4 digit number can be divided by the multiplication of this two numbers. The problem is that I have to find this numbers.

I wrote an algorithm and get 2 pair of these numbers.

1) 13 and 52, so 1352 can be divided by 13 * 52.

2) 17 and 34, so 1734 can be divided by 17 * 34.

My algorithm looks like this:

for (int i = 1010; i <= 9999; i++)
{
    int mult = (i / 100) * (i % 100);

    if ((i % 100) > 9 && i % mult == 0)
    {
        Console.WriteLine(i / 100 + " <--> " + i % 100);
    }
}

Edit: with this algorithm (based on mentallurg answer) I find this numbers a bit faster

for (int i = 10; i < 99; i++)
{
    for (int j = 10; j < 99; j++)
    {
        int mult = i * j;
        int num = i * 100 + j;

        if (num % mult == 0)
        {
           Console.WriteLine(i + " <--> " + j);
        }
    }
}

I am interested in how I can make this algorithm more efficient.

Upvotes: 2

Views: 153

Answers (3)

kennyzx
kennyzx

Reputation: 13003

Supposed one of the pairs are a and b, and so the four digits number can be expressed as 100a + b. Do a little math 

100a + b = m * a * b

Divided by a on both sides, we have 

100 + b / a = m * b

We can conclude that

  1. b can be divided by a, let's say (b == n * a);

  2. b must be greater than a, since 101 is a prime. And it cannot be 3/7/9 times of a, since 103/107/109 are also primes, but let’s neglect this to make the for loop simpler. This can be easily handled in the inner loop of the following code.

So the for loop can be written like this

for (int a = 10; a < 50; a++)
{
    for (int n = 2; n * a < 100; n++)
    {
        if ((100 + n) % (n * a) == 0)
            Console.WriteLine(a + " " + n * a);
    }
}

The number of iteration of the loop is reduced to a few dozens, from almost 10 thousand.

Upvotes: 1

Enigmativity
Enigmativity

Reputation: 117174

This is very efficient:

var query =
    from x in Enumerable.Range(10, 90)
    from n in Enumerable.Range(1, 10).TakeWhile(w => w * x < 100)
    let v = x * (100 + n)
    where v % (n * x * x) == 0
    select new { x, y = n * x };

It computes all possible first digits. It then computes all of the possible second digits that are multiples of the first digit that are greater than zero and less than 100. It then produces the a candidate value at checks if it is divisible by the product of both digits.

It gives both of the possible answers.

Here's the equivalent using for loops:

for (int x = 10; x <= 99; x++)
{
    for (int n = 1; x * n < 100; n++)
    {
        var j = x * n;
        int v = x * 100 + j;
        int d = x * j;
        if (v % d == 0)
        {
            Console.WriteLine(x + " <--> " + j);
        }
    }
}

Upvotes: 2

mentallurg
mentallurg

Reputation: 5207

Use 2 nested cycles from 1 to 99 and you will avoid two division operations on each step.

Upvotes: -1

Related Questions