Запутался в демонстрационном тесте Codility

Question

Я прошел демонстрационный тест Codility.com .

Моя программа вернула неправильное значение для одного из модульных тестов:

TEST extreme_large_numbers Последовательность с чрезвычайно большими числами, проверяющая арифметическое переполнение.

TIME 0,056 с.

РЕЗУЛЬТАТ НЕПРАВИЛЬНЫЙ ОТВЕТ получил 2, но это не точка равновесия, сумма [0..1] = 4294967294, сумма [3..3] = - 2

Хорошо, поскольку сначала я не мог увидеть проблему в своем коде, я попытался запустить ее в проекте Visual Studio. Затем компилятор обнаружил, что 4294967294 слишком велик для int. Это должен быть uint или long. Таким образом, я изменил все на long, и он работал в VS.

Однако демонстрационный тест не позволяет изменить тип ввода / возврата функции на long.

• 2 147 483 647 (самое большое 32-разрядное целое со знаком)
• 4 294 967 294 (число, указанное в модульном тесте Codility.com)

Может кто-нибудь объяснить, как эта программа может нормально работать с 4294967294 в качестве одного из значений данных в int[]?

Answer 1

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

Редактировать: Вы можете посмотреть историю изменений, чтобы увидеть код, который работает быстро и набирает 100 баллов.; -)

Answer 2

A Swift 2.2 версия кода @Lurcero, которая работает быстро и получает 100:

public func solution(inout A : [Int]) -> Int {

let n = A.count

if n == 0 { return -1 }

if n == 1 { return 0 }

var right : Int64 = A.reduce(0, combine: +)

var left : Int64 = 0

for i in 0..<n {

    right -= A[i]

    if left == right {
        return i
    }
    left += A[i]
}

return -1
}