Position Of First One

Easy

0/40

Average time to solve is 15m

Contributed by

3 upvotes

Asked in companies

Problem statement

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”.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

4
1
-1

Explanation For Sample Input 1:

Test Case 1:
Three 0’s are present at the beginning and first ‘1’ is present at the 4th position.

Test Case 2:
First ‘1’ is present at the 1st position.

Test Case 3:
1’s are not present in the array so we print -1.

Hint 1

Hint 2

Try to find the position by traversing the whole array.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N), where N is the number of elements in the array.

Since we are traversing the array once.

Space Complexity

O(1)

Since we are using constant extra space.

(100% EXP penalty)

Position Of First One

Console