Testbook Test Series

Question

An array of unknown size is filled with special symbols let's say '#'. Time required to find the size of array is

1) O(1)

2) O(logn)

3) O(n)

4) O((logn)²)

Comments

is it 2)  ?

---

I think...

it is O(1)...

---

how ?

---

@Diksha Aswal @ hs_yadav  Approach?

---

I think it would take O(logn)

Traverse it exponentially, i.e traverse with modification in Binary search

---

yes... same approach as Ashwin's

---

let 

S is an array...then...let starting address is 100 and having 5 element of 1 byte...then

&S+1 will return  100+5*1=105....now conside.. S=100

calculate....105-100=   5/size of an element  .....

and for given question this ia character...therefro we will assume size is 1 byte..

---

1 -> 2 -> 4 -> 8 -> 16 ->32 ...... -> 1024

Now, If the last element is 513 (OR 1023 OR 768 whichever is the worst case), then how to proceed?

---

yes, it will take O(logn) time.

---

@ joshi_nitish how?

---

https://stackoverflow.com/questions/21973619/interview-qgiven-an-input-array-of-size-unknown-with-all-1s-in-the-beginning-a

The above is a similar kind of problem where they have mentioned as O(n).

---

(d) option...?? @srivivek

---

No. Answer given is O(logn)

But I am not getting it

---

apply binary search and move towards right ..you will reach to the end i.e. to 'n' in O(logn) time.

---

@ Diksha Aswal

1 -> 2 -> 4 -> 8 -> 16 ->32 ...... -> 1024

Now, If the last element(#) is at 513 (OR 1023 OR 768 whichever is the worst case), then how to proceed?