2
$\begingroup$

Given a string that consists of only digits, return an integer array (without shuffling sequence of string characters) such that the array elements form a Fibonacci series based on indices. If such an array can't be formed return a new array with -1 as the only element.

Fibonacci sequence based on indices means that [element at index i] = [element at index i-1]+ [element at index i-2]

Example 1: Input: "1235" Output {1,2,3,5}

Example 2: Input:"11112233" Output: {11,11,22,33}

Example 3: Input: "123456579" Output: {123,456,579}

Example 4: Input: "135" Output: {-1}


The algorithm that I could come up with:

  1. Initialize by finding all possible groups of indices [i, j] such that input[1,i), input[i,j) form the first 2 numbers of the desired result. For each such group, do step 2 as mentioned below.
  2. Call a recursive function that uses the index of the first character of the string that is yet to be parsed (k in this case). This function will parse the string till it can either find a number with which it can extend the Fibonacci sequence or not. If it can, recursively call itself by passing the new index and the list of numbers built till now.
  3. Once the recursion reaches the index == input.length, the list of numbers formed till then is the result needed.
  4. If the list.length < 3 return an array of -1.

I need help finding a better/optimal solution.

$\endgroup$
  • $\begingroup$ I'm not sure why you're interested in a triplet of vertices. Your $i$ must always be $1$. As a result, you obtain an $O(n^3)$ algorithm. $\endgroup$ – Yuval Filmus May 16 '18 at 14:12
  • $\begingroup$ I corrected it. Is O(n^3) the best solution to this problem? $\endgroup$ – Sarveshwar May 16 '18 at 21:30
  • $\begingroup$ I don't know. Perhaps you can do better. It might also be possible to improve the time analysis of the same algorithm. $\endgroup$ – Yuval Filmus May 16 '18 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.