Здравствуйте, мыщъх, Вы писали:

М>дано N целых чисел. пускай для определенности это будет массив A.
М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].

Задача по сортировке массива, но хитрого — каждое число в >1,5 раза больше предыдущего, а если условие нарушается то задача решена — массив не валидный. Типа 1 2 4 7 12 20 33 это норм. Для отсортированного 2N операций норм, но не отсортированный — сомнительно что такая линейная сложность сортировки возможна, а без сортировки не выйдет проверить условие, разве что побитовые операции но про такие не сказано в задаче.

Для примера массив 32 20 4 7 12 2 1 — хрен за линейное число шагов проверить что не валидный.