Sum of the elements from index L to R in an array when arr[i] = i * (-1)^i

0 0 5 minutes read

Given two integers $L$ and $R$ and an array arr[] every element of which at index $i$ is calculated as arr[i] = i * (-1)ⁱ. The task is to find the sum of these elements of the array within the index range $[L, R]$ .

Examples:

Input: L = 1 , R = 5
Output: -3
Sum = (-1) + 2 + (-3) + 4 + (-5) = -3

Input: L = 5 , R = 100000000
Output: 49999998

Naive Approach: According to the definition of array elements, each odd element of the array is negative and even element is positive. So, to find the sum run a for loop from (L to R) and maintain the sum of all the odd(negative) and even(positive) numbers. Finally, return the sum.

Efficient Approach: It can be noted that the sum of all the odd elements of this series will always be equal to (totalOdd)² where totalOdd = total number of odd elements and sum of the even numbers will be totalEven * (totalEven + 1). Now, all we have to do is to find the sum of all the odd elements upto L and upto R. Store the difference of both to get the sum of all the odd elements between L and R. Do this same for even numbers and finally return the difference of even and odd sums.

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to return the odd sum
long int Odd_Sum(int n)
{
 
    // total odd elements upto n
    long int total = (n + 1) / 2;
 
    // sum of odd elements upto n
    long int odd = total * total;
 
    return odd;
}
 
// function to return the even sum
long int Even_Sum(int n)
{
 
    // total even elements upto n
    long int total = (n) / 2;
 
    // sum of even elements upto n
    long int even = total * (total + 1);
 
    return even;
}
 
// Function to find sum from L to R.
int sumLtoR(int L, int R)
{
 
    long int odd_sum, even_sum;
 
    odd_sum = Odd_Sum(R) - Odd_Sum(L - 1);
 
    even_sum = Even_Sum(R) - Even_Sum(L - 1);
 
    // return final sum from L to R
    return even_sum - odd_sum;
}
 
// Driver Program
int main()
{
 
    int L = 1, R = 5;
 
    // function call to print answer
    cout << sumLtoR(L, R);
 
    return 0;
}

Java

// Java implementation of above approach
 
import java.io.*;
 
class GFG {
     
 
 
// function to return the odd sum
static long  Odd_Sum(int n)
{
 
    // total odd elements upto n
    long  total = (n + 1) / 2;
 
    // sum of odd elements upto n
    long  odd = total * total;
 
    return odd;
}
 
// function to return the even sum
static long  Even_Sum(int n)
{
 
    // total even elements upto n
    long  total = (n) / 2;
 
    // sum of even elements upto n
    long  even = total * (total + 1);
 
    return even;
}
 
// Function to find sum from L to R.
static long sumLtoR(int L, int R)
{
 
    long  odd_sum, even_sum;
 
    odd_sum = Odd_Sum(R) - Odd_Sum(L - 1);
 
    even_sum = Even_Sum(R) - Even_Sum(L - 1);
 
    // return final sum from L to R
    return even_sum - odd_sum;
}
 
// Driver Program
 
    public static void main (String[] args) {
        int L = 1, R = 5;
 
    // function call to print answer
    System.out.println( sumLtoR(L, R));
    }
}
// This code is contributed by shs..

Python3

# Python3 implementation of above approach
 
# function to return the odd sum
def Odd_Sum(n):
 
    # total odd elements upto n
    total =(n+1)//2
 
    # sum of odd elements upto n
    odd = total*total
    return odd
 
# function to return the even sum
def Even_Sum(n):
 
    # total even elements upto n
    total = n//2
 
    # sum of even elements upto n
    even = total*(total+1)
    return even
 
def sumLtoR(L,R):
    odd_sum = Odd_Sum(R)-Odd_Sum(L-1)
    even_sum = Even_Sum(R)- Even_Sum(L-1)
 
    # return final sum from L to R
    return even_sum-odd_sum
 
 
# Driver code
L =1; R = 5
print(sumLtoR(L,R))
 
# This code is contributed by Shrikant13

C#

// C# implementation of above approach
class GFG
{
     
// function to return the odd sum
static long Odd_Sum(int n)
{
 
    // total odd elements upto n
    long total = (n + 1) / 2;
 
    // sum of odd elements upto n
    long odd = total * total;
 
    return odd;
}
 
// function to return the even sum
static long Even_Sum(int n)
{
 
    // total even elements upto n
    long total = (n) / 2;
 
    // sum of even elements upto n
    long even = total * (total + 1);
 
    return even;
}
 
// Function to find sum from L to R.
static long sumLtoR(int L, int R)
{
    long odd_sum, even_sum;
 
    odd_sum = Odd_Sum(R) - Odd_Sum(L - 1);
 
    even_sum = Even_Sum(R) - Even_Sum(L - 1);
 
    // return final sum from L to R
    return even_sum - odd_sum;
}
 
// Driver Code
public static void Main () 
{
    int L = 1, R = 5;
 
    // function call to print answer
    System.Console.WriteLine(sumLtoR(L, R));
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP implementation of above approach
 
// function to return the odd sum
function Odd_Sum($n)
{
 
    // for total odd elements upto n
    // divide by 2
    $total = ($n + 1) >> 1;
 
    // sum of odd elements upto n
    $odd = $total * $total;
 
    return $odd;
}
 
// function to return the even sum
function Even_Sum($n)
{
 
    // for total even elements upto n
    // divide by 2
    $total = $n >> 1;
     
    // sum of even elements upto n
    $even = $total * ($total + 1);
 
    return $even;
}
 
// Function to find sum from L to R.
function sumLtoR($L, $R)
{
    $odd_sum = Odd_Sum($R) - 
               Odd_Sum($L - 1);
 
    $even_sum = Even_Sum($R) - 
                Even_Sum($L - 1);
 
     
    // print final sum from L to R
    return $even_sum - $odd_sum ;
}
 
// Driver Code
$L = 1 ;
$R = 5;
 
// function call to print answer
echo sumLtoR($L, $R);
 
// This code is contributed by ANKITRAI1
?>

Javascript

<script>
 
// Javascript implementation of above approach
 
// Function to return the odd sum
function Odd_Sum(n)
{
     
    // Total odd elements upto n
    var total = parseInt((n + 1) / 2);
 
    // Sum of odd elements upto n
    var odd = total * total;
 
    return odd;
}
 
// Function to return the even sum
function Even_Sum(n)
{
     
    // Total even elements upto n
    var total = parseInt((n) / 2);
 
    // Sum of even elements upto n
    var even = total * (total + 1);
 
    return even;
}
 
// Function to find sum from L to R.
function sumLtoR(L, R)
{
    var odd_sum, even_sum;
 
    odd_sum = Odd_Sum(R) - Odd_Sum(L - 1);
    even_sum = Even_Sum(R) - Even_Sum(L - 1);
 
    // Return final sum from L to R
    return even_sum - odd_sum;
}
 
// Driver code
var L = 1, R = 5;
 
// Function call to print answer
document.write(sumLtoR(L, R));
 
// This code is contributed by SoumikMondal
 
</script>

Output

-3

Complexity Analysis:

Time Complexity: O(1)
Auxiliary Space: O(1), since no extra space has been taken.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!