Time complexity

Question

Comments

Log n, option b

---

How??

---

How O(logn)? O_O

---

Check this procedure

1.Sort the given array ===> O( n.log(n) )

assume index starts from one ===> maximum index = n, minimum index = 1

let the initialize j = maximum value

2. for( i=n; i>0; i--, j--) ====> O(n)

       if( a[i] == j )

            continue;

       break;

3. print j value ===> it is missed

 

so, total time complexity = O( n log(n) )

But Before that we have to check that, " Can we solved this problem with Binary Search ? " --- i will check and comment

---

@Shaik another way is like computing sum of first n integers i.e. from 1 to n = n(n+1)/2.

Then loop over the array and on each iteration subtract the element at that index from this sum. The sum left at the end will be the missing no.

TC: O(n).

---

@MiNiPanda, super broo

---

From geeksforgeeks! :v

---

@MiNiPanda

Hahahah.... But really GFG is a wonderful site for especially for ALGORITHMS.

if we really complete the portion in GFG, then no need to bother about any question of ALGORITHMS in GATE.

---

Yes very true..

---

Sorry ,yes it should be O(n) , @minipanda thanks bro,

Question smjhne me maine mistake kr diya tha ..

---

Well explanation bro @shaikmasthan

---

we can't apply binary search, due to array is not sort.

But we know that n is fixed ===> apply counting sort ==> O(n)

then again with a for loop, we can know which is missing ===> O(n)

O(n)+O(n) = O(n)

---

XOR method is also interesting-

https://www.geeksforgeeks.org/find-the-missing-number/