CareerCup

O(loglogn) - Interpolation Search- not recommended as points are not equally iid (Independent and identically-distributed )
O(Logn) - Binary Search : Could not be so dumb question

Not able to scrutinize the exploitation of 0's 1's , Hashing wouldn't help.

Please comment.

As it is a sorted array Binary search will be the best soln

As it is a sorted array Binary search will be the best soln

As it is a sorted array Binary search will be the best soln

Add all the numbers , suppose u get x.This takes O(N).
Now suppose size of array is n , now index to n-x. This is O(1).This is the 1st one.This works as array is sorted and zeros come first.

To mohammad.z.siddiqui
Your approach looks fine to me. I think that way we can tackle the problem.
To Rohan
Your approach sucks as you dint read the question properly.

here is my solution:
Jump 2 steps, see if it 1, then jump 4, 8 etc until u hit a one.
Then jump back 1,2,4,8 etc until u hit a zero, then forward and backward (until orgasm:)
This works good, O(log N) worst case

could someone clarify,

if the sequence is sorted then all 0's would obv appear first and then followed by 1's are they asking us to find the occurrence of the first "1" in the array,is that the question?

If the answer to my previous question is "yes" then are we required to find a method which takes < O(n).If its an O(n) solution then I am sure all of us know more than one method to do this qn.

none of the above solutions fully exploit the 0/1 property of the array

thinking...

Using a modified version of the binary search algorithm, you can return the lower bound index when the lower bound has the key being searched in case when the upper bound is greater than or equals to the key.

firstOccurrance(int[] sortedBins) {
    int lower = 0;
    int upper = sortedBins.length - 1;
    while (lower <= upper) {
        int middle = 1 + (upper - lower) / 2;
        if (sortedBins[middle] == 0) {
            lower = middle + 1;
        } else {
            upper = middle - 1;
        } 
        if (sortedBins[lower] == 1) {
            return lower;
        }
    }
    return -1;
}

public static int findNum(int[] arr)
{
Set s =new HashSet<>();

int index=0;
for(int i=0;i<arr.length;i++)
{
if(s.add(arr[i]) && arr[i]==1)
{
index=i;
}
}
return index;
}

when using hashset you are again scanning through the array which means complexity is >O(n)

#include<stdio.h>
#include<math.h>
int BinarySearch(short int* array, int end) {
int mid;
int start=0;
while(start<=end) {
mid=(start+end)/2;
if(array[mid]==0 && array[mid+1]==1)
return mid+2;
else if(array[mid]==1 && array[mid-1]==0)
return mid+1;
else if(array[mid]==0)
start=mid+1;
else if(array[mid]==1)
end=mid-1; }
return -1; }

int find(short int* array) {
int i=0;
long long index=0;
while(array[index]!=1) {
i++;
index=pow(2,i); }
i=BinarySearch(array,index);
return i; }