# GATE2017-1-48

7.3k views

Let $A$ be an array of $31$ numbers consisting of a sequence of $0$'s followed by a sequence of $1$'s. The problem is to find the smallest index $i$ such that $A\left [i \right ]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ____________.

edited
1
It can be done with 4  comparison .
It is clearly mention that 0's sequence is followed by 1's sequence. Mean there atleast one 0 and followed by 1's sequence.   or  there is many zeros and atlest one 1 at the end.

In worst case i can search min index of 1 in 4 step because ,last camparision is not required. Because list will cotain 2 element .
That is 0 followed by 1. Because it is necessary candition there should be atlest one 0 or there should be atlest one 1 .
12

@vikram No you need to do the last probe also, consider this

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 4 2 1

first row is index, second row is data and third row is for probing

5th probe is necessary to get the right answer i.e. index E

0
what does probe and optimal actually mean?
2
0

Why you have taken a[16] , we have to take

 m := floor((L + R) / 2) i.e. floor((0+30)/2)

correct me if i m wrong.

0
Why it can't be this sequence 0000000.....01. It also takes 5 probes.
0

Here, since $0$s are followed by $1$s so we have a sorted sequence and we can apply binary search.

At each stage we compare with ${\frac{(low + high)}{2}}^{th}$ element index and if it is $1$ we check left and if it is $0$ we check right.

Total worst case no. of probes is $\lceil \log_{2}{31}\rceil=5.$

So, answer is $5.$

edited
2
how 5 comparisions are enough to do this?
01111111111....
how can we recognize the smallet index with 5 comparisions in above example?
2
16-8-4-2-1 binary searching
3
Is no. of probes same as no. of comparisons made in this case of Binary Search?? I want to ask what is the meaning of 'probes'?
0

Actually not, only 4 probes are sufficient here because once you find a 1 at 2nd position, you're certain that i=2. So, this 01111.. comes under the average case.

Whereas, the sequence 001111.. or 000111.. comes under the worst case and requires the probes 16,8,4,2,3. The probe at 3 is required after finding 0 at 2nd position to ascertain whether i=3 or 4.

And by probe the question means the number of locations that the program dereferences.

0

Vidhi Sethi   No not same.

2
Is no.of probes is the no. of times we perform binary search i.e. one binary search == one probe
17
Yes one iteration of binary search = one probe
0
I think answer should be 1 probe.                                                                                                     You can add the entire elements in the array ------------------say we got value 'x'

then  arr[31-x] will directly give us the first slot with value '1'
0
it is asking for worst case
0

I think it should be 6 in case if the 1 is present at 31st position.

indexes are staring from 0.

15,22,26,28,29,.....30

Now (29+30)/2 is always 29.

So we have to check the last value either at the first time or the last time forcefully. divide and conquer will not let us check the last index.

Also if the 1 is not present then also same scenario.

2

@abhishek_tyagi Here you are not incrementing the value of i by 1. As initially i and j will be 0 and 31 respectively then k=(0+31)/2 = 15, now the index of  will be incremented to i+1 so i becomes 16. Now again calculate the new value of k, if arr[k]== 0 then go to the right or move to left.

If we consider the sequence 0000...01 as the worst-case then we would be looking at  this sequence :- 16,24,28,29,30 => 5 .

0
Why are we not considering the case when we probe the intended element at 31st index? Shouldn't the probe sequence be 15 23 27 29 30 31 and hence 6 probs instead of 5? Though I know log 31 will give 5 as answer but when I am doing it with pen and paper I am getting 6. Please correct me if I am wrong.
2
@roodramohan when you are at the position 30 and found out that 1 is not here, then definitely it will be at 31, so we don't need to do probing.It is also mentioned in the question that there is atleast one 1's is present.
0
you said "if it is 1 we check left and if it is 0 we check right." I dont think we should do this because then we will be probing one extra location in the array as in the ques it is mentioned "by probing minimum number of LOCATIONS IN ARRAY".And if you dont count checking this extra location as probing then answer will be 4 and not 5 because the worst case will occur when array is 011111....
and in this case you will get in 4th iteration as : i=0 , j=2 ,k=1 and now when you will check to the left of A[k] you will find a 0 hence you will stop and there is no need to go to 5th iteration. However, if array contains all 1's then we might need to go to 5th iteration(not sure about that).
0
> in the question that there is atleast one 1's is present.

