给定一个数，找到其种子根的算法

Question

我看到了这个问题在 Glassdoor上并尝试实现它。问题描述如下：

考虑数字123，数字和其各位数字相乘(123*1*2*3 = 738)等于738。因此，123是738的种子根。编写一个程序来接受一个数字并查找所有可能的种子根。例如，如果用户输入4977，则答案应该是79和711。

我想到了一种方法：

1. 找出所有从2到9的数字，用其去除输入数字并得出余数为0的数字。 2. 然后从最大的数字(在步骤1中找到的数字中)开始，找到组成输入数字的数字，并打印这些数字的所有排列。

但是，这种方法假设数字不重复，第二个问题是它无法找到所有的数字，例如对于4977，它可以找到79，但找不到711。

是否有更好的方法？

- Naveen

Answer 1

我的方法大致如下。这是一个递归算法，使用一个集合S，其中包含数字2到9，可能会多次出现。

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);
        }
    }
}

然后针对原始数字进行操作。

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

我认为这个方法可行，但可能会忽略掉一些边界情况。

对于4977，try（4977，empty，9）将发现4977可被9整除，因此它调用了try（553，{9}，9）。内部的 try 发现553是可被7整除的，553/7 = 79; 这时S' = {7, 9}，算法检查是否由数字 {7, 9}组成79，这一步成功了。虽然算法继续执行，但最终我们会回溯到外部的 try ，在某个时刻尝试 d = 7，并且4977/7 = 711，在进行检查时，S' = {7} 并且711由7和一些1组成，因此也是一种答案。

编辑：我已经包含了完整的C ++函数：

#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;
        }
    }
}

- ajb

---

我不知道你是怎么想的，但它似乎可以工作。让其他人来审查一下。 - Naveen

请注意，如果您找到答案，不要退出递归。只有在找到除1以外的任何数字都不能被整除的N时，才停止递归。 - Lee Meador

没错，它可能会返回多个答案，这是要求的一部分。 - ajb

Answer 2

另一种解决方法是检查n的每个因子，看看它是否可能是一个种子。要检查所有因子，只需要检查n的平方根。所以这个算法的时间复杂度为O(sqrt(n))。你能更快地完成吗？

以下是演示这个想法的简单C++程序。

#include<iostream>

using namespace std;

int prod(int n){
  int res=n;
  while(n!=0){
    res*=n%10;
    n/=10;
  }
  return res;
}

int main(){
  int n;
  cin >> n;

  for(int i=1;i*i<=n;++i){
    if(n%i==0){
      if(prod(i)==n)
        cout << i << endl;
      if(n/i!=i && prod(n/i)==n)
        cout << n/i << endl;
    }
  }
}

- user2660581

---

我看到的结果是，如果数字大于25000左右且没有答案，我的算法会快得多。对于6位数，它大约快2倍，对于7位数则快4倍。当至少有一个答案时，您的算法对于七位数要快大约2倍，并且对于较小的数字比例更大。我发现大约99％或更多的值没有解决方案；因此，对于循环遍历某个范围内所有可能的输入值的程序，如果涉及5位数或更大的数字，则我的程序应该更快。 - ajb

如果想要循环遍历某个范围内的所有可能值（1到n），类似于for(n in range) resultat[prod(n)].push_back(n)这样的代码可能会更快。 - user2660581

+1 确实是最容易理解的解决方案。谢谢！@Blabla404 - Vbp

Answer 3

这是一个简单的程序。在1秒内获取176852740608的种子根。现场演示。

更新：寻找376,352,349 -> 153,642,082,955,760需要27秒。你们呢？我不知道这是否好。

更新2：@ajb有一个更快的答案，至少在我做的实验中是这样。但这个答案的优点是更简单！

#include<iostream>
using namespace std;

typedef long long int Big_Int; // To get a 64-bit int

void root_stem(const Big_Int r, const Big_Int product_of_my_digits, const Big_Int target) {

        // There are two rules we can use to prune:
        //
        // First: The product_of_my_digits must divide into the target.
        //        If not, return
        // Second: The products produced lower in the search true will always be higher
        //         than those above. Therefore, we should return early if
        //         my_seed_product is larger than the target

        if (target % product_of_my_digits != 0)
                return;

        Big_Int my_seed_product = r * product_of_my_digits;

        if(my_seed_product >= target) {
                if (my_seed_product == target) {
                        cout << r << "\t->\t" << my_seed_product << endl;
                }
                return;
        }
        // print all roots, with their products, between 10*r and 10*r + 9
        for(Big_Int digit_to_append = 1; digit_to_append<=9; ++digit_to_append) {
                root_stem(r*10 + digit_to_append, product_of_my_digits*digit_to_append, target);
        }
}

