Tổng các phần tử từ chỉ số L đến R trong một mảng khi arr [i] =i * (-1) ^ i trong C ++

Trong bài toán này, chúng ta được cho hai số L và R. Chúng ta cũng có một mảng arr [] sao cho arr [i] =i * (- 1) ^ i . Nhiệm vụ của chúng ta là tạo một chương trình để tính tổng của phần tử từ chỉ số L đến R trong một mảng khi arr [i] =i * (- 1) ^ i.

Vì vậy, chúng ta cần tìm tổng các phần tử trong phạm vi [L, R] của mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

L = 2 , R = 6

Đầu ra

4

Giải thích

arr[] = {-1, 2, -3, 4, -5, 6}
Sum = 2+ (-3) + 4 + (-5) + 6 = 4

Một giải pháp đơn giản cho vấn đề sẽ là chạy một vòng lặp từ L đến R, sau đó cộng tất cả các số chẵn và trừ tất cả các số lẻ. Và cuối cùng trả lại tổng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

Sum of elements of array from index 3 to 15 is -9

Đây không phải là một cách tiếp cận hiệu quả và sẽ giải quyết vấn đề với độ phức tạp về thời gian là O (n).

Một giải pháp hiệu quả sẽ là sử dụng công thức tính tổng của n số lẻ. Vì vậy,

Tổng của n số lẻ đầu tiên =n * n

Tổng của n số chẵn đầu tiên =n * (n + 1)

Ở đây, tổng cuối cùng sẽ được tính là

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 )

* Sẽ có N / 2 số chẵn / lẻ cho đến n. tức là sẽ có R / 2 số chẵn. Vì vậy, chúng tôi sẽ sử dụng R / 2 và L / 2 để tính tổng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

Sum of elements of array from index 3 to 15 is -9