C++でarr[i]=i *（-1）^ iの場合、配列内のインデックスLからRまでの要素の合計

この問題では、LとRの2つの数値が与えられます。 arr [i] =i *（-1）^iとなる配列arr[]もあります。 。私たちのタスクは、arr [i] =i *（-1）^ iの場合に、配列内のインデックスLからRまでの要素の合計を計算するプログラムを作成することです。

したがって、配列の範囲[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までN/2の偶数/奇数があります。つまり、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