krazy8's blog

Find missing integer using divide and conquer
By krazy8, history, 3 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

»
3 years ago, # |
  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
  • »
    »
    3 years ago, # ^ |
      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
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, that sword got through the heart of fly ;)

      → Reply