Unimodal Search

An array A[1...n] is unimodal if it consists of an increasing sequence followed by a decreasing sequence. More precisely, if there is an index m in {1, 2, ... n} such that
A[i] < A[i+1] for 1 <= i < m and
A[i] > A[i+1] for m <= i < n

In particular, A[m] is the maximum element, and it is the unique "locally maximum" element surrounded by smaller elements.

Give an algorithm to compute the maximum element of a unimodal input array A[1...n] in O(lg n) time.

Source: Problem 1-3.from MIT OpenCourseWare Course - 6.046J / 18.410J Introduction to Algorithms (SMA 5503)

100 Switches & 100 bulbs

There are 100 switches in a room operating 100 bulbs. At iteration '0' all switches are OFF. For every iteration 'i', all switches that are multiples of 'i' are toggled (turn OFF if ON, turn ON if OFF).

You need to find the state of the 'k'th switch/bulb (1<=100) after the 'i' th iteration

Expected O(1) time and space complexity.