CareerCup

I think u guys have nt understood the qns properly. The end of the string is nt specicifed. Its an infinite string, so calculating MID and applying BST wont be possible. The soln ofcourse will require BST, but to calculate the end we need to either go for random number generation and then testing whether the value at this index is one or not or by taking a value and incrementing it exponentially to chk whether the value at this no as index is 1. If one is found thru any of the mtds above then use it as the end and then apply the concept of bst.

This needs a one-sided binary search.

Let's say the Array is A. Start at position i=0 of the array. I assume the Array is large enough so that there won't be errors.

int prev = -1
while(A[i] == 0) {
prev = i;
i*=2;
}

This will get us a range of prev+1 to i in between which the transition would have happened.

Now we can apply a specialized binary search to find the first location of 1 in this range.

Binary Search.

Binary search , with increasing index as 2^k each time with k++.... O(log n)

Take it in an array.then compare A[mid]>=1.Accordingly do binary search...

int firstonepos(int* a,int i,int j){
	if(i==j) return i;
	else if(a[(i+j)/2]==1){
		return firstonepos(a,i,(i+j)/2);
	}
	else{
		return firstonepos(a,(i+j)/2+1,j);
	}
}

int main(){
	int a[9]={0,0,0,0,0,0,0,0,1};
	printf("%d\n",firstonepos(a,0,8));
	return 0;
}

The binary search will not work. Suppose the sequence is 01111. Here the median is 1. When 1 is compared with median (i.e. 1) it returns the index 3 which is the second one.

@Sam :binary search will surely works here just check condition this
a[i]==1 && a[i-1]==0 ok and accoredingly make the base conditions :)
code for this---
int INDEXRETURN(int arr[],int n)
{
int start=0;
int end=n-1;
int mid;
while(start<end)
{
if(a[start]==1)
return start;
if(a[end]==0)
return -1;// not any index

mid=(start+end)/2;
if(a[mid]==1&&a[mid-1]==0)
return mid;
else if(a[mid]==0)
start=mid+1;
else
end=mid-1;
}
return -1;// not available
}

@geeks it doesn't work for i/p 01111. I think while loop should be (start<=end).

The question is the input is a string or a number. If it is number than bitshift can be used. Else, underlying concept of binary search can be used.

#include <cstdlib>
#include <iostream>

using namespace std;

//TASK locate index of first 1 in an 0*1* string

// supposing full string is an in-memory char*
int SearchFirstOne(char *s, int *result){
    if (!s){ *result=-1; return -1; }// could not find '1'
    int min = 0;
    int max = strlen(s)-1;
    int mid = -1;
    *result = -1;
    int retval = -1;
    while (min < max){
          mid = (min+max)/2;
          printf(" min:%d, mid:%d, max:%d\n", min, mid, max);
          if (s[mid]== '1') {
               max = mid-1;
               *result = mid;//so far this is a valid starting location
               retval = 0;
               }
           else
           {min = mid+1;}
          
    }
    if (s[min] == '1'){ *result = min; return 0;}
          
    return retval;
}

int main(int argc, char *argv[])
{
    char *s = "011111111";
    // one solution using simplest tool:
    printf("%d\n", strchr(s,'1') - s);
    // also can use :%s/0*1 or awk/sed to find in a file, or a FSM if the string is coming through "the wire" one byte at a time
    // also, opening the file in notepad then ctrl+f to find the first 1 also works to find the column number

    
    //supposing we want a general-purpose search through an in-memory char*, use the binary search from above:
    int result = -1;
    int errcode = SearchFirstOne(s, &result);
    if (errcode == 0)
    {
     printf("%d\n\n", result);
     }
     else
     {printf("Error trying to find '1'\n");}
//I ignore the error code from here on to the end:
     SearchFirstOne("111111", &result);
     printf("%d\n", result);
     SearchFirstOne("11111", &result);
     printf("%d\n", result);
     SearchFirstOne("0", &result);
     printf("%d\n", result);
     SearchFirstOne("1", &result);
     printf("%d\n", result);
     SearchFirstOne("001111", &result);
     printf("%d\n", result);
     SearchFirstOne("01111", &result);
     printf("%d\n", result);
     SearchFirstOne("000111", &result);
     printf("%d\n", result);
     SearchFirstOne("000011111111111111111111", &result);
     printf("%d\n", result);
     SearchFirstOne("111111111111111111111111111111111111111111111111111", &result);
     printf("%d\n", result);
     SearchFirstOne("0000000000000000000000000000000000000000000000000000000000000000000000000000000000", &result);
     printf("%d\n", result);
     SearchFirstOne("000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111", &result);
     printf("%d\n", result);
     
    system("PAUSE");
    return EXIT_SUCCESS;
}

int a[]={0,1,1,1,1,1,1,1,1};
int min=0,mid;
int max=(a.length)-1;

while(min<max)
{
mid=(min+max)/2;
if(a[mid]==1)
max=mid;
else
min=mid+1;

if(a[min]==1)
{
System.out.print(min);
break;
}


}

}

}

Most of the solutions present here are kind of assuming that length of array is provided.

But it looks like inteviewer is looking for an solution which does not take care of the length of the string.