Robert Eisele
Engineer, Systems Architect and DBA

Codefights: Complete the Sequence

Original Problem

Jack isn't really good at math, but his sadistic teacher still gave him some math exercises about sequences. He needs to find the next number of the given sequence, which can be one of the following three types:

  • arithmetic progression;
  • geometric progression;
  • pseudo-fibonacci sequence (a sequence each element of which is the sum of two preceding elements).

You are given 4 first numbers in the series as a string, in which the numbers are separated by commas. Help Jack to figure out what type of the sequence it is, and return the next number.

Example

  • For sequence = "4,6,10,16", the output should be
    CompletetheSequence(sequence) = 26.

    The sequence is a pseudo-fibonacci sequence.

  • For sequence = "5,10,20,40", the output should be
    CompletetheSequence(sequence) = 80.

    The sequence for a geometric progression with r = 2.

  • For sequence = "2,4,6,8", the output should be
    CompletetheSequence(sequence) = 10.

    The sequence for a arithmetic progression with d = 2.

Input/Output

  • [time limit] 4000ms (js)
  • [input] string sequence

    A string containing 4 numbers separated by a comma.

    Constraints:
    7 ≤ sequence.length ≤ 254.

  • [output] integer

    The next element of the sequence.

Solution

Case 1: Fibonacci Sequence

A Fibonacci sequence is given by

\[x_n = x_{n-1} + x_{n-2}, x_1 = 1, x_2 = 1\]

As we're given 4 numbers, we can check two times if the difference of two consecutive numbers results in the previous number before them:

\[x_3 - x_2 = x_1 \land x_4-x_3 = x_2\]

If this is the case, we can return the sum of the last two numbers:

\[S = x_3 + x_4\]

Case 2: Linear recurrence sequence

A linear recurrence sequence is defined as

\[x_1 = a, x_{n+1} = rx_n + d\]

With this generation rule, we can state:

\[\begin{array}{rrl}& x_2&= rx_1 + d\\& x_3&= rx_2 + d\\\Rightarrow & r&= \frac{x_2-x_3}{x_1 - x_2}\\\Rightarrow& d&= x_2 - rx_1\\\Rightarrow& S&= r * x_4 + d\end{array}\]Implemented in JavaScript the whole thing could look like this:

CompletetheSequence = s => {

  x = s.split`,`

  a = +x[0]
  b = +x[1]
  c = +x[2]
  d = +x[3]

  if (d - c == b) {
    return d + c
  } else {
    R = (b - c) / (a - b)
    return R * d + b - R * a
  }
}

Or minimized:

CompletetheSequence = s =>
  (c = (x = s.split`,`)[2]) - ((d = x[3]) - c - (b = x[1])
      ? (c - b) * (d - b) / (x[0] - b)
      : -d)

That's quite neat, but too much code for this code golfing task. Let's try to handle the arithmetic and geometric sequence separately as we don't need the general case. Detecting if it's an arithmetic sequence can be done quite easily by checking if \(d\) exists:

\[d = x_3 \bmod x_2\]

Case 2a: Geometric sequence \((d=0)\)

\[S = x_4 * (x_4 / x_3)\]

Case 2b: Arithmetic sequence \((d\neq 0)\)

\[x_4 + (x_4 - x_3)\]

As we're given the list as a string instead of an array, we have to do some magic JavaScript foo to lower the code size:

CompletetheSequence = s => {

  x = s.split`,`

  b = +x[1]
  c = +x[2]
  d = +x[3]

  if (d - c == b) {
    return d + c
  } else if (d % c > 0) {
    return d + d - c
  } else {
    return d * d / c
  }
}

That works fine, even if we only check the upper 3 numbers for the fibonacci detection.

CompletetheSequence = s => {

  x = s.split`,`
  b = +x[1]
  c = +x[2]
  d = +x[3]

  return (d - c - b) ? (d % c) ? (d + d - c) : (d * d / c) : (c + d)
}

Even smaller:

CompletetheSequence = s =>
  ((d = (x = s.split`,`)[3]) - (c = x[2]) - x[1])
    ? (d % c)
      ? (2 * d - c)
      : (d * d / c)
    : (c - -d)

Now remove the brackets:

CompletetheSequence = s =>
  (d = (x = s.split`,`)[3]) - (c = x[2]) - x[1]
    ? d % c
      ? 2 * d - c
      : d * d / c
    : c - -d

« Back to problem overview