0
\$\begingroup\$

This is a programming problem:

Write a program that finds and displays all pairs of 5-digit numbers that between them use the digits 0 through 9 once each, such that the first number divided by the second is equal to an integer N so that:

abcde / fghij = N

where each letter represents a different digit. The first digit of one of the numerals is allowed to be zero.

Input

Each line of the input file consists of a valid integer N. An input of zero is to terminate the program.

Output

Your program have to display ALL qualifying pairs of numerals, sorted by increasing numerator (and, of course, denominator). Your output should be in the following general form:

xxxxx / xxxxx = N

xxxxx / xxxxx = N

In case there are no pairs of numerals satisfying the condition, you must write "There are no solutions for N.". Separate the output for two different values of N by a blank line.

This keeps giving me TLE. How can I speed it up?

#include <iostream>
#include <algorithm>

using namespace std;


int i[10] = {0,1,2,3,4,5,6,7,8,9};

int check(int helper, int n)
{
    int a[5] = {i[5],i[6],i[7],i[8],i[9]};
    sort(a,a+5);
    int p = 0;
    int comp = helper*n;
    while (p < 120)
    {
        next_permutation(a,a+5);
        if(comp == a[0]*10000 + a[1]*1000 + a[2]*100 + a[3]*10 + a[4])
            return 1;
        p++;
    }
    return 0;
}

