Проблема PassingCars в коде с использованием Java

Question

Я делаю задачи по кодилизации. В данный момент я нахожусь в квесте Passing Car - https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/;

В одном из тестов производительности я получил "НЕПРАВИЛЬНЫЙ ОТВЕТ, получил -1794967296, ожидал -1"

(имя теста производительности - "large_big_answer" 0..01..1, длина = ~ 100 000 ")

Другие тесты были хорошо сделаны

Интересно, как исправить эту ошибку

Вот мой код

class Solution {
    public int solution(int[] A) {
        int mul = 0;
        int cnt = 0;
        for(int i = 0 ; i<A.length ; i++){
            if(A[i] == 0) mul++;
            else cnt = cnt+mul;
        }
        if(cnt>1000000000) return -1;
        return cnt;
    }
}

Answer 1

Проблема, как заметил @Nicholas K, связана с переполнением.

Переместите чек для if (cnt > 1_000_000_000) в цикл for. Требования:

Функция должна вернуть -1, если количество пар прохождения количество автомобилей превышает 1 000 000 000

Таким образом, как только количество пар превысит счет, остановитесь.

Итак,

public int solution(int[] A) {
    int mul = 0;
    int cnt = 0;
    for(int i = 0 ; i<A.length ; i++){
        if(A[i] == 0) mul++;
        else cnt = cnt+mul;

        if(cnt>1000000000) return -1;
    }

    return cnt;
}

Вот тестовый пример, показывающий ошибку:

@Test
public void testHalfEach() {
    final int[] inp = new int[100_000];
    final int exp = -1;
    Arrays.fill(inp, 0, 50_000, 0);
    Arrays.fill(inp, 50_000, 100_000, 1);
    validate(inp, exp);
}

private void validate(int[] inp, int exp)
{
    PassingCars prog = new PassingCars();
    int ans = prog.solution(inp);
    assertEquals(exp, ans);
}

Изменение местоположения чека позволит пройти этот тест.