Not able to understand the test case?

#1

Can you please explain the test case

#2

Hi @sharad1103
sample test case :slight_smile:5 3
1 2 8 4 9

arranged in sorted order, index of stall available:
1 2 4 8 9
Now possible arrangement of 3 cows:
1 2 4 //min distance between adjacent cows = 1
1 2 8 // 1
1 2 9 // 1
1 4 8 // 3
1 4 9 // 3
1 8 9 // 1
…
4 8 9 // 1

The largest among all the min distance = 3.
That’s the output.

Hope it helps
Mark resolved if satisfied :slight_smile:

#3

if i am going to use binary search to slove this problem then is it possible to check in linear time whether that combination exists or not

#4

Yes, Each check can take place in O(n).

#5

hii, don’t know how to do it in linear time.Can you please drop some hint

#6

Sorry for the late reply, I forgot to follow up and did’nt recieve the mail too.
Try this approach :
Lets say we want to check for distance = ans
maintain a variable count = 1, prev = 0
lets place a cow at arr[0], now iterate through the array and look for the next index such that index-prev >= ans.
place the cow at index and increase counter.
At the end of loop, check if counter >= no of cows given.
if true return true
else false

Hope it helps

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.