Glassdoorでこの質問に出会い、実装しようとしました。質問は次のとおりです-
数字 123 を考えてみましょう。数字と数字の積 (123*1*2*3 = 738) は 738 です。したがって、123 は 738 のシード ルートです。数値を受け入れ、すべての可能なシード ルートを見つけるプログラムを作成してください。 . たとえば、ユーザーが 4977 と入力した場合、答えは 79 と 711 になります。
私は1つの方法を考えました：
数を割る 2 から 9 までのすべての数字を見つけます。
次に、(ステップ 1 で見つかった数字の中で) 最も大きい数字から始めて、数字を構成する数字を見つけ、それらの数字のすべての順列を出力します。
ただし、これは数字が繰り返されないことを前提としており、次に、4977 のようにすべての数字を出力するわけではありません。79 は見つかりますが、711 は見つかりません。
より良いアプローチはありますか？
私のアプローチはこのようなものになります。これは、2 から 9 までの数字を含むマルチセットであるセット S を、場合によっては複数回使用する再帰アルゴリズムです。
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} となり、アルゴリズムは 79 が数字 {7, 9} で構成されているかどうかをチェックし、成功します。ただし、アルゴリズムは引き続き実行されます。最終的には外側のに戻り、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;
}
}
}
もう 1 つの解決策は、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;
}
}
}
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;
}
}
*
数値が別の数値のシードであるかどうかを調べるプログラムを実装します。X にすべての桁を掛けると YEg に等しい場合、数値 X は数値 Y のシードであると言われます。123 は、123 1 2*3 = 738 として 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
}
}
まず、数を因数分解するすべての方法を見つけます。
100 - 2 * 50 - 4 * 25 - 2 * 2 * 25 - ...など ... - 2 * 2 * 5 * 5
数字に 1 桁がある場合は、それらを使用していくつかの要素を追加します。
これらすべての因数分解を実行し、いずれかが正しい形式であるかどうかを確認します。
「正しい形式」は、因数の数と同じ桁数 (1 を引いた数) の 1 つの因数を持ち、他の因数はその桁数に等しい因数分解です。
これは、因数分解を見つけたらフィルタリングする方法を示唆しています。
その因数分解は機能しません。
数を因数分解するいくつかの方法へのリンクは次のとおりです。
これを行うコードを次に示します。すべての場合に正しいという約束はありません。ブルートフォースを使用して因数分解し、いくつかのフィルターを使用して、うまくいかない場合にプロセスを短絡させます。
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;
}
}