Saturday, December 10, 2011

Search an element in sorted rotated array

Problem: Given a sorted rotated array of distinct integers, find out the index of a given integer target in the array. If target does not exist in the array, return -1.


Approach: Using binary search.


Implementation in C#:

    public int Search(int[] nums, int target) 
    {
        int start = 0, end = nums.Length - 1;
        
        while (start <= end)
        {
            int mid = start + (end - start) / 2;
            
            if (nums[mid] == target)
            {
                return mid;
            }
            
            if (nums[start] <= nums[mid])
            {
                if (target >= nums[start] && target < nums[mid])
                {
                    end = mid - 1;
                }
                else
                {
                    start = mid + 1;
                }
            }
            else
            {
                if (target > nums[mid] && target <= nums[end])
                {
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }
        }
        
        return -1;
    }


Complexity: O(logn)

Tuesday, December 6, 2011

5 Pirates and 100 Gold Coins

Question:
Five pirates got a chest containing 100 gold coins. Now they need to think about a distribution strategy. The pirates are ranked  (Pirate 1 to Pirate 5, where Pirate 5 is the most powerful). The most powerful pirate gets to propose a plan and then all the pirates vote on it. If at least half of the pirates agree on the plan, the gold is split according to the proposal. If not, then that pirate will be killed and this process continues with the remaining pirates until a proposal is accepted. The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 5 devises a plan which he knows will be accepted for sure and will maximize his gold. What is his plan? 

Solution:
Reduce this problem to only 2 pirates. So what happens if there are only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates, the proposal has to be accepted.

Now in 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to give one gold coin to Pirate 1 . Pirate 1 knows that one gold coin is better than nothing so he has to back Pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}.
If there are 4 pirates, Pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 knows that if he dies, pirate 2 will get nothing (according to 3 pirates situation) so he will give one gold coin to pirate 2 to get his vote. So the distribution will be {0, 1, 0, 99}.

Now in 5 pirates situation, Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. so he can give one gold coin to Pirates 1 and 3 to get their vote. In the end, he proposes {1, 0, 1, 0, 98}.