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

[-Hex-]

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

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

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