Факториал начинается с четного числа

Я хочу собрать все числа в диапазоне [a, b], факториал которых начинается с четного числа.

Например:

a = 1, b = 10

Отвечать:

2 3 4 8

Объяснение:

2! = 2 = starts with even
3! = 6 = starts with even
4! = 24 = starts with even
8! = 40320 = starts with even

Ограничения:

1 <= а, б <= 100

Вот мой код:

List<Integer> process(int a, int b) {
    long base = i;
    for(int i=1; i<=a; i++) base *= i;
    
    if(even(base)) list.add(a);
    
    for(int i=a+1; i<=b; i++) {
        base *= i;
        if(even(base)) list.add(i);
    }
    return list;
}

boolean even(long k) {
    int z = ("" + k).charAt(0) - '0';
    return z % 2 == 0;
}

Это было задано несколько дней назад в задаче кодирования, когда я реализовал это, 6 скрытых тестовых случаев не сработали из 15 тестовых случаев. Я не могу найти ошибку в этом коде.

Забавный факт: каждый факториал n!, где n >= 2 — четное число. Четное число должно делиться на 2, а значит, и на n! = n * (n-1) * ... 3 * 2 * 1 = 2x, где x — произведение факториала до 2.

Rogue 18.11.2022 23:07

«Я хочу собрать все числа в диапазоне [a, b], факториал которых является четным числом». - ∀(n ∈ N): n > 1 ↔ n % 2 = 0.

Turing85 18.11.2022 23:08

Для тех, кто не понял, вопрос в том, у скольких есть факториал, НАЧИНАЮЩИЙСЯ с четного числа.

btilly 18.11.2022 23:08

@btilly хороший улов, пропустил эти комментарии. У меня возникает соблазн подумать, что для этого также может быть закрытое решение.

Rogue 18.11.2022 23:10

Ваш код не может быть скомпилирован. Кроме того, у длинных значений нет метода charAt.

Melron 18.11.2022 23:11

@Melron, я исправил это сейчас.

learner 18.11.2022 23:13

Учитывая ограничения, значения можно рассчитать заранее и поместить в список, а затем просто вытащить элементы, находящиеся во входном диапазоне.

Andrew S 18.11.2022 23:18

Если 1 < a < b < 100, почему бы просто не вычислить ответ и не найти его при необходимости?

Dave 18.11.2022 23:18

[2, 3, 4, 8, 12, 13, 14, 16, 18, 20, 23, 24, 26, 29, 30, 31, 32, 33, 34, 39, 40, 43, 44, 47, 49 , 52, 53, 54, 57, 58, 60, 65, 68, 71, 72, 73, 75, 79, 82, 85, 86, 87]

Dave 18.11.2022 23:32

Большинство факториалов для n, где 1 <= n <= 100 значительно превышает возможности long.

WJS 19.11.2022 00:18

Я заметил, что ваш диапазон описывается как [a,b], что в математике представляет собой закрытый интервал. В Java диапазоны обычно наполовину открыты [a,b), а b исключены. Просто интересно, что это было.

WJS 19.11.2022 14:57

Я попробовал sqrt(π) e^(-n) n^(n + 1/2) 2^(ceiling(-(2 log(n) n - 2 n + log(2 n π))/log(100)) + 1/2) 5^ceiling(-(2 log(n) n - 2 n + log(2 n π))/log(100)), которое, я думаю, является последним числом, но оно выводит inf все время.

Neil 20.11.2022 06:09
Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot
В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .
Как включить TLS в gRPC-клиенте и сервере : 2
Как включить TLS в gRPC-клиенте и сервере : 2
Здравствуйте! 🙏🏻 Надеюсь, у вас все хорошо и добро пожаловать в мой блог.
Сортировка hashmap по значениям
Сортировка hashmap по значениям
На Leetcode я решал задачу с хэшмапой и подумал, что мне нужно отсортировать хэшмапу по значениям.
Принципы SOLID - лучшие практики
Принципы SOLID - лучшие практики
SOLID - это аббревиатура, обозначающая пять ключевых принципов проектирования: принцип единой ответственности, принцип "открыто-закрыто", принцип...
gRPC на Android с использованием TLS
gRPC на Android с использованием TLS
gRPC - это относительно новая концепция взаимодействия между клиентом и сервером, но не более.
5
12
211
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

Это проще, чем вы думали.

  1. Цикл от а до б

  2. Вычислить факториал индекса цикла

  3. Проверьте, является ли первый символ сгенерированного индекса четным, и добавьте его в свой список.

  4. Распечатать список

    private static List<Integer> process(int a, int b)
    {
        List<Integer> list = new ArrayList<>();
        for (int i = a; i <= b; i++)
        {
            final int factorial = calcFactorial(i);
            if (factorialStartsWithEven(factorial))
                list.add(i);
        }
        return list;
    }
    
    private static boolean factorialStartsWithEven(int factorial)
    {
        final String strVal = String.valueOf(factorial);
        final int intVal = Integer.valueOf(strVal.charAt(0));
        return intVal % 2 == 0;
    }
    
    private static int calcFactorial(int n)
    {
        if (n == 0)
            return 1;
        return (n * calcFactorial(n - 1));
    }
    