int main()
{
    int n;
    int helper = 0;
    int boo = 0;
    string str;
    int j = 0;
    int a1,a2,a3,a4,a5;
    while (cin >> n)
    {
        while(j < 10)
        {
            i[j] = j;
            j++;
        }
        do
        {
            a1 = i[0];
            a2 = i[1];
            a3 = i[2];
            a4 = i[3];
            a5 = i[4];
            while (a1 == i[0] && a2 == i[1] && a3 == i[2] && a4 == i[3] && a5 == i[4])
                next_permutation(i,i+10);
            helper = i[0]*10000 + i[1]*1000 + i[2]*100 + i[3]*10 + i[4];
            if(check(helper,n))
            {
                cout << helper * n << "/" << i[0] << i[1] << i[2] << i[3] << i[4] << endl;
                boo++;
            }
        }while (helper * n <= 100000);
        if (boo == 0)
            cout << "There are no solutions for " << n << "." << endl;
        boo = 0;
    }
    return 0;
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ There seems to be a bug in the program. Only the first number entered gives correct results. \$\endgroup\$ – Edward Dec 27 '14 at 0:56
  • \$\begingroup\$ What does TLE mean? \$\endgroup\$ – TheCoffeeCup Dec 27 '14 at 1:31
  • 1
    \$\begingroup\$ TLE = time-limit-exceeded \$\endgroup\$ – Edward Dec 27 '14 at 1:49
  • \$\begingroup\$ No, I have tried it several times, no such bug. \$\endgroup\$ – MikhailTal Dec 27 '14 at 11:44
9
+50
\$\begingroup\$

C++ is not my normal haunt, but there are a few significant observations on an algorithmic level that can be made here.

Bugs

  1. The first obvious bug is that your code does not run multiple times. You need to reset the j variable in the outside loop, because the system will otherwise never start again from the beginning.
  2. Your code enters an infinite loop if the user inputs 1. The code is supposed to output the result There are no solutions for 1.. Instead, since all 5-digit numbers are less than 100000 and since helper will never be more than 5 digits, the helper * 1 < 100000 exit condition for the while loop will never fail.

This leads on to a number of code-style problems...

Style

  • Namespaces:

    using namespace std;
    

    Don't do that. It is too easy to have issues with pollution in your namespace.

  • Variable declarations:

    Declare variables in the scope they are used. This would have solved the bug, for the record. The j variable is declared outside it's use-scope. This is how you declare j:

    int j = 0;
    int a1,a2,a3,a4,a5;
    while (cin >> n)
    {
        while(j < 10)
        {
            i[j] = j;
            j++;
        }
    

    But this is how it should be declared:

    int a1,a2,a3,a4,a5;
    while (cin >> n)
    {
        int j = 0;
        while(j < 10)
        {
            i[j] = j;
            j++;
        }
    
  • Bracing C++ styles generally recommend the brace at line end: e.g. Google C++ style guide Local standards override this, though, so if your local dev team has a standard they follow, that's the one that should be followed.

Algorithm

First, this problem is a 2-part problem. The first is that you have to find all 5-digit numbers that do not have the same digit twice. The second is that you have to find the right multiple of that number that uses the other digits.

Your solution is pretty poor.... you use all combinations of essentially all 10 digits to find the numbers, and you skip many, many combinations. Consider this:

while (a1 == i[0] && a2 == i[1] && a3 == i[2] && a4 == i[3] && a5 == i[4])
    next_permutation(i,i+10);

Here you have taken a copy of the i array, and put it in the a array. Then you calculate all permutations of the remaining 5 digits, until the head-5-digits of the number change. I calculate millions of iterations in that loop that are wasted.

A better solution will use some mathematical properties to limit the problem significantly. For example, the basic formula you have, is:

$$ A \times N = B $$

where A and B are both 5-digit numbers, and N is an integer. Additionally, none of the digits in A are in B. Using this, we know that:

  • the largest B can be is 98765
  • the largest A can be is 98765 / N
  • the smallest N can be is 2 (N == 1 is impossible because then A == B and we know they cannot have the same digits).

A smarter algorithm will be:

  1. obtain N
  2. find the maximum limit of A (98765 / N)
  3. find all combinations of unique digits less than (or equal to) the A limit.
  4. find the N'th multiple (B) of that digit.
  5. determine whether the digits in B are unique (when combined with A).

Working code example:

#include <iostream>

bool digitsUnique(long value) {
  int count[10] = {};
  // Move 0 digits to the end
  while (value < 10000) {
    value *= 10;
  }
  while (value > 0) {
    if (count[value % 10]++ > 0) {
      return false;
    }
    value /= 10;
  }
  return true;
}

bool combinedUnique(long low, long high) {
  int count[10] = {};
  // Move 0 digits to the end
  while (low < 10000) {
    low *= 10;
  }
  while (high < 10000) {
    high *= 10;
  }
  while (low > 0) {
    if (count[low % 10]++ > 0) {
      return false;
    }
    low /= 10;
  }
  while (high > 0) {
    if (count[high % 10]++ > 0) {
      return false;
    }
    high /= 10;
  }
  return true;
}

void compute(int mult) {
  int count = 0;
  // 10 will require releating digits,
  // and more than 10 requires multiple 0 digits
  if (mult > 1 && mult < 10) {
    long limit = 98765 / mult;
    for (long low = 1234; low <= limit; low++) {
      if (digitsUnique(low)) {
        long high = low * mult;
        if (combinedUnique(low, high)) {
          count++;
          std::cout << high << "/" << low << " = " << mult << "\n";
        }
      }
    }
  }
  if (count == 0) {
    std::cout << "There are no solutions for " << mult << ".\n";
  }
}

int main() {
  int n;
  // std::cout << "Enter Multiple: ";
  while (std::cin >> n) {
    compute(n);
    // std::cout << "Enter Multiple: ";
  }
  return 0;
}

Note, when I run your solution on my computer, and use the input values 2 through 11 like:

time ./nfact < inputs

I get the time result of:

.....
97524/10836
There are no solutions for 10.
There are no solutions for 11.

real    0m0.815s
user    0m0.808s
sys     0m0.008s

When I run my version above, I get:

95823/10647 = 9
97524/10836 = 9
There are no solutions for 10.
There are no solutions for 11.

real    0m0.019s
user    0m0.016s
sys     0m0.000s

Note that it is about 42 times faster.... I like 42.

\$\endgroup\$
4
  • \$\begingroup\$ Updated with code, and performance output. Additional bug identified. \$\endgroup\$ – rolfl Jan 2 '15 at 22:22
  • \$\begingroup\$ Thank you for your answer. The code bug for 1 isn't an actual bug, because of the 2 to 79 limitation. I will check your answer better and regard all of its improvements on my code. \$\endgroup\$ – MikhailTal Jan 3 '15 at 10:05
  • \$\begingroup\$ Also I have no idea how the j reset was missed. It worked on my computer. I must have pasted it wrong. \$\endgroup\$ – MikhailTal Jan 3 '15 at 10:06
  • \$\begingroup\$ I just tried the old code in my computer, and it strangely worked. Maybe an automatic debug function? \$\endgroup\$ – MikhailTal Jan 3 '15 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.