Problem Statement
Given a sequence S of numbers, its difference sequence D(S) is obtained by writing down the absolute difference between each pair of consecutive elements of S. Note that the length of D(S) is always one less than the length of S.
For example, if S = {10, 50, 50, 40, 30}, we have |10-50| = 40, |50-50| = 0, |50-40| = 10 and |40-30| = 10, thus D(S) = {40, 0, 10, 10}.
You are given N and V.
Arrange the integers from 1 to N into a sequence S such that D(S) will contain exactly V distinct values.
Return the answer as a int[]. If multiple valid solutions exist, any one of them will be accepted. If there is no valid solution, return an empty int[] instead.
Definition
- Class:
- LimitedDifferences
- Method:
- arrange
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] arrange(int N, int V)
- (be sure your method is public)
Notes
- You must use each of the values from 1 to N exactly once in your sequence. In other words, you must return a permutation of those numbers.
Constraints
- N will be between 2 and 500, inclusive.
- V will be between 1 and N-1, inclusive.
Examples
7
1
Returns: {7, 6, 5, 4, 3, 2, 1 }The returned sequence S = {7, 6, 5, 4, 3, 2, 1} has the difference sequence D(S) = {1, 1, 1, 1, 1, 1}. As required, there is only one distinct value in D(S): the value 1. The sequence S = {1, 2, 3, 4, 5, 6, 7} is also a correct answer. There are no other correct answers for this test case, only these two.8
2
Returns: {1, 5, 6, 7, 8, 4, 3, 2 }The difference sequence for the example return value is {4, 1, 1, 1, 4, 1, 1}. Thus, there are exactly two distinct differences: 1 and 4.5
2
Returns: {2, 4, 1, 3, 5 }Here each consecutive pair of elements of the returned sequence has a difference of either 2 or 3.15
5
Returns: {11, 14, 12, 10, 8, 3, 7, 4, 2, 6, 1, 9, 5, 13, 15 }The differences between consecutive elements of the sequence returned as example output are 2, 3, 4, 5, and 8. There are many other valid solutions.3
2
Returns: {1, 3, 2 }