13! больше, чем максимальное значение, которое может быть сохранено в int.
user3386109 19.11.2022 00:55
Ответ принят как подходящий

Я использую BigInteger, чтобы решить эту проблему. Чтобы ускорить процесс, я запоминаю последующие вычисления факториала как отправные точки для будущих. Я также создал запись для хранения соответствующих данных, чтобы облегчить процесс.

Может быть математический способ предсказать четность первой цифры, но на данный момент это работает.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class FactorialStartsWithEven {

    public static void main(String[] args) {
       
        List<Integer> list = getForRange(1, 20);
        System.out.println(list);
    }

отпечатки

[2, 3, 4, 8, 12, 13, 14, 16, 18, 20] 
public static List<Integer> getForRange(int start, int end) {
    List<Integer> results = new ArrayList<>();
    for (int i = start; i <= end; i++) {
       if(factorialStartsWithEven(i)) {
           results.add(i);
       }
    }
    return results;
}

Запись, объявленная для хранения данных

    record Fact(BigInteger fact, int n, boolean parity) {}

Инициализировать Memo для вычисленных факториалов

    static List<Fact> computed = new ArrayList<>(List.of(
            new Fact(BigInteger.ONE, 0, false),
            new Fact(BigInteger.ONE, 1, false),
            new Fact(BigInteger.TWO, 2, true)));
  • Если значение уже существует, просто найдите его и верните логическое значение.
  • в противном случае получите последнее вычисленное значение и начните вычисления до n, добавляя каждый факториал в список по мере его вычисления.
    public static boolean factorialStartsWithEven(int n) {
        if (n < computed.size()) {
            return computed.get(n).parity;
        }
        Fact f = computed.get(computed.size()-1);
        BigInteger b = f.fact;
        Fact result = null;
        for (int k = f.n+1; k <= n; k++) {
            b = b.multiply(BigInteger.valueOf(k));
            result = new Fact(b, k, Character.digit(b.toString().charAt(0),10) % 2 == 0);
            computed.add(result);
        }
        return result.parity;
    }


Красивый! Ваш ответ полон ценных вещей и новейших структур данных, полезных для учащихся.

Arvind Kumar Avinash 19.11.2022 18:56

Вот код Ruby, который решает это для ваших параметров. Я не знаю Java, но это будет легко перевести. Нет смысла решать сложную общую проблему, когда ваши входные параметры такие скромные (в частности, b <= 100). Мой массив останавливается на 87, потому что 88! через 100! все имеют нечетные начальные цифры.

def get_list(a, b)
  arr = [2, 3, 4, 8, 12, 13, 14, 16, 18, 20, 23, 24, 26, 29, 30, 31, 32, 33, 34, 39, 40, 43, 44, 47, 49, 52, 53, 54, 57, 58, 60, 65, 68, 71, 72, 73, 75, 79, 82, 85, 86, 87]
  
  list = []
  
  arr.each do |val|
    list.append(val) if a <= val && val <= b
  end
  
  return list
end

> get_list(10, 20)
=> [12, 13, 14, 16, 18, 20]

Это грязное решение — я на самом деле не рекомендую его, просто публикую его здесь для интереса — но цифры с меньшим значением относительно мало повлияют на первую цифру. В качестве таких:

import java.math.BigInteger;
public class Main {  
  public static void main(String args[]) {
    long acc = 1;
    int limit = (int)Math.log10(Long.MAX_VALUE);
    for (int i = 1; i <= 100; i++){
      int accLength = (int)Math.log10(acc) + 1;
      int iLength = (int)Math.log10(i) + 1;
      //System.out.printf("Acc :%s, accLength : %s, i : %s, iLength : %s \n", acc, accLength, i, iLength);
      if (accLength + iLength >= limit){
        //System.out.printf("Adjusting %s by %s", acc, iLength);
        acc = acc / (long)(Math.pow(10, iLength));
        //System.out.println(" becomes: " + acc);
      }
      acc = acc * i;
      System.out.printf("acc is %s\n", acc);
    }
  }
}

Простите за неаккуратность, давно не работал на Java.

В любом случае, это решение основано на том факте, что младшие цифры не будут сильно влиять на ведущие цифры. Так что — и никому не говорите, что я сказал, что можно заниматься математикой таким образом — я просто отбрасываю их, делю на некоторую степень 10 и сохраняю только то, что могу поместиться в long.

На самом деле я не уверен, как долго это будет оставаться точным. Мне любопытно, хочет ли кто-нибудь взвесить это, но я подозреваю, что это будет продолжаться до тех пор, пока цифры i (то, что мы берем факториал) не станут значимыми по отношению к длине длинного.

Другие вопросы по теме