int main() {
        root_stem(0,1, 4977);
        root_stem(0,1, 24562368);
        root_stem(0,1, 176852740608);
        return 0;
}

- Aaron McDaid

Answer 4

小于1秒钟的时间内计算出176852740608的所有因数，然后检查特定的因数是否为种子根。

import java.util.ArrayList;

public class Number {
    long value;
    public ArrayList<Long> factors= new ArrayList<Long>();

    public Number(long a){
        value = a;
        for(long i=1;i<= Math.sqrt(a);i++){
            if(a%i==0)
                {
                factors.add(i);
                if((a/i)!=i)
                    factors.add(a/i);
                }
        }
        System.out.println(factors);
    }


public static void main(String args[]){
    long x = 24562368L;
    Number N = new Number(x);
    for(long i : N.factors){
        long ProductOfDigits = 1;
        long k = i;
        while(k!=0){
            ProductOfDigits = ProductOfDigits*(k%10);
            k = k/10;
        }
        if(i*ProductOfDigits == N.value)
            System.out.println(i);
    }
}
}

- VikkyB

Answer 5

首先，找出分解数字的所有方法：

100 - 2 * 50 - 4 * 25 - 2 * 2 * 25 - ...等等... - 2 * 2 * 5 * 5

如果数字中有任何1位数，可以使用它们添加一些因子：

• 1 * 2 * 50
• 1 * 4 * 25
• ...等等...

运行所有这些分解并查看是否有符合条件的。

“符合条件”的是一种分解，其中有一个因子与因子数量（减去1）相同，而其他因子等于数字的某些数字。

这表明了一种过滤分解的方法，因为一旦发现：

• 两个双位数或更高的因子（因为一个解决方案由一个可能有多位数的因子以及所有其他因子恰好有一个数字组成）-OR-
• 比原始数字中的位数更多的单个数字因子（因为因子永远不可能比原始数字具有更多的数字）
• 可能还有更多

那个分解就无法起作用。

这里有一个链接，介绍了一些分解数字的方法：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.1230&rep=rep1&type=pdf

以下是一些代码，用于实现分解数字。不能保证在所有情况下都正确。使用暴力方法进行分解，并使用一些过滤器来在无法计算时快速退出。

package com.x.factors;

import java.util.ArrayList;
import java.util.List;

public class Factors {

    private List<Long> solutions;
    private final long original;
    private final int originalDigitCount;
    private List<Long> primes = new ArrayList<Long>();

    public Factors(long original) {
        this.original = original;
        this.originalDigitCount = ("" + original).length();
    }

    public List<Long> findSeeds() {
        // Consider a number 123, the product of the number with its digits (123*1*2*3 = 738) is 738. Therefore, 123 is
        // the seed product of 738. Write a program to accept a number and find all possible seed products. For example,
        // If the user entered 4977 then the answer should be 79 and 711.

        solutions = new ArrayList<Long>();

        // filter out numbers that can't have seeds

        // Number must be positive (and not zero)
        if (original <= 0) {
            return solutions;
        }

        // Find a number with a 0 digit in it
        long temp = original;
        while (temp > 0) {
            if (temp % 10 == 0) {
                return solutions;
            }
            temp = temp / 10;
        }

        collectFactors(original, new ArrayList<Long>(), 0, 0);

        return solutions;
    }

    private void collectFactors(long num, List<Long> factors, int factorCount, int doubleDigitFactorCount) {
        if (primes.contains(num)) {
            return;
        }

        // The seed can't have more digits than the original number. Thus if we find more factors excluding
        // the seed than that, this can't be a solution.
        if (factorCount > originalDigitCount) {
            return;
        }

        boolean isPrime = true; // check whether num is prime
        int newDoubleDigitFactorCount = 0;
        for (long i = num / 2; i > 1; --i) {

            // Once we have one factor 2 digits or over, it has to be the seed, so there is no use trying
            // any more double digit numbers as only single digits are needed.
            if (i > 9) {
                if (doubleDigitFactorCount > 0) {
                    return; // short circuit because of two many non-one-digit factors
                }
                newDoubleDigitFactorCount = 1;
            } else {
                newDoubleDigitFactorCount = 0;
            }

            long remdr = num / i;
            if (remdr * i == num) { // is it a factor?
                isPrime = false; // it has a factor, its not prime

                // add this new factor into the list
                if (factors.size() <= factorCount) {
                    factors.add(i);
                } else {
                    factors.set(factorCount, i);
                }

                // found a list of factors ... add in the remainder and evaluate
                if (factors.size() <= factorCount + 1) {
                    factors.add(remdr);
                } else {
                    factors.set(factorCount + 1, remdr);
                }
                long seed = evaluate(factors, factorCount + 2);
                if (seed > 0) {
                    if (solutions.contains(seed)) {
                        continue;
                    }
                    solutions.add(seed);
                }

                collectFactors(remdr, factors, factorCount + 1, doubleDigitFactorCount + newDoubleDigitFactorCount);
            }
        }
        if (isPrime) { // if its prime, save it
            primes.add(num);
        }
        return;
    }

