Last Updated: 5 Sep, 2020
Position Of First One
Easy
Asked in companies
Given a sorted array of size N, consisting of only 0’s and 1’s. The problem is to find the position of first ‘1’ in the sorted array Assuming 1 based indexing.
It could be possible that the array consists of only 0’s or only 1’s. If 1’s are not present in the array then print “-1”.
Input Format:
The first line contains an Integer 't' which denotes the number of test cases/queries to be run.
Then the test cases follow.
The first line of input for each test case/query contains an integer N representing the size of the array.
The second line of input for each test case/query contains N space-separated integers consisting of only ‘0’s and ‘1’s in the sorted order.
Output Format:
For each test case, print the position of the first ‘1’ in the sorted array. If 1’s are not present in the array then print “-1”.
Output for every test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the function.
Constraints:
1 <= t <= 100
0 <= N <= 10^4
Time Limit: 1sec
Approaches
- Run a loop from i = 0 to i = n-1, and if the element at i’th index is 1, return i+1.
- If you reached the end of the for loop, it means there was not a single ‘1’. Therefore, return -1.
- Initialize ans with N and initialize two variables: low with 0 and high with N-1.
- We run a while loop till low<=high and we calculate the mid-value and we check
- If array[mid] == 0 then low = mid + 1
Because if the middle element is 0, all elements to its left will be 0, so we don’t need to search over there. - Otherwise high = mid - 1 and ans = min(ans,mid)
- Because if the middle element is 1 this is a candidate for our answer and we can skip the right part of mid.
- If array[mid] == 0 then low = mid + 1
- Now check if ans is still equal to N. If so, return -1, as if we have found 1 at any position, then ans would be in between 0 to N-1.
- Since the required position has 1 based index return ans + 1.
Similar problems