In my opinion the question doesn't really mention this. It does say followed by a sequence of 1s which can be interpreted either way. The professors messed this one up for no apparent gain in its ability to judge a student's understanding. If only they could have mentioned assume atleast 1 of each type is present (like they do in majority of other questions)
0
@Aboveallplayer No only 4 probes are sufficient for the case:011111111......

it should not take more than 5 probes

#include <bits/stdc++.h>
using namespace std;
#define N 100
void display(bool a[]) {
int i=0;
while(i<31) printf("%2d ",a[i++]);
}
void assign(bool a[],int zeros) {
for(int i=0;i<31;i++)
(i<zeros)?a[i] = 0:a[i] = 1;
}
int main() {
srand(time(NULL));
bool a[31];
for(int i=0;i<31;i++) printf("%2d ",i);
printf("\n\n");
int max_probes = 0;
for(int iteration = 1;iteration <= N;iteration++) {
int zeros = rand()%32;
assign(a,zeros);
sort(a,a+31);
int low,high,mid,ans;
std::vector<int> seq;

low = 0;
high = 31;
while(low < high) {
mid = low + floor((high - low) / 2);
seq.push_back(mid);
if(a[mid] == 0) {
low = mid + 1;
ans = low;
if(a[mid + 1] == 1) break;
} else {
high = mid;
ans = high;
if(mid > 0)
if(a[mid - 1] == 0) break;

}
}

display(a);
printf(" | probes=%d  ",seq.size());
for(auto e:seq) printf("%d ",e);
printf(" | at = %dth\n",ans);
//if(ans == 15) printf("\nHHH=-------------\n");
max_probes = max(max_probes,(int)(seq.size()));
seq.clear();
}
printf("%d\n",max_probes);
}



edited
1
the meaning of probe ? is it ok ?
0
Can u explain diagram a bit?

According to the question there are 31 numbers,

where atleast one 0 followed by thirty 1's

So, 01111111..... in worst case

And by binary search there will be maximum 5 comparisons
3
the purpose of the diagram is to emphasize that one iteration of while loop counts one probe only. What happens inside one while iteration (finite no of comparisons ) does not change the probe count.
0

I cannot understand ur program

Can u explain a bit?

https://ideone.com/4ZG8jN

3
It randomly assigns some no of zeros and ones in an array of $31$ elements in the given order. Then binary search on the array to find the first occurrence of $1$. I put this whole thing inside a iteration loop to see results for different array configuration ( different nos of $0/1$'s) and this difference is made possible by random utility which determines the no of zeros to fill) and Total no of iteration is $100$
0
but is 100 iteration can take all combinations?

As u r taking random order, So, one 0 and thirty 1's can can take 31 numbers rt?
1
It may not, but $100$ is pretty large number compared to $31$ length
0
the above problem is nothing but finding the first occurence of a number in a sorted array which can be done in O(logn) time thats it it gives u 4.something and they asked the minimum number of probes so take ciel
0

DOES PROBE MEAN NO. OF TIMES WE DIVIDE ARRAY A USING BINARY SEARCH????

0
To 'probe' means to check/test (here, it means to check if the number at that location is 0 or 1)
0

I think the worst case occurs when all elements are 0's or all elements are 1's. Only in these two cases, i;e 11111...111 or 0000...000 we get no. of probes as 5. In the case where we have 011111....1111 we get 4 probes and even when we have 0000...001 we get 4 probes. Code: https://onlinegdb.com/ryJEKscqH Please let me know if anything is wrong here. :)

0
Can we consider probe here as an Unsuccessful Search?
0

@Shivateja MST No. A probe is a search. It could be successful as well as unsuccessful.

0
Here it is 5 as we have stopped binary search at last but one index in worst case considering input as 0000......1? I mean we have stopped probing at last but one index?

Ans is ceil(log 31) =5   Why ceil??

Take another example.
1 2 3 4 5 6 7   (7 elements... We are searching for 1)
Iteration 1:  1 2 3 4  (4!=1)     5 6 7 cancelled out.
Iteration 2:  1 2  (2!=1)          3 4 cancelled out.
Iteration 3:  1  (1==1)

3 = ceil (log 7) you know...   hence.
Here ans is  ceil (log 31) = 5        (base is 2 every where)

Here in this question, the number are sequence of zeros followed by sequence of ones.
We have to find the first index from where 1 starts. Right ?
So if you got a '1' just check if it's previous element is 0. Thats it. If it is not 0, continue binary search.
Worst Case happens when all are 1 or only first element is zero & rest are one.
111111...11  or
01111.....11  or
0011.......11  or
00011.....11  or
.
.
.

ceil(log 31) = ceil(log 30)  =  ceil(log 29) =............
only log 16 will give 4 ,   anything greator than 16 elements with ceil will give 5 as answer.

Worst case will also happen for
00.......00
00.......01
.
.
.
You got 0, here you will move right side to find the first index from where 1 starts.

edited by
0
Great explanation bro :-)
Do Binary search.
Worst case 000000000000..01 (i.e. n-1 0s and last one is 1).
It will take log n time worst case. Hence log 31 = 5.
0
can u beleive it i made a blunder, i made it 4.95 (log 31).. should have made it 5
0
Actually, I do relate to that.
1
@aboveallplayer Probes are not in floating-point, you should have made it to 5.
Ans:  6

