PROBLEM LINK:
Author: Mahmoud Badawy
Tester: Mohammed Ehab
DIFFICULTY:
Easy
PREREQUISITES:
Binary Search
PROBLEM:
You have a array which has two ones and other elements are zeros you can find the sum of elements in the interval [l,r] find where the two elements are
QUICK EXPLANATION:
use binary search to find them
EXPLANATION:
You can use binary search to find them by dividing the array to two pieces and search in the piece which has two criminals until you reach a point which have a criminal in its right and the other in its left you will then do a normal binary search
Complexity: O(2*log(n))
ALTERNATIVE SOLUTION:
iterate over all places to find the place of the criminals
Complexity: O(n)
SOLUTIONS:
Binary Search solution can be found here.
iterative solution can be found here.