Simple Linear Regression (Least Squares)

Linear regression finds the line y = slope × x + intercept that best fits the data, meaning the sum of squared errors is as small as possible. For one input variable there is an exact formula:

• slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
• intercept = ȳ - slope × x̄

where x̄ and ȳ are the means of xs and ys. If all xs are equal, return slope 0 and intercept ȳ.

Implement linear_regression(xs, ys).

Input

xs, ys: The x and y values of the data points (same length).

Output

Return [slope, intercept].

Constraints

1 ≤ number of points ≤ 10,000

-10,000 ≤ each value ≤ 10,000

Examples

Input:
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]

Expected output:
expected = [2.0, 1.0]

Input:
std::vector<double> xs = {1.0, 2.0, 3.0, 4.0};
std::vector<double> ys = {3.0, 5.0, 7.0, 9.0};

Expected output:
std::vector<double> expected = {2.0, 1.0};

Input:
double[] xs = new double[] {1.0, 2.0, 3.0, 4.0};
double[] ys = new double[] {3.0, 5.0, 7.0, 9.0};

Expected output:
double[] expected = new double[] {2.0, 1.0};

Input:
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]

Expected output:
expected = [0.5, 1.5]

Input:
std::vector<double> xs = {0.0, 1.0, 2.0};
std::vector<double> ys = {1.0, 3.0, 2.0};

Expected output:
std::vector<double> expected = {0.5, 1.5};

Input:
double[] xs = new double[] {0.0, 1.0, 2.0};
double[] ys = new double[] {1.0, 3.0, 2.0};

Expected output:
double[] expected = new double[] {0.5, 1.5};

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

• scikit-learn, Linear models
• Stanford CS229 Machine Learning, lecture notes