Problem Statement
You have been given a sequence of numbers and would like to search for patterns. Patterns can be of the following forms:
In all of the following sequences k can not be equal to 0.
1) x,x*k,x*k*k,... where k is some real number, and x is an integer
2) x,x+k,x+k+k,... where x and k are integers
3) x^a,x^(a*k),x^(a*k*k),... where x, a and k are integers
Given a sequence of numbers, you will return the size of the largest subsequence of those numbers that obeys one of the given patterns. Patterns cannot have any missing terms. For example:
sequence = {100,3,2,4,1}
The largest valid subsequence has size 4 since 1,2,3,4 is pattern 2 with x = 1 and k = 1. It is other patterns as well.
sequence = {25,10,1,5}
The largest valid subsequence has size 3 since 1,5,25 is pattern 1 with x = 1, k = 5. It is other patterns as well. 5,10,25 is not pattern 2 with x = 5, k = 5 since 15 and 20 are missing
Note a number can only occur once for each time it occurs in the input. For example: {10,3,2,1} cannot have a subsequence of size 4 of the form 1,1,1,1 since 1 only appears once in the input. If the input was {1,1,1,1,2} then 1,1,1,1 would be valid. Also note that all arithmetic is exact (don't round).
Create a class Sequences that contains the method size, which takes an int[] sequence, and returns an int describing the size of the largest subsequence that obeys a pattern.
In all of the following sequences k can not be equal to 0.
1) x,x*k,x*k*k,... where k is some real number, and x is an integer
2) x,x+k,x+k+k,... where x and k are integers
3) x^a,x^(a*k),x^(a*k*k),... where x, a and k are integers
Given a sequence of numbers, you will return the size of the largest subsequence of those numbers that obeys one of the given patterns. Patterns cannot have any missing terms. For example:
sequence = {100,3,2,4,1}
The largest valid subsequence has size 4 since 1,2,3,4 is pattern 2 with x = 1 and k = 1. It is other patterns as well.
sequence = {25,10,1,5}
The largest valid subsequence has size 3 since 1,5,25 is pattern 1 with x = 1, k = 5. It is other patterns as well. 5,10,25 is not pattern 2 with x = 5, k = 5 since 15 and 20 are missing
Note a number can only occur once for each time it occurs in the input. For example: {10,3,2,1} cannot have a subsequence of size 4 of the form 1,1,1,1 since 1 only appears once in the input. If the input was {1,1,1,1,2} then 1,1,1,1 would be valid. Also note that all arithmetic is exact (don't round).
Create a class Sequences that contains the method size, which takes an int[] sequence, and returns an int describing the size of the largest subsequence that obeys a pattern.
Definition
- Class:
- Sequences
- Method:
- size
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int size(int[] sequence)
- (be sure your method is public)
Notes
- 0^0 is undefined and cannot be a part of a pattern
Constraints
- list contains between 2 and 50 elements inclusive
- Each element of sequence is between -1000000000 and 1000000000 inclusive
Examples
{100,3,2,4,1}Returns: 4
The example from above{25,10,1,5}Returns: 3
Another example from above{1,1,1,1,2}Returns: 4
The four 1's are the only possible pattern. Remember k cannot be 0 so pattern 3 will not work for all 5.{-1,-1,-1,1,1,1,1}Returns: 7
x = 1, k = -1 works for pattern 1{1,1,1,-1,1,1}Returns: 6
(-1)^1,(-1)^2,(-1)^4,(-1)^8,(-1)^16,(-1)^32 works for pattern 3{-3,9,81,6561}Returns: 4
(-3)^1,(-3)^2,(-3)^4,(-3)^8 works for pattern 3{0,1,1,1,1}Returns: 4
{900000000,1000000000,810000000,729000000}Returns: 4
Beware of big numbers.{0,0,0,0,0}Returns: 5
x = 0, k = 1, pattern 1{1,500000000,-371654656}Returns: 2
Integers can be small sometimes(be careful of overflow).{9,6,4}Returns: 3
x = 9, k = 2/3, pattern 1
Back to all problems