Сумма пандигитального продукта

Question

Я пытаюсь решить эту проблему:

Мы скажем, что n-значный номер является pandigital, если он использует все цифры от 1 до n ровно один раз; например, 5-значный номер, 15234, от 1 до 5 пандигитальный.

Произведение 7254 необычно, так как тождество 39 × 186 = 7254, содержит множитель, множитель и произведение от 1 до 9 Pandigital.

Найти сумму всех продуктов, для которых множитель / множитель / продукт личность может быть написана как 1-9 пандигитальный.

ПОДСКАЗКА: Некоторые продукты можно получить несколькими способами, поэтому обязательно включите его один раз в вашу сумму.

но я не получаю правильный ответ.

Что я делаю не так?

Вот моя попытка:

public class Euler32 {

    public static boolean checkValue(char c,String s,int j) {    
        for(int i=j+1;i<s.length();i++)
            if(c==s.charAt(i)) 
                return true;      
        return false;
    } 

    public static void main(String[] args) {
        long total=0;
        long sum=0;

        for(int i1=40;i1<=999;i1++) {   
            for(int j=130;j<=9999;j++) {
                sum=i1*j;
                String s=i1+""+j+""+sum;

                if(s.length()!=9) continue;

                else {
                    for(int i=0;i<s.length()-1;i++) {
                        if(checkValue(s.charAt(i),s,i))
                            break;          
                        if(i+1==s.length()-1) 
                            total+=sum;      
                    }
                } 
            }
        }
        System.out.println("Total sum is: "+total);
    }    
}

Answer 1

хорошо, несколько заметок:

1. Ваше предположение начать с 40 неверно, поскольку 4 * 1783 = 6952 является пандигитальным. И есть еще один, которого вам не хватает:)
2. Вы не исключаете дубликаты продуктов.

Основываясь на обсуждении с Мариусом, я обновляю оригинальный ответ здесь. Это только метод isPandigital.

private boolean isPandigital(int a,int b){
   int c=a*b;
   StringBuilder st =  new StringBuilder();
   st.append(a).append(b).append(c);

   if (st.length()!=9 || st.indexOf("0")>-1) return false;

   Set<Character> x=new TreeSet<Character>();

   for (int i=0;i<9; i++){
       x.add(st.charAt(i));
   }
  if (x.size()==9){
     for (int k=0;k<=cnt;k++){
        if (products[k]==c) return false;
     }
  products[++cnt]=c;
  total += c;

  return true;
  }
 return false;
}

Я сравнил оба кода на моей машине, десять попыток затем усредняются, результаты выглядят следующим образом:

1. Код Мариуса: средний (2070 мс)
2. код медопалы: средний (2200 мс)
3. код Мариуса (с использованием строки): среднее (4200 мс)
4. код медопалы (с использованием строки): среднее (5000 мс)

Я добавил сравнение String vs StringBuilder, потому что, к сожалению, именно это сделало мой оригинальный код таким медленным. Но используя StringBuilder, код Marius выигрывает у меня в среднем только за 200 мс:)

Извлеченные уроки:

• StringBuilder занимает почти половину времени String. (по крайней мере, в этом эксперименте)
• Когда вам лень думать, вы можете использовать готовые структуры. (снова в этом эксперименте по крайней мере), я не обобщаю

Спасибо, Мариус:)

Answer 2

Вот еще одна реализация. Есть некоторые комментарии, чтобы увидеть, как я решил выбрать нижний и верхний предел :

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
 * 15234, is 1 through 5 pandigital.
 * The product 7254 is unusual: 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
 * Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
 * HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
 */
public class P32 {
    /* Obs:
     * 1) Because x * y = y * x, let's consider x < y (avoid duplicates)
     * 2) f * abcde => at least 1 + 5 + 5 = 11 digits => too long => y <= 9876
     * 3) If x has 3 or more digits => at least 3 + 3 + 5 = 11 digits => too long
     *    x <= 98
     * 4) If y has 2 digits => at most 8 digits => y >= 123
     * 5) If x = 1 => y and product have the same value
     * */

    final private static int min = 2;
    final private static int maxOfTwoDigits = 98;
    final private static int minOfThreeDigits = 123;
    final private static int max = 9876;

    public static void main(String args[]) {
        Set<Integer> goodProducts = new HashSet<Integer>();
        for (int multiplicand = min; multiplicand <= maxOfTwoDigits; multiplicand++) {
            for (int multiplier = minOfThreeDigits; multiplier <= max; multiplier++) {
                int product = multiplicand * multiplier;
                List<Integer> multiplicandDigits = getDigits(multiplicand);
                List<Integer> multiplierDigits = getDigits(multiplier);
                List<Integer> productDigits = getDigits(product);
                if (multiplicandDigits.size() + multiplierDigits.size()
                        + productDigits.size() == 9) {
                    productDigits.addAll(multiplierDigits);
                    productDigits.addAll(multiplicandDigits);
                    for (int i = 1; i <= 9; i++) {
                        productDigits.remove((Integer) i);
                    }
                    if (productDigits.size() == 0) {
                        goodProducts.add(product);
                    }
                }
            }
        }
        System.out.println(getSum(goodProducts));
    }

    private static List<Integer> getDigits(int x) {
        List<Integer> digits = new ArrayList<Integer>();
        while ( x > 0 ) {
            digits.add(x%10);
            x/=10;
        }
        return digits;
    }

    private static long getSum(Set<Integer> s) {
        long sum = 0;
        for ( Integer i : s) {
            sum += i;
        }
        return sum;
    }

}

Объяснение

• Умножает некоторые числа (находящиеся в указанном интервале), чтобы получить произведение.
• Для всех 3 чисел он получает цифры, а если общее количество цифр равно 9, все цифры добавляются в один и тот же список.
• Затем цифры от 1 до 9 удаляются из списка, и если список содержит 0 элементов, это означает, что комбинация является пандигитальной.
• Чтобы избежать дубликатов, товары добавляются в набор.

Время: 362 мс .

Answer 3

Вам не хватает некоторых очков:

1. Это 1,9
2. Уникальные продукты
3. Как получилось использовать 40 и 130 (просто любопытно)

(помните, что понимание проблемы решает 50%)

Рекомендации:

1. Узнайте о continue [label]; операторе и используйте локальный цикл for вместо checkValue
2. Зачем использовать s.length () более одного раза?
3. Использование StringBuilder