ARRAY

Question

A Sorted array of n elements contains 0 and 1 to find out majority of 0 and 1.How much time it will take???

and please explain  Meaning -majority of 0 and 1??

Comments

If I'm understanding it correctly , it's asking for calculating the nunber of 0's and 1's in the array , and comparing them , and finding which is in majority .

If this is the correct interpretation , then this problem can be done in $O(logn)$ time using binary search , since the array is sorted.

---

i am agree with your interpretation ,but given ans is O(1). i am also confused with interpretation

---

Can you send the solution with the actual problem statement?

---

i have only ans not solution if u want we can send

Answer 1

I think the answer should be O(1) as the middle element can be found in constant time as the n/2th element is the middle element in. Once found, it can be compared. If it is found to be 1 then the majority is 1 otherwise 0 as it is given as sorted array.

Comments

i  agree with your explanation . thanku 🙂

---

000111

6/2 = 3

3rd element is middle element right?.

But here can you tell which one is in majority only by checking the middle element?.

I agree with your approach , but you need to look one element i.e mid-1 to confirm .

---

11011

middle =3 element

Here, the middle element is 0, then how could you say that the majority is 0?

---

In the question ,the array given is sorted while in your case it's not.

---

I think my approach is right if n is odd otherwise we've to check both mid and mid-1 to confirm whether the array has a majority or equality.Still the answer is O(1) as it will take constant time.

---

But in question it is said that find out majority of 0 and 1. We can find majority only when no of 0’s and no of 1’s are not equal. If both are equal than no(either 0 or 1) will be in majority.