Split Array into Fibonacci Sequence
Memorial Day Problem: https://leetcode.com/problems/split-array-into-fibonacci-sequence/description/
public class Solution
{
public IList<int> SplitIntoFibonacci(string S)
{
List<int> retVal = new List<int>();
int f1 = 0;
for (int i = 0; i < S.Length; i++)
{
f1 = 10 * f1 + (S[i] - '0');
if (f1.ToString().Length != i + 1) continue;
int f2 = 0;
for (int j = i + 1; j < S.Length - 1; j++)
{
f2 = 10 * f2 + (S[j] - '0');
if (f2.ToString().Length != j - i) continue;
int f3 = f1 + f2;
if (Valid(f2, f3, S.Substring(j + 1)))
{
retVal.Add(f1);
retVal.Add(f2);
S = S.Substring(f1.ToString().Length + f2.ToString().Length);
while (S.Length != 0)
{
retVal.Add(f3);
S = S.Substring(f3.ToString().Length);
f1 = f3;
f3 = f3 + f2;
f2 = f1;
}
return retVal;
}
}
}
return retVal;
}
public bool Valid(int previous, int current, string S)
{
if (S.Length == 0) return true;
if (!S.StartsWith(current.ToString())) return false;
return Valid(current, previous + current, S.Substring(current.ToString().Length));
}
}
Given a string
S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].
Formally, a Fibonacci-like sequence is a list
F of non-negative integers such that:0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);F.length >= 3;- and
F[i] + F[i+1] = F[i+2]for all0 <= i < F.length - 2.
Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.
Return any Fibonacci-like sequence split from
One strategy to solve the problem is to do an N^2 nested-loop thru the array (given that the array length is 200, this would cost you 40,000, which is reasonable) where the outer-loop corresponds to the F1 in the Fibonacci sequence and the inner-loop corresponds to the F2 in the Fibonacci sequence. From that point on you'll calculate F3 (simple: F3 = F1 + F2) and will check if the rest of the string S forms a valid Fibonacci sequence. Given that the Fibonacci sequence grows up exponentially, it would mean that this check would run in LogN, for a total of N^2LogN complexity, roughly less than 400,000 iterations which is very small and fast. Code is below, Happy Memorial Day!!! Marcelo.S, or return [] if it cannot be done.
{
public IList<int> SplitIntoFibonacci(string S)
{
List<int> retVal = new List<int>();
int f1 = 0;
for (int i = 0; i < S.Length; i++)
{
f1 = 10 * f1 + (S[i] - '0');
if (f1.ToString().Length != i + 1) continue;
int f2 = 0;
for (int j = i + 1; j < S.Length - 1; j++)
{
f2 = 10 * f2 + (S[j] - '0');
if (f2.ToString().Length != j - i) continue;
int f3 = f1 + f2;
if (Valid(f2, f3, S.Substring(j + 1)))
{
retVal.Add(f1);
retVal.Add(f2);
S = S.Substring(f1.ToString().Length + f2.ToString().Length);
while (S.Length != 0)
{
retVal.Add(f3);
S = S.Substring(f3.ToString().Length);
f1 = f3;
f3 = f3 + f2;
f2 = f1;
}
return retVal;
}
}
}
return retVal;
}
public bool Valid(int previous, int current, string S)
{
if (S.Length == 0) return true;
if (!S.StartsWith(current.ToString())) return false;
return Valid(current, previous + current, S.Substring(current.ToString().Length));
}
}
Awesome problem and a very nice, Marcelo! Your solution takes advantage of the problem statement very well! My solution is not nearly as fancy and uses a good old backtracking with tree pruning. In practice it works pretty fast (4ms) though :)
ReplyDeleteclass Solution {
private:
bool canSplit(const string& s, int idx, vector& state) const {
if (idx == s.size() && state.size() >= 3) return true; // F.length >= 3
long num = 0;
for (int i = idx; i < s.size(); ++i) {
if (i != idx && s[idx] == '0') return false; // each piece must not have extra leading zeroes
num = num * 10 + (s[i] - '0');
if (num > numeric_limits::max()) return false; // 0 <= F[i] <= 2^31 - 1
if (state.size() >= 2 && (state[state.size()-2] + state.back() != num)) continue; // F[i] + F[i+1] = F[i+2]
state.push_back(num);
if (canSplit(s, i+1, state)) return true;
state.pop_back();
}
return false;
}
public:
vector splitIntoFibonacci(const string& S) {
vector state;
if (canSplit(S, 0, state)) return state;
return {};
}
};
https://leetcode.com/problems/split-array-into-fibonacci-sequence/discuss/135687/4ms-backtracking-in-C++
Cheers,
Taras