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.
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.
The only input line contains an integer X, the index of the first occurrence of 1. (Hidden to the user)
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.
0 <= ARR[i] <= 1
Time limit: 1sec
10
10
1
1
Go for a 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.
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.
O(1), as no extra space is required.
All tags
Sort by
Interview problems
Easy Soln C++
long long firstOne() {
// Since, It is guaranteed that the answer will fit in a 64-bit integer.
// Whose max Value is 9223372036854775807.
long long start=0, end=9223372036854775807;
long long ans= -1;
while(start<end) {
long long mid= start+ (end-start)/2;
if(get(mid) == 1) {
ans= mid;
end= mid;
} else {
start= mid+1;
}
}
return ans;
}
Interview problems
100% Faster Exponential Search C++ Solution
long long firstOne()
{
if(get(0) == 1)
return 0;
long long index = 1;
while(true){
if(get(index) == 0)
index = index *2;
else
break;
}
long long start = index/2;
long long end = index;
long long ans = 0;
while(start <= end){
long long mid = start + (end-start)/2;
if(get(mid) == 1){
ans = mid;
end = mid-1;
}
else
start = mid+1;
}
return ans;
}
Interview problems
easy cpp
/************************************************************
Use get function that returns the value at index i
in the infinite sorted binary array.
get(i)
{
}
************************************************************/
#include<bits/stdc++.h>
long long firstOne() {
long long s = 0;
long long e = LLONG_MAX;
while (s <= e) {
long long mid = s + (e - s) / 2;
if (get(mid)) {
e = mid - 1;
}
else {
s = mid + 1;
}
}
return s;
}
Interview problems
easy c++ code || upvote if this code helped
long long firstOne()
{
// Write your code here.
int start = 0;
int end = 1;
while(get(end)==0)
{
start = end;
end *= 2;
}
long long ans = end;
while(start<=end)
{
int mid = start + (end-start)/2;
if(get(mid)==1)
{
ans = mid;
end = mid-1;
}
else
{
start = mid+1;
}
}
return ans;
}
Interview problems
Using Exponential Search C++
long long Bs(long long s, long long e) {
long long ans=-1;
while(s<=e) {
long long mid = s+(e-s)/2;
if(get(mid) == 1) {
ans = mid;
e = mid-1;
}
else if(get(mid) < 1) {
s = mid +1;
}
else{
e = mid-1;
}
}
return ans;
}
long long firstOne() {
long long i=0, j=1;
while(get(j) < 1) {
i = j;
j = j *= 2;
}
long long s=j/2; long long e = j;
return Bs(s,e);
}Interview problems
simple binary search code
#include <bits/stdc++.h>
long long firstOne()
{
// Write your code here.
long long s = 0;
long long e = LLONG_MAX;
while(s<=e){
long long mid = s + (e-s)/2;
if(get(mid) ==1){
e = mid-1;
}
else{
s = mid+1;
}
}
return s;
}
Interview problems
C++ binary Search || Even your grandma can do it😸
long long firstOne()
{
long long s = 0;
long long e = 1;
while(get(e) == 0)
{
s = e;
e *= 2;
}
long long ans = e;
while(s <= e)
{
long long mid = (s + (e - s)/2);
if(get(mid) == 1)
{
ans = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return ans;
}Interview problems
Simple Python Solution
'''
def get(i):
Use the given get function which is given as an argument here,
that returns the value at index i
in the infinite sorted binary array.
'''
def firstOne(get):
low = 0
high = int(1e18)
while low <= high:
mid = low + (high - low) // 2
if get(mid) == 1:
high = mid - 1
else:
low = mid + 1
return low
Interview problems
java solution
public static long firstOne()
{
long low=0;
long high=Long.MAX_VALUE;
while(low<=high){
long mid=low+(high-low)/2;
if(Runner.get(mid)==1){
high=mid-1;
}else {
low=mid+1;
}
}
return low;
}
Interview problems
Simple Logic ~ Java || Amazon Interview Asked || Java ~ Use Runner.get(i)
public class Solution {
public static long firstOne()
{
// Write your code here.
long low =1;
while(Runner.get(low)<=0){
low=low*2;
}
long high =low;
low=low/2;
long ans=0;
while(low<=high){
long mid = low+(high-low)/2;
if(Runner.get(mid)==1){
ans =mid;
high =mid-1;
}else{
low =mid+1;
}
}
return ans;
}
}
