title: Find missing numbers in array in O(log(n)) time
body: <p>I'm given two arrays A and B where A is completely filled with positive integers and B is A with some constant number of elements turned into zeroes. I'm also given an arbitrary function that takes an array and gives the sum of the array in O(1) from an a to b where a and b are indices in the array.</p>
  
  <p>I'm supposed to design an algorithm that turns array B into array A in O(log(n)) time, but I'm having difficulties seeing how that is possible.</p>
  
  <p>I've come up with a solution that is O(n) where I simply compare the index of A to the index of B. If they are the same, I continue through the loop and if they are different, I update the value of B[i] to be A[i]. I don't see a way to improve this, especially if the arrays are unsorted. </p>