Количество неокрашенных клеток в пирамиде длины H, построенной из кубиков

Дана пирамида, построенная из кубов единичной площади заданной высоты H. Затем пирамида ставится на землю и окрашивается снаружи. Задача состоит в том, чтобы найти количество кубиков, оставшихся неокрашенными.

Примеры:

Input: H = 3
Output: 1
Explanation:

Input: H = 1
Output: 0

Наивный подход: количество кубиков, которые останутся неокрашенными, равно количеству кубиков, которых нет на границе пирамиды. Итак, для каждого слоя кубиков на высоте h количество неокрашенных кубиков равно где h>1 . Итак, сложите количество неокрашенных кубиков на каждом уровне, чтобы получить ответ.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)

Эффективный подход: поскольку количество неокрашенных кубиков в каждом слое на высоте h равно , так что эту задачу можно свести к нахождению суммы квадратов первых (H-2) натуральных чисел. Итак, ответ: (n * (n + 1) * (2n + 1))/6 , где n=H-2 .

Временная сложность: O(1)
Вспомогательное пространство: O(1)