хорошо теперь это терпит неудачу в течение 15

отаю над программой, которая принимает целое число и находит количество комбинаций последовательных сумм, которые имеет целое число:

Число 13 может быть выражено как сумма последовательных положительных целых чисел 6 + 7. Четырнадцать могут быть выражены как 2 + 3 + 4 + 5, также сумма последовательных положительных целых чисел. Некоторые числа могут быть выражены как сумма последовательных положительных целых чисел более чем одним способом. Например, 25 - это 12 + 13, а также 3 + 4 + 5 + 6 + 7.

Я исследовал и прочитал, что это число нечетных факторов минус один. Поэтому я написал программу, которая находит число нечетных факторов, и в некоторых случаях мой ответ все еще неверен. Любое понимание?

Кажется, код работает нормально, но происходит сбой из-за тайм-аута, что, вероятно, связано с ошибкой оптимизации.

Ограничения для возможного размера ввода от 1 до 10 ^ (12)

Код ниже скопирован сответ Альфасина ниже:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;


  static long consecutive(long num) {
    while (num % 2 == 0) num /= 2;
    return  consecutiveHelper(num);
}

public static long consecutiveHelper(long num) {
    return LongStream.rangeClosed(3, (num / 2)).parallel().filter(x -> x % 2 != 0).map(fn -> (num % fn == 0) ? 1 : 0).sum();
}
        public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        final String fileName = System.getenv("OUTPUT_PATH");
        BufferedWriter bw = null;
        if (fileName != null) {
            bw = new BufferedWriter(new FileWriter(fileName));
        }
        else {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        int res;
        long num;
        num = Long.parseLong(in.nextLine().trim());

        res = consecutive(num);
        bw.write(String.valueOf(res));
        bw.newLine();

        bw.close();
    }
}

Это то, что у меня сейчас есть

 Ed Cottrell♦15 окт. 2017 г., 21:26
Комментарии не для расширенного обсуждения; этот разговор былперешел в чат.

Ответы на вопрос(2)

которые мы обсуждали в разделе комментариев, смотрите комментарии как маркеры:

static int consecutive(long num) {
    while (num % 2 == 0) num /= 2; // 1st opt.
    return  consecutiveHelper(num)-1;
}

public static int consecutiveHelper(long num) {
    long factorNumber = 1;
    int count = 0;

    while(factorNumber <= num / 2) { // 2nd opt.
        if(num % factorNumber == 0) {
            count++;
        }
        factorNumber += 2; // 3rd opt.
    }
    if (num % 2 != 0) {
        count++;
    }
    return count;
}

ОБНОВИТЬ

Мне удалось сократить время выполнения больших чисел на ~ 50% (10 ^ 12) с помощью интерфейса Java 8 Stream и параллельной работы:

static long consecutive(long num) {
    while (num % 2 == 0) num /= 2;
    return  consecutiveHelper(num);
}

public static long consecutiveHelper(long num) {
    return LongStream
        .rangeClosed(3, (num / 2))
        .parallel()
        .filter(x -> x % 2 != 0)
        .map(fn -> (num % fn == 0) ? 1 : 0)
        .sum();
}

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

 Ron Baker15 окт. 2017 г., 06:22
черт еще таймаут
 alfasin15 окт. 2017 г., 06:23
мы можем улучшить его немного дальше ...
 Ron Baker15 окт. 2017 г., 06:23
ну прошло еще один тестовый случай, чем в прошлый раз
 alfasin15 окт. 2017 г., 06:24
проверить 2-й вариант очередной раз
 Ron Baker15 окт. 2017 г., 06:25
хорошо теперь это терпит неудачу в течение 15
Решение Вопроса
Поскольку пост, на который я ответил, был дубликатом, я также скопировал свой ответ здесь.

Давайте попробуем найти псевдооптимизированный метод для решения вашей проблемы:

разложите ваше число в главные факторы.

Например, если вы берете1200 :

1200 = 2*2*2*2*3*5*5 = 1 * 2^4 * 3^1 * 5^2

Затем вы можете проанализироватькак вы могли получить странные факторы с этими основными факторами, Быстрый анализ скажет вам, что:

нечетный * нечетный = нечетныйнечетный * четный = четныйдаже * даже = даже

Имея это в виду, давайте найдем все факторы, которые мы получаем сстранный * странный :

1 * 1 = 13 * 1 = 35 * 1 = 55 * 3 = 155 * 5 = 255 * 5 * 3 = 75

Быстрый способ найти эти комбинации без записи их всехплюс 1 метод": добавить 1 к числу вхождений каждого простого нечетного множителя иумножить их вместе :

Мы нашли это1200 = 1 * 2^4 * 3^1 * 5^2так что мы можем сделать:

(«число 3» + 1) («число 5» + 1) =(1 + 1) ( 2 + 1) = 6

Для числа 1200 существует 6 нечетных коэффициентов, и, как вы сказали, удалите 1 из этого числа, чтобы получить количество комбинаций последовательных сумм, которые имеет 1200:

6 - 1 = 5 <- вау! наконец-то получил результат!

Теперь давайте посмотрим на код.То, что мы хотим иметь, это Карта, ключи - главные факторы, а значения - количество их вхождений. :

/*
    If number is odd,
    find the number in the keys and add 1 to its value.
    If the number is not in the keys, add it with value = 1.
 */
public static void addValue(Map<Integer, Integer> factors, int i) {
    if(i % 2 != 0) {
        int count = factors.containsKey(i) ? factors.get(i) : 0;
        factors.put(i, ++count);
    }
}

/*
    Classic algorithm to find prime numbers
 */
public static Map<Integer, Integer> oddPrimeFactors(int number) {
    int n = number;
    Map<Integer, Integer> factors = new HashMap<>();
    for (int i = 2; i <= n / i; i++) {
        while (n % i == 0) {
            addValue(factors, i);
            n /= i;
        }
    }

    if(n > 1) addValue(factors, n);
    return factors;
}

С этим, давайте попробуем напечатать то, что карта содержит для числа1200 :

public static void main(String[] args) {
    int n = 1200;

    System.out.println(oddPrimeFactors(n));
}


$n : {3=1, 5=2}

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

public static int combinations = 1;

public static void main(String[] args) {
    int n = 1200;

    oddPrimeFactors(n).forEach((key, value) -> combinations *= (value + 1));
    combinations--;

    System.out.println(combinations);
}


$combinations = 5


Закончено! не стесняйтесь спрашивать, если вы что-то не поняли!

Примечание: я попробовал свою программу с максимальным значением, которое может обработать Integer, и моя программа заняла менее одной секунды, что мне кажется довольно быстрым. Вероятно, это может быть быстрее, вам нужно найти наиболее оптимизированную версию этого кода!

 Paul Lemarchand15 окт. 2017 г., 21:54
да, другой пост был дубликатом, поэтому я разместил здесь. Вы можете принять ответ слева, если он решил вашу проблему. Вы сказали, что зададите вопрос, но не сделали этого
 Ron Baker15 окт. 2017 г., 22:09
спасибо я исправил, приму ваш ответ дважды
 Paul Lemarchand15 окт. 2017 г., 21:58
я видел это сейчас, но в чем проблема с длинными? просто замените int на long, а Integer на Long
 Ron Baker15 окт. 2017 г., 21:55
о, я спросил это в другом посте случайно извините
 Ron Baker15 окт. 2017 г., 21:46
Эй, ты тут

Ваш ответ на вопрос