Problem Statement

A TriFibonacci sequence begins by defining the first three elements A, A and A. The remaining elements are calculated using the following recurrence:

A[i] = A[i-1] + A[i-2] + A[i-3]

You are given a int[] A which contains exactly one element that is equal to -1, you must replace this element with a positive number in a way that the sequence becomes a TriFibonacci sequence. Return this number. If no such positive number exists, return -1.

Definition

 Class: TriFibonacci Method: complete Parameters: int[] Returns: int Method signature: int complete(int[] A) (be sure your method is public)

Notes

-The constraints for the elements of the input int[] A do not necessarily apply for the replacement to the missing element.

Constraints

-A will contain between 4 and 20 elements, inclusive.
-Each element of A will be -1 or between 1 and 1000000, inclusive.
-Exactly one element of A will be -1.

Examples

0)

 {1,2,3,-1}
Returns: 6
1)

 {10, 20, 30, 60, -1 , 200}
Returns: 110
2)

 {1, 2, 3, 5, -1}
Returns: -1
 No replacement can make this sequence TriFibonacci as 5 is not equal to 1+2+3.
3)

 {1, 1, -1, 2, 3}
Returns: -1
 The missing element must be 0 for this sequence to be TriFibonacci. Since this is not a positive integer, return -1.
4)

 {-1, 7, 8, 1000000}
Returns: 999985

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10587

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13935&pm=10587

vexorian

Testers:

Rustyoldman , timmac , Nickolas , StevieT

Problem categories:

Brute Force, Math, Simple Search, Iteration