Обработка больших чисел и переполнения

Question

Мне задан массив из N элементов, и мне нужно найти индекс P в этом массиве, где сумма значений в диапазоне от 0 до P равна сумме значений в диапазоне P + 1 к N-1.

значения каждого элемента массива может варьироваться в -2147483648 до 2147483647 и N может быть не более 10000000.

Учитывая это, как я гарантировать не переполнение при добавлении каждой значения, чтобы найти индекс P ?

Answer 1

Чтобы избежать переполнения, используйте int32_t и int64_t.

Диапазон значений [-2147483648 ... 2147483647] соответствует диапазону int32_t. Вы также можете использовать для этого int64_t, но массив из 10000000 заслуживает внимания пространства.

Поскольку сумма любых 10000000 значений не превышает диапазон int64_t, выполнять все ваши дополнения, используя int64_t.

#include <stdint.h> 
size_t foo(const int32_t *value, size_t N) { 
    int64_t sum = 0; 
    ... 
    sum += value[i]; 
    ... 
} 

---

Кстати: Уверенный, что решение можно было, что не требует добавления 64-битного сложения.
[Редактировать] Не удалось получить простое int32_t единственное решение, но придумал:

size_t HalfSum(const int32_t *value, size_t N) { 
    // find sum of entire array  
    int64_t ArraySum = 0; 
    size_t P; 
    for (P = 0; P < N; P++) { 
    ArraySum += value[P]; 
    } 

    // compute sum again, stopping when it is half of total 
    int64_t PartialSum = 0; 
    for (P = 0; P < N; P++) { 
    PartialSum += value[P]; 
    if ((PartialSum * 2) == ArraySum) { 
     return P; 
    } 
    } 

    return N; // No solution (normally P should be 0 ... N-1) 
} 

Answer 2

В худшем случае P + 1 = N-1. Поскольку максимальное значение ynumber может быть только 2147483647 или -2147483647 для любого единственного числа, это означает, что в наихудших случаях P будет максимальным или минимальным. В других случаях P все равно будет длинным целым числом. Из-за этого вам нужно использовать только длинный сценарий наихудшего случая (поскольку, если в худшем случае ожидаемый результат будет таким, что P является самым большим возможным числом, которое может быть любым одним числом, оно является длинным.

Чтобы убедиться, что вам не нужно использовать ничего большего, сопоставьте отрицательные значения с постовыми, чтобы вы оставались ниже переполнения длинного.

Представьте, что у нас есть 3 числа, ab и C. Если a + b переполняет длинный тип данных , мы знаем, что c не будет P.

Теперь представьте, что у нас есть 4 числа, a, b, c, d такие, что a + b + c = d (означает d является P), если a + b будет overflow long, это означает 1) c не может быть P 2) существует комбинация a + b + c, так что тип данных long не должен быть переполнен.

Например, a является максимально длинным, b является максимальным, c является минимальным, а d равно 0, то a + c + b = d будет правильной комбинацией операций, чтобы не использовать тип данных больше, чем длинный, и мы можем попробовать + c, так как мы знаем, что c не может быть P, так как a + b будет переполняться длинным> максимально возможное значение P.

Answer 3

Используйте 64-битные целые числа для ваших вычислений. Лучшим типом для использования является int64_t, так как long не гарантированно будет 64 бита (у вас должно быть #include <stdint.h>, чтобы сделать его доступным).

Edit: Паскаль Cuoq прав: long long действительно обеспечивает 64-битную гарантию, а также и не нуждается в включаемой (он может быть длиннее, чем 64 бита, хотя), так что это просто тип long, что вы должны избегайте, если вы хотите быть портативным.