Problem Statement
Janusz is a young physicist.
Recently he has been studying a dynamic system.
There are n elements in the system.
We will label them 0 through n-1.
The set of all elements will be denoted E.
Janusz models the changes in his system using a function that operates on elements of E.
You are given this function as a int[] f with n elements, each between 0 and n-1, inclusive.
The int[] f describes Janusz's function as follows:
For each valid i, if the function is given the input i, its output will be f[i].
For Janusz, invariant subsets of E have a special significance.
A subset S of the set E is called invariant (with respect to f) if it has the following property: for any x in S, f[x] is also in S. For example, the entire set E is invariant (for any f). The empty set is always invariant as well.
Given is the int[] f. Compute and return the number of invariant subsets of E (including E itself and the empty set).
Definition
- Class:
- InvariantSets
- Method:
- countSets
- Parameters:
- int[]
- Returns:
- long
- Method signature:
- long countSets(int[] f)
- (be sure your method is public)
Notes
- You may assume that the return value will fit into integer type long.
Constraints
- f will have between 1 and 50 elements, inclusive.
- Each element of f will be between 0 and n-1, inclusive, where n is the number of elements of f.
Examples
{1,0,0,0}Returns: 5
The invariant sets are: {}, {0,1}, {0,1,2}, {0,1,3}, {0,1,2,3}.{1,2,0}Returns: 2
There are only 2 invariants sets: {} and {0,1,2}.{0,0,1,2}Returns: 5
The invariant sets are: {}, {0}, {0,1}, {0,1,2}, {0,1,2,3}.{0,1,2,3,4,5}Returns: 64
Every set is invariant when f(x)=x for all x.{12, 10, 0, 4, 0, 6, 3, 8, 9, 14, 1, 5, 6, 12, 5}Returns: 90
Back to all problems