Задачи на эффективность Опции

[-Hex-]

подскажите решение:
1. дается упорядоченный массив типа 111..11100000...000. нужно опсчитать количество единиц в нем.

нет проблем сделать это с эфективностью порядка логорифм М по основанию 2 (где М-длинна всего массива).
требуется сделать это с эфективностью порядка логорифм N по основанию 2 (где N-количество единиц в массиве).
для простоты длинну массива можно ограничить <20.

2. дается квадратная матрица размерности N. Требуется повернуть ее на 90 градусов используя минимум памяти.

[Michael_Rybak]

требуется сделать это с эфективностью порядка логорифм N по основанию 2 (где N-количество единиц в массиве).

Сначала находишь наибольшее p такое, что a[2^p] = 1. Теперь пытаешься идти дальше с шагом 2^(p-1), уменьшая шаг в 2 раза каждый раз, когда упираешься в нолик.

2. дается квадратная матрица размерности N. Требуется повернуть ее на 90 градусов используя минимум памяти.

Дополнительная память - O(1). Крутятся по отдельности,прямо на месте, четверки (x, y)->(n-y+1, x)->(n-x+1, n-y+1)->(y, n-x+1). Нумерация строк и столбцов - с единицы.