Problem Statement
We have a sequence of N positive integers: a[0] through a[N-1].
You do not know these integers.
All you know is the number of trailing zeros in their binary representations.
You are given a
For example, suppose that a[0]=40. In binary, 40 is 101000 which ends in three zeros. Therefore, d[0] will be 3.
You like geometric sequences. (See the Notes section for a definition of a geometric sequence.) You would like to count all non-empty contiguous subsequences of the sequence a[0], a[1], ..., a[N-1] that can be geometric sequences (given the information you have in d).
More precisely: For each pair (i,j) such that 0 <= i <= j <= N-1, we ask the following question: "Given the values d[i] through d[j], is it possible that the values a[i] through a[j] form a geometric sequence?"
For example, suppose that d = {0,1,2,3,2}. For i=0 and j=3 the answer is positive: it is possible that the values a[0] through a[3] are {1,2,4,8} which is a geometric sequence. For i=1 and j=4 the answer is negative: there is no geometric sequence with these numbers of trailing zeros in binary.
Compute and return the number of contiguous subsequences of a[0], a[1], ..., a[N-1] that can be geometric sequences.
Definition
- Class:
- PotentialGeometricSequence
- Method:
- numberOfSubsequences
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int numberOfSubsequences(int[] d)
- (be sure your method is public)
Notes
- A geometric sequence is any sequence g[0], g[1], ..., g[k-1] such that there is a real number q (the quotient) with the property that for each valid i, g[i+1] = g[i]*q. For example, {1,2,4,8} is a geometric sequence with q=2, {7,7,7} is a geometric sequence with q=1, and {18,6,2} is a geometric sequence with q=1/3.
Constraints
- N will be between 1 and 50, inclusive.
- d will contain exactly N elements.
- Each element of d will be between 0 and 100, inclusive.
Examples
{0,1,2}
Returns: 6
One possibility is that a[0]=3, a[1]=6, and a[2]=12. In this case, all contiguous subsequences of this sequence are geometric.
{1,2,4}
Returns: 5
All one-element and two-element subsequences are geometric. The entire sequence cannot be geometric.
{3,2,1,0}
Returns: 10
{1,2,4,8,16}
Returns: 9
{1,3,5,5,5,5,64,4,23,2,3,4,5,4,3}
Returns: 37
{0,50,100,50,0}
Returns: 11
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
Returns: 1275
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
Returns: 1275
{29,21,13,5,6,7,8,12,10}
Returns: 23
{100,0,50,0,0}
Returns: 9
{1,2,3,4,6,8,10}
Returns: 19
{60,89,100,97,93,6,20,21,75,50,25,0,26,27,28,29,30,85,62,39,16,35,53,25,38,39,40,20,92,92,44,15,35,72,60,75,90}
Returns: 87
{60,80,100,89,5,11,55,36,2,68,77,53,83,5,40,75,22,37,75,55,64,73,82,69,78,87,60}
Returns: 59
{50,50,50,50,50,50,50,50,73,45,17,82,76,78,80,82,84,86,88,74,92,94,96,98,13,57,31,5,63,70,77,84,91,98,23,10,23,36,49,62,75,88,80,78,76,74,72,13}
Returns: 167
{75,78,96,22,66,2,36,72,40,49,58,67,76,85,94,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73}
Returns: 396
{22,61,100}
Returns: 6
{32,26,20,14,99,8,4,0,35,20,83,80,76,72}
Returns: 32
{25,22,19,16,98,10,7,4,5,22,39,56,73,90,72,48,24,39,32,25,18,11,4,56,41,26,76,76,41,16,29,76,35,79,98,77,76,75,74,73,72,71,70,69,68,67}
Returns: 162
{22,48,22,73,23,87,93,99,82,82,82,82,82,56,52,27,2}
Returns: 41
{40,57,55,2,84,78,51,49,47,46,41,36,31,26,21,16,11,6,1,10,80,26,23,91,62,39,16,92,53,14,90,2,13,24,35,46,30,20,1,81,43,5,98,93,21,26,31,36}
Returns: 144
{99,89,39,14,9,14,56,59}
Returns: 15
{43,74,74,73,89,60,22,69,43,47,51,55,25,20,15,10,5,0,32,39,46,50,47,44,41,38,35,32,29,26,23,20,17,14,11,8,5,2,64,60,56,52,48,44,9,16,23,30,37,44}
Returns: 253
{24,19,14,9,17,35,36,30,23,16,9,2,42,43,44,45,46,47,48,51,6,37,30,23,16,9,2,7,32,51,55,44,91,67,46,83,29,36,20,15,10,5,0,65}
Returns: 127
{100,85,70,55,40,19,91,95,99,100,98,37,1,29,66}
Returns: 36
{70,73,34,16,58,97,96,93,25,31,7,8,68,73,68,72,72,67,62,57}
Returns: 42
{83,79,75,71,67,14,91,50,9,41,37,1,29,55,54,74}
Returns: 38
{71,53,17,59,58,2,31,60,89,54,41,97,8,8,4,90,31}
Returns: 36
{19,100,98,2,94,92,90,88,86,5,30,32,77,36,38,40,42,44,46,48,12,16,20}
Returns: 67
{55,98,31,26,19,19,19,19,19,19,19,19,19,38}
Returns: 55
{35,12,43,55,67,19}
Returns: 12
{7,66,65,64,21,69,43,8,30,77,69,69,18,69,69,37,67,97,42,43,11,6,1,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,45,44,43,42,11,3,39,38,37}
Returns: 191
{49,1,53,54,55,90,88,86,84,100,93,72,79,86,93,80,75,89,21,62,60,58,56,54,52,50,48,46,98,100,40,38,37,46,96,76,56,36,16,45,38,31,24,17,10,43,76,96,36,39}
Returns: 151
{5,96,40,42,44,46,82,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,67,64,61,58,55,52,49,46,43,22,37,34,31,28,25,22,19}
Returns: 445
{55,22,19,4,17,16,15,44,46,38,9,10,70,30,74,90,5,4,3,2,37,65,100,55,64,99,8,44,80,37,72,85,52,88,52,32,25,18,11,4,49,2,17,19,21,23,25,27,29,31}
Returns: 131
{59,37,75,72,69,66,63,60,57,54,51,88,57,59,61,79,74,69,64,59,54,49,44,19,3,65,72,19,14,9,4,95,97,99,76,49,45,67,75,83,91,68,96,94,96,92,98,95,92,89}
Returns: 159
{29,26,23,20,17,14,11,6,7,8,9,10,4,12,13,14,15,76,1,96,64,64,64,64,93,64,1,1,20,14,65,51,79,1,12,1,1,1,1,1,1,1,1,1,1,1,1,39,75,1}
Returns: 181
{6, 6 }
Returns: 3
{1, 2, 4 }
Returns: 5
{64, 84, 100 }
Returns: 5
{3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3 }
Returns: 55
{69, 83, 35, 3, 36, 42, 48, 61, 98, 60, 76, 89, 22, 23, 74, 95, 77, 12, 83, 94, 82, 45, 59, 29, 37, 97, 71, 66, 72, 12, 24, 37, 94, 28, 5, 64, 68, 35, 69, 39, 40, 1, 28, 89, 16, 19, 60, 98, 83, 17 }
Returns: 100
{6 }
Returns: 1
{1 }
Returns: 1
{1, 1 }
Returns: 3
{1, 0 }
Returns: 3
{0, 100, 5, 100, 12, 99, 98, 100, 32, 9, 4, 100, 78, 43, 100, 0, 1, 100, 50 }
Returns: 37
{1, 2, 2, 3 }
Returns: 7
{0, 2, 1 }
Returns: 5
{80, 81, 83 }
Returns: 5
{0, 0, 0, 4, 4, 3, 2, 1, 2, 4, 8, 12, 8, 12, 24, 0, 0, 0, 0 }
Returns: 45
{60, 20, 60, 10, 20, 30, 40, 50, 60 }
Returns: 27
{1, 1, 1, 1, 2, 1, 1, 1, 1 }
Returns: 23