Question

There is an extremely large array A such that the first n entries are positive integers, and all remaining entries are 0. Find n. You can use any programming language you want, but state the runtime of the program.

Answer 1

ans.cpp

#include<iostream>
#include<vector>
using namespace std;
int findn(vector<int> v)
{
int length = v.size(); // total length of array
int idx =0; // return 0 if all number are zero
int st=0;
int end =length-1;
while(st<=end)
{
int mid =(st+end)/2; // search at middle
if(v[mid]==0) // if middle element is 0
end = mid-1; // set end to mid-1
else
st = mid+1; // set st to mid+1
}
return st;
}
int main()
{
int t;
cin>>t;
while(t--)
{ int n,x;
std::vector<int> v;
cout<<"enter vector length"<<endl;
cin>>n;
cout<<"enter vector of size "<<n<<endl;
for(int i=0;i<n;i++)
{ cin>>x;
v.push_back(x);
}
int ans =findn(v);
cout<<"n = "<<ans<<endl<<endl;
}
// find n in this position of last postive integer in vector

}

Runtime complexity is O(log(size of array A)). logrithmic time complexity