Problem Statement
Foobar the Frog lives on a number line.
One day, he performed a series of one or more jumps.
At the beginning he was on an integer coordinate.
The first jump in the sequence was 1 unit long.
Each subsequent jump was twice as long as the previous one.
Foobar wrote down a sequence of all coordinates he visited during his jumps, including the coordinate where he started. (Hence, this sequence consisted of J+1 integers, where J is the number of jumps Foobar made.)
Foobar then produced a new sequence of integers. The new sequence was produced in two steps. In the first step, Foobar may have erased some elements of his original sequence. (It is possible that he did not erase any elements. After the first step the sequence contained at least one element.) In the second step, Foobar may have rearranged the remaining elements arbitrarily.
You are given a long[] positions. Return "Valid" if this sequence can be obtained as the result of the process described above. In other words, return "Valid" if it is possible to rearrange the elements of positions and possibly add some new elements in such a way that the reconstructed sequence corresponds to Foobar's way of jumping. Otherwise, return "Invalid".
Foobar wrote down a sequence of all coordinates he visited during his jumps, including the coordinate where he started. (Hence, this sequence consisted of J+1 integers, where J is the number of jumps Foobar made.)
Foobar then produced a new sequence of integers. The new sequence was produced in two steps. In the first step, Foobar may have erased some elements of his original sequence. (It is possible that he did not erase any elements. After the first step the sequence contained at least one element.) In the second step, Foobar may have rearranged the remaining elements arbitrarily.
You are given a long[] positions. Return "Valid" if this sequence can be obtained as the result of the process described above. In other words, return "Valid" if it is possible to rearrange the elements of positions and possibly add some new elements in such a way that the reconstructed sequence corresponds to Foobar's way of jumping. Otherwise, return "Invalid".
Definition
- Class:
- Jumps
- Method:
- isValidList
- Parameters:
- long[]
- Returns:
- String
- Method signature:
- String isValidList(long[] positions)
- (be sure your method is public)
Notes
- The numbers Foobar erased from the list could have been arbitrary. In particular, the erased numbers did not necessarily satisfy the constraints given for positions.
Constraints
- positions will contain between 1 and 50 elements, inclusive.
- Each element of positions will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
Examples
{1, 2, 8, 16, 4}Returns: "Valid"
One possibility is that Foobar's original list was [1, 2, 4, 8, 16] and he only rearranged it.{1, 2, 3}Returns: "Valid"
Foobar's original list might have been [2, 1, 3].{1, 2, 3, 4}Returns: "Invalid"
{6, 62, 30, 11, 10, 12}Returns: "Valid"
{1, 1000000000000000000, 2}Returns: "Valid"
{1, 1000000000000000000, 2, 999999999999999999}Returns: "Invalid"
{1, 1}Returns: "Invalid"
Back to all problems