समस्या
लीनियर रिग्रेशन वह रेखा y = slope × x + intercept खोजता है जो डेटा पर सबसे अच्छी बैठती है, यानी जिसमें स्क्वेयर्ड एरर का योग सबसे कम हो। एक इनपुट वेरिएबल के लिए एक सटीक सूत्र है:
- slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
- intercept = ȳ - slope × x̄
जहाँ x̄ और ȳ, xs और ys के औसत हैं। अगर सभी xs बराबर हों, तो slope 0 और intercept ȳ लौटाएँ।
linear_regression(xs, ys) लागू करें।
इनपुट
xs, ys: डेटा पॉइंट्स के x और y मान (समान लंबाई)।
आउटपुट
[slope, intercept] लौटाएँ।
सीमाएँ
1 ≤ पॉइंट्स की संख्या ≤ 10,000
-10,000 ≤ हर मान ≤ 10,000
उदाहरण
इनपुट:
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]
अपेक्षित आउटपुट:
expected = [2.0, 1.0]
इनपुट:
std::vector<double> xs = {1.0, 2.0, 3.0, 4.0};
std::vector<double> ys = {3.0, 5.0, 7.0, 9.0};
अपेक्षित आउटपुट:
std::vector<double> expected = {2.0, 1.0};
इनपुट:
double[] xs = new double[] {1.0, 2.0, 3.0, 4.0};
double[] ys = new double[] {3.0, 5.0, 7.0, 9.0};
अपेक्षित आउटपुट:
double[] expected = new double[] {2.0, 1.0};
व्याख्या
पॉइंट्स ठीक y = 2x + 1 पर हैं। x̄ = 2.5, ȳ = 6, Σ(x - x̄)(y - ȳ) = 10 और Σ(x - x̄)² = 5, इसलिए slope = 2 और intercept = 6 - 2 × 2.5 = 1।
इनपुट:
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]
अपेक्षित आउटपुट:
expected = [0.5, 1.5]
इनपुट:
std::vector<double> xs = {0.0, 1.0, 2.0};
std::vector<double> ys = {1.0, 3.0, 2.0};
अपेक्षित आउटपुट:
std::vector<double> expected = {0.5, 1.5};
इनपुट:
double[] xs = new double[] {0.0, 1.0, 2.0};
double[] ys = new double[] {1.0, 3.0, 2.0};
अपेक्षित आउटपुट:
double[] expected = new double[] {0.5, 1.5};
व्याख्या
x̄ = 1 और ȳ = 2। Σ(x - x̄)(y - ȳ) = (-1)(-1) + 0 + (1)(0) = 1 और Σ(x - x̄)² = 2, इसलिए slope = 0.5 और intercept = 2 - 0.5 × 1 = 1.5।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Best-fit line x और y के अपने means के आसपास कैसे vary करते हैं, उससे निकलती है।
संकेत 2
पहले means निकालें, फिर slope formula के लिए numerator और denominator accumulate करें।
संकेत 3
अगर सभी x-values same हों, तो slope undefined है, इसलिए average y-value से गुजरती हुई flat line return करें।
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।