Произведение двух чисел равное сумме последовательности чисел

А ограничения какие ?

Можно попробовать делать усечение перебора, или искать какой-то алгоритм с меньшей сложностью. Без ограничений не поймешь, можно ли пропихнуть перебор просто оптимизировав его.

Можно попробовать отсортировать массив /O(n * logn)/, потом перебирать первое число, а второе искать бинпоиском по оставшейся справа от первого части массива.

если я правильно побмню питон, то range(n) аллоцирует массив, и это писец, т.к. у тебя в пустую аллоцируется туева хуча этих массивов, когда достаточно одного (а на деле и один не нужен)

Ограничения на выполнение? 8 секунд на последовательность в ~1000000. Т.е. задание более математическое, нужно понять примерное расположение первого множителя и предположить, где будет второй. Таким образом сильно уменьшим количество пар для перебора. Проверял в цикле на до 1000 — вариант всегда один, если он есть.

Сообщение прочел по диагонали. Можно, например, посчитать сумму всех чисел и сразу отбрасывать числа, произведение которых больше этой величины. Эта элементарная оптимизация уже немного сократит время.

Это третьепитон, тут range работает как xrange во втором. В данном случае на решение задачи это не сильно влияет.

Хм. Попробуй сделать так, как я предложил выше (с бинпоиском второго числа) - это будет сложность O(n * log n) - по идее должно пропихнуться в ограничение.

ну можно предположить что нижняя граница искомых чисел > rsum/n

это немного сократит перебор

Может конечно я не понимаю задачу, но вроде к этому есть контрпример:

1 1 1 1 1 1 5 (sum=11, n=7)

1 1 1 1 1 1

судя по коду там 1 2 3 4 5 6 и т.д.

если i * j > rsum - i - j, то i * (j + 1) > rsum - i - (j + 1). Т.е. внутренний цикл делай от 1 до n и прерывай сразу, как только превысило. Также можно начинать внутренний цикл от i, чтобы зеркальные дубликаты не учитывать. Также можно посчитать верхнюю границу цикла для i.

1000000

кто-то еще квадрат советует оптимайзить, ага

Ищи пары множителей числа (n(n+1)/2)+1 и вычитай из каждого множителя в паре по единице. Как минимум один из множителей не может быть больше квадратного корня.

У тебя в арифметике ошибка.

пиши nlog n как уже сказали и засылай по pypy(у меня python на самом оптимальном, что я смог написать, 14с работает)

решение за O(n) скорее всего есть, но это не оно

UPD а, не, действительно оно, сорян

Обзываем элементы последовательности a. i-й элемент будет a_i. Считаем сумму всех элементов, S.

Требуется найти a_i и a_j такие, что a_i * a_j = S - a_i - a_j. Путём нехитрых манипуляций получаем a_i = (S - a_j) / (a_j + 1). Стало быть, нам нужно перебрать все a_j и посчитать соответствующие им a_i. Для ускорения проверки перед проходом кладём все элементы в hashset. Итого — O(NlogN). Если все элементы целые, нужно ещё проверять, что частное будет целое. Ещё чуть быстрее.

Сейчас бы вместо одного квадратичного решения предложить другое квадратичное...

решение за O(n)

Что-то я сомневаюсь, что есть за O(n).

Если элементы последовательности — натуральные числа, тогда да, O(N).

Где?

Я неверно понял твои рассуждения и решил, что ты переносишь i из правой части в левую, только каким-то странным образом. При положительном i ошибки нет.

Ну тупо отсечь, например, так: берем сумму всех чисел в диапазоне (всех), а потом для каждого члена последовательности смотрим, делится ли сумма - a(i) на a(i). У кого делится, тех и перебираем.

В общем случайно наткнулся на решение на java с пояснением:

import java.util.*;

/**
 * http://www.codewars.com/kata/is-my-friend-cheating/
 */
public class IsMyFriendCheating {
	
    /*
     * The sum of numbers 1..n is n*(n+1)/2
     * So, define the operation sum(n) as n -> n*(n+1)/2.
     *
     * For any pairs (a,b) in 1..n s.t. a < b, where
     * sum(n) - a - b = a * b, we note that
     *
     * sum(n-1)/(n+1) <= a < sqrt(sum(n)+1) - 1
     * and
     * b = (sum(n)-a)/(a+1)
     */
    public static List<long[]> removNb(long n) {
        LinkedList<long[]> pairs = new LinkedList<>();
        long sum = n * (n + 1) / 2;
        long lowerBound = ((n - 1) * n / 2) / (n + 1);
        long upperBound = (long) Math.sqrt(sum + 1) - 1;
        for (long a = upperBound; a >= lowerBound; a--) {
            long b = (sum - a)/(a + 1);
            if (a * b + a + b == sum) {
                pairs.addFirst(new long[]{a, b});
                pairs.addLast(new long[]{b, a});
            }
        }
        return pairs;
    }

}

def func(n):
    lst = []
    rsum = (n * (n + 1)) / 2
    low = ((n - 1) * n // 2) // (n + 1)
    up = round((rsum + 1) ** 0.5 - 1)
    for a in range(low, up + 1):
        b = int((rsum - a) // (a + 1))
        if a * b + a + b == rsum:
            lst.append((a, b))
    return lst

def removNb(n):
    sum = n*(n + 1)/2  
    return [(x, (sum - x) / (x + 1)) for x in xrange(1, n+1) if (sum - x) % (x + 1) == 0 and 1 <= (sum - x) / (x + 1) <= n]

Все равно сложность большая. Попробуй запустить на массиве в миллион чисел.

нет, все классно. Только вот деление есть, да

Ну там тривиальные рассуждения, не стал их расписывать. Да, конечно при положительных числах это всё имеет смысл, у топикстартера в цикле по крайней мере именно так идёт. С отрицательными будет интересней.

Кстати я туплю, есть ещё простое и очевидное решение. Цикл по i идёт от 1 до какой-то границы (по идее в районе корня, надо распиывать). Далее имеем:

i * j = rsum - i - j
i * j + j = rsum - i
(i + 1)*j = rsum - i
j = (rsum - i) / (i + 1)

т.е. надо проверить, делятся ли эти числа нацело и если делятся, то ответ готов. Таким образом внутренний цикл не нужен. Сложность будет в районе O(N^(1/2)).