CRIMINAL - editorial

PROBLEM LINK:

Practice
Contest

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.