ในปัญหานี้ เราได้ตัวเลขสองตัว L และ R เรายังมีอาร์เรย์ arr[] ที่ arr[i] =i*(-1)^i . งานของเราคือสร้างโปรแกรมเพื่อคำนวณผลรวมขององค์ประกอบจากดัชนี L ถึง R ในอาร์เรย์เมื่อ arr[i] =i*(-1)^i.
ดังนั้น เราต้องหาผลรวมขององค์ประกอบภายในช่วง [L, R] ของอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
L = 2 , R = 6
ผลผลิต
4
คำอธิบาย
arr[] = {-1, 2, -3, 4, -5, 6}
Sum = 2+ (-3) + 4 + (-5) + 6 = 4 วิธีแก้ปัญหาอย่างง่ายคือการวนซ้ำจาก L ถึง R แล้วบวกเลขคู่ทั้งหมดแล้วลบเลขคี่ทั้งหมด แล้วสุดท้ายก็คืนผลรวม
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
#include <math.h>
using namespace std;
int CalcArrSumLtoR(int L, int R) {
int sum = 0;
for (int i = L; i <= R; i++){
sum += (i * pow((-1), i));
}
return sum;
}
int main() {
int L = 3, R = 15;
cout<<"Sum of elements of array from index "<<L<<" to "<<R<<" is "lt;lt;CalcArrSumLtoR(L, R);
return 0;
} ผลลัพธ์
Sum of elements of array from index 3 to 15 is -9
นี่ไม่ใช่แนวทางที่มีประสิทธิภาพและจะแก้ปัญหาความซับซ้อนของเวลา O(n)
วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้สูตรสำหรับผลรวมของเลขคี่ n ดังนั้น
ผลรวมของเลขคี่ n ตัวแรก =n*n
ผลรวมของเลขคู่ n ตัวแรก =n*(n+1)
ที่นี่ผลรวมสุดท้ายจะถูกคำนวณเป็น
sum = (sum of first R even number - sum of first (L-1) even number ) - (sum of first R odd number - sum of first (L-1) odd number )
* จะมี N/2 คู่/เลขคี่จนถึง n. กล่าวคือจะมีเลขคู่ R/2 ดังนั้น เราจะใช้ R/2 และ L/2 ในการคำนวณผลรวม
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
long int findSum(int n, bool isEven) {
long int total = 0;
if(isEven == true){
total = (n) / 2;
return (total * (total+1));
}
else {
total = (n + 1) / 2;
return total * total;
}
}
int CalcArrSumLtoR(int L, int R) {
return (findSum(R, true) - findSum(L - 1, true))- (findSum(R, false) - findSum(L - 1, false));
}
int main() {
int L = 3, R = 15;
cout<<"Sum of elements of array from index "<<L<<" to "<<R<<" is "<<CalcArrSumLtoR(L, R);
return 0;
} ผลลัพธ์
Sum of elements of array from index 3 to 15 is -9
