2

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.

Improve this question
7
  • The first thing thing that popped to my mind is that if you already checked 13 * 52 and know it's 1352, you don't need to check 52 * 13 to know it's not 5213... Commented Jun 2, 2018 at 7:42
  • 1
    @ZoharPeled, yes but implementing this willn't make it slower? (because I have only two pairs of this kind of numbers ) Commented Jun 2, 2018 at 7:47
  • If I increment i by 2 (i+=2) i get the same result, so maybe it is better to use it? Commented Jun 2, 2018 at 7:48
  • 3
    Check out code review SE. Seems more fitting for this question. Commented Jun 2, 2018 at 7:55
  • 1
    This snippet of code should run almost instantly. Next time you should add an benchmark result to your question and what do you expect. Commented Jun 2, 2018 at 7:55

3 Answers 3

Reset to default
2

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);
        }
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

You are checking for example 1010, 1020, and so on, and not 1012 for example. what is the idea behind it?
@Alex - If I have the number 10 then to form a four digit number starting with 10 that is also divisible by ten I can only look at 1010, 1020, 1030, ..., 1090. There's no point in looking at 1012.
1

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.

Improve this answer

Comments

-1

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.