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 < 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:
- 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 <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.
