Search In Infinite Sorted 0-1 Array

Easy

0/40

Average time to solve is 10m

37 upvotes

Asked in companies

Problem statement

You are given an infinite array consisting of only ones and zeroes, in sorted order. You have to find the index of the first occurrence of 1.

Example:

If the array is 0 0 0 0 1 1 1 1… then, the first occurrence of 1 will be at index 4 therefore the answer here is 4.

Note:

As the array size is infinite, the actual array won’t be given to you. Instead, you will be able to access the array elements by calling a method named ‘get’.

get(i) : returns the value present at index I.

Indexing is 0-based. 

Instead of representing an infinite array in the input, we give the index of the first occurrence of 1 in the input itself. However, this input will be completely hidden from the user.

It is guaranteed that the answer will fit in a 64-bit integer.

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

Input Format:

The only input line contains an integer X, the index of the first occurrence of 1. (Hidden to the user)

Output Format:

Print an integer denoting the index of the first occurrence of 1.

Note:

You do not need to print anything, the output has already been taken care of. Just implement the given function.

Constraints:

0 <= ARR[i] <= 1

Time limit: 1sec

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

Hint 1

Hint 2

Go for a linear search.

Approaches (2)

Approach 1

Approach 2

Linear Search

The simplest approach would be to start from the beginning, i.e. index 0, and check if there’s a 1 at this index. If yes, then we have found the first occurrence of 1. Else, we check for the next index.

Time Complexity

O(X), where X is the index of the first occurrence of 1.

We search X indices before arriving at index X, and checking at each index takes O(1) time.

Space Complexity

O(1), as no extra space is required.

(100% EXP penalty)

Search In Infinite Sorted 0-1 Array

Console