Problem Statement
F is a function that is defined on all real numbers from the closed interval [1,N].
You are given a int[] Y with N elements.
For each i (1 <= i <= N) we have F(i) = Y[i-1].
Additionally, you know that F is piecewise linear: for each i, on the interval [i,i+1] F is a linear function.
The function F is uniquely determined by this information.
For example, if F(4)=1 and F(5)=6 then we must have F(4.7)=4.5.
As another example, this is the plot of the function F for Y = {1, 4, -1, 2}.
Given a real number y, we can count the number of solutions to the equation F(x)=y. For example, for the function plotted above there are 0 solutions for y=7, there is 1 solution for y=4, and there are 3 solutions for y=1.1. We are looking for the largest number of solutions such an equation can have. For the function plotted above the answer would be 3: there is no y such that F(x)=y has more than 3 solutions.
If there is an y such that the equation F(x)=y has infinitely many solutions, return -1. Otherwise, return the maximum possible number of solutions such an equation may have.
As another example, this is the plot of the function F for Y = {1, 4, -1, 2}.
Given a real number y, we can count the number of solutions to the equation F(x)=y. For example, for the function plotted above there are 0 solutions for y=7, there is 1 solution for y=4, and there are 3 solutions for y=1.1. We are looking for the largest number of solutions such an equation can have. For the function plotted above the answer would be 3: there is no y such that F(x)=y has more than 3 solutions.
If there is an y such that the equation F(x)=y has infinitely many solutions, return -1. Otherwise, return the maximum possible number of solutions such an equation may have.
Definition
- Class:
- PiecewiseLinearFunction
- Method:
- maximumSolutions
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int maximumSolutions(int[] Y)
- (be sure your method is public)
Constraints
- Y will contain between 2 and 50 elements, inclusive.
- Each element of Y will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
{3, 2}Returns: 1
The graph of this function is a line segment between (1, 3) and (2, 2). For any y such that 2 ≤ y ≤ 3 the equation F(x)=y has 1 solution, and for any other y it has 0 solutions.{4, 4}Returns: -1
The function's plot is a horizontal line segment between points (1, 4) and (2, 4). For y=4, F(x)=y has infinitely many solutions.{1, 4, -1, 2}Returns: 3
This is the example from the problem statement. Three solutions are obtained for any value of y between 1 and 2, inclusive:{2, 1, 2, 1, 3, 2, 3, 2}Returns: 5
{125612666, -991004227, 0, 6, 88023, -1000000000, 1000000000, -1000000000, 1000000000}Returns: 6
Back to all problems