krazy8's blog

Find missing integer using divide and conquer
By krazy8, history, 5 years ago, In English

Given an array of size n-1 filled with elements from 1 to n with one missing number. Find that missing number using divide and conquer.
I google it and found many binary search algorithms but couldn't find any divide and conquer approach. Anybody know how to solve it.

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
5 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

if anyone knows i'm also interested in solutions using dynamic prorgramming, maxflow, fft and the gröbner basis... please help!!

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it +33 Vote: I do not like it

    Use FFT/DC to get $$$(x - a_1)(x - a_2) \cdots (x - a_{n - 1})$$$ and then multi-point evaluation on $$$1, 2, \dots, n$$$ to find which one is non-zero.

    → Reply