a[0..3] = 0

a[4..31] = 1

Binary search is as follows (indexes of array a is given below):
i - j ... middle
0-31...15

0-15...7

0-7...3

3-7...5

3-5...4

3-4...3

After this i > j
3

Your naive binary search has only one condition to terminate the search which is i > j

If we do some modifications in the code keeping condition i > j then we can achieve under $5$ probes only.

You may argue that modification is not permitted. On this argument, I would like to say that, this binary search is the best algorithm to this question task. We agree. But on the implementation basis, there exists better program to do a binary search in this particular case. I think we should approach worst case using best algorithm supported by optimal program but not with rudimentary code.

All 0's are followed by 1's . So elements are sorted, we can apply Binary Search i.e log2n.

Here he is asking for minimum so take a ciel.

Ciel(log2(31))=5.00.
1 vote

If you go through the book - Skiena- the algorithm design manual, it has clearly stated that we can find a transition point in sorted array using Binary search in ceiling(logn) comparisons.

The concept is if have a sorted array with sequnce of zeros followed by sequence of 1 then we can find the smallest index 'i' such that array[ i ] is '1', which is called the transition point.

If you analyze the question, we have same thing asked in the question i.e. the transition point.

We have n=31, hence we require maximum of ceiling (logn) probes i.e. ceiling(log 31)= 5 probes.

P.S.: This question was asked on a direct concept.

Here Optimal algorithm would be Binary search with little modification. The question implies it is a sorted array of 0's followed by 1's. So 0111...1 or 00...01 or any combination of {$0^{+}.1^{+}$} of size 31.

We are taking 2 index variable i & j and it will run until i<j.

Binary Search (Modified):-

int i, j, k;
i= 0; j = 30;
do {
k = (i+ j) / 2;
if( A[k] ==  0)

i = k+1;

else j = k-1;
} while (i < j) ;

If(A[j] == 0)  printf(" J+1 is the smallest index for value 1 ");

else   printf(" J is the smallest index for 1 ") ;

In the below example we are taking an array of 7 element to understand the function of this algorithm, rest is same.

Here 2 probes are necessary to reach first 1's or last 0's in this sequence, and again 1 probe to check what value is in A[j] to find the correct index for first 1's.

So in general total no. of probes needed for this sequence of length 31= $\left \lceil Log 31 \right \rceil$ = 5

0
so as per your example , ceil(log7 base 2) = 3 , but no of probes req is 3 , why such ambiguity ?

## Related questions

1
10.1k views
A cache memory unit with capacity of $N$ words and block size of $B$ words is to be designed. If it is designed as a direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ____________ bits.
Consider the expression $(a-1) * (((b+c)/3)+d)$. Let $X$ be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which only load and store instructions can have memory operands and arithmetic instructions can have only register or immediate operands. The value of $X$ is _____________ .
Consider a $2-$way set associative cache with $256$ blocks and uses $LRU$ replacement. Initially the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access ... $10$ times. The number of conflict misses experienced by the cache is _________ .