Uniquely digitized 5-digit multiples 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 &lt;iostream&gt;
#include &lt;algorithm&gt;

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 &lt; 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 &gt;&gt; n)
    {
        while(j &lt; 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] &amp;&amp; a2 == i[1] &amp;&amp; a3 == i[2] &amp;&amp; a4 == i[3] &amp;&amp; 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 &lt;&lt; helper * n &lt;&lt; "/" &lt;&lt; i[0] &lt;&lt; i[1] &lt;&lt; i[2] &lt;&lt; i[3] &lt;&lt; i[4] &lt;&lt; endl;
                boo++;
            }
        }while (helper * n &lt;= 100000);
        if (boo == 0)
            cout &lt;&lt; "There are no solutions for " &lt;&lt; n &lt;&lt; "." &lt;&lt; endl;
        boo = 0;
    }
    return 0;
}
C++ is not my normal haunt,  but there are a few significant observations on an algorithmic level that can be made here.

Bugs


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.
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 &lt; 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 &gt;&gt; n)
{
    while(j &lt; 10)
    {
        i[j] = j;
        j++;
    }



But this is how it should be declared:

int a1,a2,a3,a4,a5;
while (cin &gt;&gt; n)
{
    int j = 0;
    while(j &lt; 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] &amp;&amp; a2 == i[1] &amp;&amp; a3 == i[2] &amp;&amp; a4 == i[3] &amp;&amp; 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:


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


Working code example:

#include &lt;iostream&gt;

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

bool combinedUnique(long low, long high) {
  int count[10] = {};
  // Move 0 digits to the end
  while (low &lt; 10000) {
    low *= 10;
  }
  while (high &lt; 10000) {
    high *= 10;
  }
  while (low &gt; 0) {
    if (count[low % 10]++ &gt; 0) {
      return false;
    }
    low /= 10;
  }
  while (high &gt; 0) {
    if (count[high % 10]++ &gt; 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 &gt; 1 &amp;&amp; mult &lt; 10) {
    long limit = 98765 / mult;
    for (long low = 1234; low &lt;= limit; low++) {
      if (digitsUnique(low)) {
        long high = low * mult;
        if (combinedUnique(low, high)) {
          count++;
          std::cout &lt;&lt; high &lt;&lt; "/" &lt;&lt; low &lt;&lt; " = " &lt;&lt; mult &lt;&lt; "\n";
        }
      }
    }
  }
  if (count == 0) {
    std::cout &lt;&lt; "There are no solutions for " &lt;&lt; mult &lt;&lt; ".\n";
  }
}

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


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

time ./nfact &lt; 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.