    /* package */long evaluate(List<Long> factors, int factorCount) {
        // Find seed, the largest factor (or one of them if several are the same)
        long seed = 0; // Note seed will be larger than 0
        int seedIndex = 0;
        for (int i = 0; i < factorCount; ++i) {
            if (factors.get(i) > seed) {
                seed = factors.get(i);
                seedIndex = i;
            }
        }

        // Count the digits in the seed, see if there are the right number of factors. Ignore 1's
        boolean[] factorUsed = new boolean[factorCount]; // start off as all false
        int seedDigitCount = 0;
        long temp = seed;
        while (temp > 0) {
            if (temp % 10 != 1) {
                ++seedDigitCount;
            }
            temp = temp / 10;
        }
        if (seedDigitCount != factorCount - 1) {
            return 0; // fail - seed digit count doesn't equal number of single digit factors
        }

        // See if all the seed's digits are present
        temp = seed;
        factorUsed[seedIndex] = true;
        while (temp > 0) {
            int digit = (int) (temp % 10);
            if (digit != 1) { // 1's are never in the factor array, they are just freely ok
                boolean digitFound = false;
                for (int digitIndex = 0; digitIndex < factorCount; ++digitIndex) {
                    if (digit == factors.get(digitIndex) && !factorUsed[digitIndex]) {
                        factorUsed[digitIndex] = true;
                        digitFound = true;
                        break;
                    }
                }
                if (!digitFound) {
                    return 0; // fail, a digit in the seed isn't in the other factors
                }
            }
            temp = temp / 10;
        }

        // At this point we know there are the right number of digits in the seed AND we have
        // found all the seed digits in the list of factors
        return seed;
    }
}

- Lee Meador

---

运行所有这些因式分解可能需要一些时间，除非你有一些改进的想法... - Bernhard Barker

@Lee Meador: Dukeling是正确的。此外，如果您有一个数字，比如81，那么您可以将其写为9*9、3*3*9、3*3*3*3。它们都是1位数字。我们如何处理这种情况呢？ - Naveen

其中除了一个以外，其他的都不会“处于正确的形式”。你需要编写代码来检测具有与因子计数（少1个）相同位数的一个因子，以及这些其他因子等于这些数字的分解。9 * 9符合这个条件。数字是9，数字列表是[9]，长度为1。 - Lee Meador

请注意，找到所有因数分解是一个任意困难的问题。例如，简单粗暴的方法是迭代遍历到数字的一半，检查该整数是否为因数，如果是，则递归查找原始数字除以该因数的因数。对于一个100位数来说，这将需要很长时间。 - Lee Meador

一直在尝试。试试497745674，它没有种子，但我需要大约10秒钟才能找到它。或者试试9333333，它有一个带有很多1的种子。(@ajb可能有更快的算法) - Lee Meador

Answer 6

public class Seeds
    {
        public static void main(String[] args)
        {
             int num=4977;
             if(!seed(num).isEmpty())
                 System.out.println(seed(num));
             else
                 System.out.println("no seed number");
        }
        public static List<Integer> seed(int num)
        {  List<Integer> list=new ArrayList<Integer>();
            for(int i=1; i<=num; i++)
                {
                if(num%i==0)
                {
                    int factor_digit=1;
                    int factor = i;
                    factor_digit=factor_digit*factor;

            // when i is the factor, find factors of i and multiply them together to form number        
            while(factor>=1)
            {
                factor_digit = factor_digit * (factor%10); 
                factor = factor/10;     
            }
            if(factor_digit== num) 
                list.add(i);
        }

    }
            return list;
    }
    }

*

- Katie

Answer 7

实现一个程序，用于判断一个数字是否是另一个数字的种子。 如果将数字X乘以其每个数字得到数字Y，则称数字X是数字Y的种子。 例如：123是数字738的种子，因为12312*3 = 738 */。

class SeedNumber 
{
    public static void main(String[] args) 
    {
        int seed = 45;
        int num = 900;
        int seedNum = seed;
        int check=1;
        for(check=check*seed;seed>0;seed /=10)
        {
            int rem = seed % 10;
            check = check * rem;              
        }
        System.out.println(check);
        if(check == num)
            System.out.println(seedNum+" is a seed of "+num);
        else
            System.out.println(seedNum+" is not a seed of "+num);
        // Implement your code here 
    }
}

- Ashok Kumar