一种查找给定数量的种子根的算法

Question

我在Glassdoor遇到了这个问题并试图实施它.问题如下 -

考虑一个数字123,数字及其数字(123*1*2*3 = 738)的乘积是738.因此,123是738的种子根.写一个程序接受一个数字并找到所有可能的种子根.例如,如果用户输入4977,则答案应为79和711.

我想到了一个方法:

1. 找到2到9之间的所有数字,用于划分数字.

2. 然后从最大的数字(在步骤1中找到的数字中)开始,找到构成数字的数字,然后打印这些数字的所有排列.

但是,这假定数字不重复,其次它不打印所有数字,如4977,它可以找到79但不会找到711.

有更好的方法吗？

Answer 1

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

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

如果数字中有任何 1 数字，请使用这些因素添加一些因子：

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

遍历所有这些因式分解，看看其中是否有正确的形式。

“正确形式”是一种因数分解，其中一个因数的位数与因数计数相同（少一），而其他因数等于位数

这建议了一种在找到分解因子时对其进行过滤的方法，因为一旦发现

• 两个两位数或更高的因子（因为解决方案由一个因子组成，因此可能有超过一位数加上所有其他因子恰好有一位数）-或-
• 比原始数字中的位数更多的个位数因子（因为因子的位数永远不会超过原始数字）
• 可能还有更多

因式分解不起作用。

以下是分解数字的一些方法的链接：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;
    }
}