# Spotting the difference between two arrays using divide-and-conquer

Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.

For simplicity, assume we can use two subroutines that can sum any subarray in our first and second arrays, respectively.

How would we use this to find a suitable algorithm using a divide-and-conquer approach? And if so, how many times would it have to call the subroutines? I assume we can start by dividing our arrays into two and solving our problem recursively from there.

• Is a time complexity given for those two subroutines that can sum any subarray in our [arrays]? What can you gain if it was log-linear (in subarray length)? Linear? – greybeard Oct 21 '19 at 7:25