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

[-Hex-]

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

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

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

[Michael_Rybak]

a - это заданный массив, p - это число, которое надо найти циклом for. А 2^p - это 2 в степени p.

[-Hex-]

a - это заданный массив, p - это число, которое надо найти циклом for. А 2^p - это 2 в степени p.

чет не догоняю...

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

вообще не врубаюсь.. ты пишеш что сначала надо найти индекс последней единицы(a[2^p] = 1, p max), и дальше что то с ним сделать?? но индекс последней еденици это не "сначала", это и есть требование задачи... как я его нахожу, в этом и вопрос...
обьясни плиз поподробней.