이 문제에서는 두 개의 숫자 L과 R이 제공됩니다. 또한 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