An algorithm to find the seed root of a given number

Question

I came across this question at Glassdoor and tried to implement it.The question is as follows-

Consider a number 123, the product of the number with its digits (123*1*2*3 = 738) is 738. Therefore, 123 is the seed root of 738. Write a program to accept a number and find all possible seed roots. For example, If the user entered 4977 then the answer should be 79 and 711.

I thought of one way:

1. Find all the digits from 2 to 9 which divide the number.

2. Then start from the biggest digit (among the digits found in step 1) and find the numbers that make up the number and then print all the permutations of those numbers.

But, this assumes that the digits are not repeated and secondly it doesn't print all the numbers like for 4977 it can find 79 but will not find 711.

Is there a better approach?

Answer 1

My approach would be something like this. It's a recursive algorithm that uses a set S which is a multiset containing digits from 2 to 9, possibly multiple times.

try (N, S, digit) {
    for d = digit, digit-1, ..., 2 {
        if N is divisible by d then {
            S' = S + {d};
            if N/d is composed of all the digits in S', perhaps with
               some 1's thrown in, then N/d is an answer;
            try (N/d, S', d);
        }
    }
}

then for the original number

try (originalN, empty-set, 9);
also check originalN to see if it has only 1 digits (11, 11111, etc.); if so, then it's also an answer

I think this will work, but I may have missed some boundary cases.

For 4977, try(4977, empty, 9) will find that 4977 is divisible by 9, so it calls try(553, {9}, 9). The inner try finds 553 is divisible by 7, and 553/7 = 79; at that point S' = {7, 9} and the algorithm checks to see if 79 is composed of the digits {7, 9}, which succeeds. The algorithm keeps going, though. Eventually we'll backtrack to the outer try, which will at some point try d = 7, and 4977/7 = 711, and when we do the check, S' = {7} and 711 is composed of 7 with some 1's, so that's also an answer.

EDIT: I've included a complete C++ function:

#include <iostream>
#include <vector>

using namespace std;

struct digitMultiset {
    int counts[10];  // note: the [0] and [1] elements are not used
};

static const digitMultiset empty = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} };

bool hasDigits (const int n, digitMultiset& s) {
    digitMultiset s2 = empty;
    int temp = n;
    int digit;
    while (temp > 0) {
        digit = temp % 10;
        if (digit == 0) return false;
        if (digit != 1) s2.counts[digit]++;
        temp /= 10;
    }
    for (int d = 2; d < 10; d++)
        if (s2.counts[d] != s.counts[d]) return false;
    return true;
}

void tryIt (const int currval, const digitMultiset& s,
            const int digit, vector<int>& answers) {
    digitMultiset newS;
    for (int d = digit; d >= 2; d--) {
        if (currval % d == 0) {
            int quotient = currval / d;
            newS = s;
            newS.counts[d]++;
            if (hasDigits (quotient, newS))
                answers.push_back (quotient);
            tryIt (quotient, newS, d, answers);
        }
    }
}

void seedProduct (const int val) {
    vector<int> answers;
    tryIt (val, empty, 9, answers);
    int temp = val;
    bool allOnes = true;
    while (temp > 0)  {
        if (temp % 10 != 1) {
            allOnes = false;
            break;
        }
        temp /= 10;
    }
    if (allOnes)
        answers.push_back(val);

    int count = answers.size();
    if (count > 0)  {
        if (count == 1)
            cout << val << " has seed product " << answers[0] << endl;
        else  {
            cout << val << " has " << count << " seed products: ";
            for (int& ans : answers)
                cout << ans << " ";
            cout << endl;
        }
    }
}