Problem Statement
Triangular numbers are numbers that can be obtained when counting items arranged into a triangle - in other words, they are sums of prefixes of the sequence of all positive integers.
The smallest few triangular numbers are 1, 3, 6, 10, 15, 21, ...
A permutation of order N is a sequence of length N that contains each of the numbers from 1 to N exactly once.
A permutation called a cyclic triangular permutation if it has the following property: if you place the elements of the permutation around a circle, each pair of adjacent elements would sum to a triangular number.
For example, {1, 2, 8, 7, 3, 12, 9, 6, 4, 11, 10, 5} is a cyclic triangular permutation. This is because 1+2, 2+8, 8+7, 7+3, ..., 10+5, and also 5+1 are all triangular numbers.
Given N, determine whether a cyclic triangular permutation of order N exists. If yes, return any one such permutation. If no, return an empty int[].
Definition
- Class:
- AllTriangles
- Method:
- construct
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] construct(int N)
- (be sure your method is public)
Constraints
- N will be between 2 and 200, inclusive.
Examples
2
Returns: {1, 2 }Both {1, 2} and {2, 1} are valid cyclic triangular permutations.3
Returns: { }Regardless of how you place the numbers 1, 2, 3 onto a circle, 2 and 3 will be adjacent, and their sum 2+3 is not a triangular number.12
Returns: {1, 2, 8, 7, 3, 12, 9, 6, 4, 11, 10, 5 }The example from the problem statement.