знакомую девушку юниора на java завалили на собеседовании следующей задачкой:

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

спрашивается: за какое кол-во операций мы можем установить что заданный массив чисел отвечает предъявленным требованиям? у нас есть операции сложения и сравнения. сложение это одна операция, сравнение это одна операция. память не выделять, но можно читать/писать в массив и операции чтения/записи считаются бесплатными. в коде должно быть не более трех целочисленных переменных и не более одной булевой переменной. массив на выходе может быть испорченным и возвращать его в исходное состояние не обязательно.

знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.

мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?