Difficulty in thinking a divide and conquer approach

1
votes

I am self-learning algorithms. As we know Divide and Conquer is one of the algorithm design paradigms. I have studied mergeSort, QuickSort, Karatsuba Multiplication, counting inversions of an array as examples of this particular design pattern. Although it sounds very simple, divides the problems into subproblems, solves each subproblem recursively, and merges the result of each of them, I found it very difficult to develop an idea of how to apply that logic to a new problem. To my understanding, all those above-mentioned canonical examples come up with a very clever trick to solve the problem. For example, I am trying to solve the following problem:

Given a sequence of n numbers such that the difference between two consecutive numbers is constant, find the missing term in logarithmic time.

Example: [5, 7, 9, 11, 15] 
Answer: 13

First, I came up with the idea that it can be solved using the divide and conquer approach as the naive approach will take O(n) time. From my understanding of divide and conquer, this is how I approached: The original problem can be divided into two independent subproblems. I can search for the missing term in the two subproblems recursively. So, I first divide the problem.

leftArray = [5,7,9]
rightArray = [11, 15]

Now it says, I need to solve the subproblems recursively until it becomes trivial to solve. In this case, the subproblem becomes of size 1. If there is only one element, there are 0 missing elements. Now to combine the result. But I am not sure how to do it or how it will solve my original problem.

Definitely, I am missing something crucial here. My question is how to approach when solving this type of divide and conquer problem. Should I come up with a trick like a mergeSort or QuickSort? The more I see the solution to this kind of problem, it feels I am memorizing the approach to solve, not understanding and each problem solves it differently. Any help or suggestion regarding the mindset when solving divide and conquer would be greatly appreciated. I have been trying for a long time to develop my algorithmic skill but I improved very little. Thanks in advance.

2
algorithmdivide-and-conquer

2 Answers

2
votes

You have the right approach. The only missing part is an O(1) way to decide which side you are discarding.

First, note that the numbers in your problem must be ordered, otherwise you can't do better than O(n). There also needs to be at least three numbers, otherwise you wouldn't figure out the "step".

With this understanding in place, you can determine the "step" in O(1) time by examining the initial three terms, and see what's the difference between the consecutive ones. Two outcomes are possible:

  • Both differences are the same, and
  • One difference is twice as big as the other.

Case 2 hands you a solution by luck, so we will consider only the first case from now on. With the step in hand, you can determine if the range has a gap in it by subtracting the endpoints, and comparing the result to the number of gaps times the step. If you arrive at the same result, the range does not have a missing term, and can be discarded. When both halves can be discarded, the gap is between them.

0
votes

As @Sergey Kalinichenko points out, this assumes the incoming set is ordered

However, if you're certain the input is ordered (which is likely in this case) observe the nth position's value to be start + jumpsize * index; this allows you to bisect to find where it shifts

Example: [5, 7, 9, 11, 15]
Answer: 13

start    = 5
jumpsize = 2
  • check midpoint: 5 * 2 * 2 -> 9
    this is valid, so the shift must be after the midpoint
  • recurse

You can find the jumpsize by checking the first 3 values

a, b, c = (language-dependent retrieval)
gap1 = b - a
gap2 = c - b
if gap1 != gap2:
    if (value at 4th index) - c == gap1:
        missing value is b + gap1  # 2nd gap doesn't match
    else:
        missing value is a + gap2  # 1st gap doesn't match

bisect remaining values