Given an array arr[] of integers and a sequence of the form:
[ 2, 3, 0, 1, 6, 7, 4, 5, … ].
Also given two integers L and R such that 
. The task is to find the sum of all numbers in a given range from L to R.
Examples:
Input : L = 0, R = 5
Output : 19
Explanation :
The arr[] is {2, 3, 0, 1, 6, 7}.
sum = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] + arr[5]
sum = 2 + 3 + 0 + 1 + 6 + 7
Hence, the sum is 19.
Input : L = 2, R = 5
Output : 14
Explanation :
The arr[] is {0, 1, 6, 7}.
sum = arr[2] + arr[3] + arr[4] + arr[5]
sum = 0 + 1 + 6 + 7
Hence, the sum is 14.
Approach:
To solve the question mentioned above we first have to observe the sequence of the array and understand how is it generated. The given array is generated from a sequence of whole numbers which is [ 0, 1, 2, 3, 4, 5, 6, … ]. Initially, we add 2 to the first two integers, then we subtract 2 from the next two integers and this goes on. So our newly formed array looks like [ 0+2, 1+2, 2-2, 3-2, 4+2, 5+2, 6-2, 7-2, … ]. Hence we generate this new sequence of integers up to R and store it in array. Finally, calculate the sum from indices in range L to R and return it.
Below is the implementation of the above approach:
C++
// C++ program to find the// sum in given range L to R#include <bits/stdc++.h> using namespace std;// Function to find the sum// within the given rangeint findSum(int L, int R){ vector<int> arr; // generating array from given sequence int i = 0; int x = 2; while (i <= R) { arr.push_back(i + x); if (i + 1 <= R) arr.push_back(i + 1 + x); x *= -1; i += 2; } // calculate the desired sum int sum = 0; for (int i = L; i <= R; ++i) sum += arr[i]; // return the sum return sum;}// Driven codeint main(){ // initialise the range int L = 0, R = 5; cout << findSum(L, R); return 0;} |
Java
// Java program to find the// sum in given range L to Rimport java.util.*;class GFG{ // Function to find the sum// within the given rangepublic static int findSum(int L, int R){ ArrayList<Integer> arr = new ArrayList<>(); // Generating array from given sequence int i = 0; int x = 2; while (i <= R) { arr.add(i + x); if (i + 1 <= R) arr.add(i + 1 + x); x *= -1; i += 2; } // Calculate the desired sum int sum = 0; for(i = L; i <= R; ++i) sum += arr.get(i); // return the sum return sum;}// Driver codepublic static void main(String[] args){ // Initialise the range int L = 0, R = 5; System.out.println(findSum(L, R));}}// This code is contributed by jrishabh99 |
Python3
# Python3 program to find the # sum in given range L to R # Function to find the sum # within the given range def findSum(L, R) : arr = [] # generating array from given sequence i = 0 x = 2 k = 0 while (i <= R) : arr.insert(k, i + x) k += 1 if (i + 1 <= R) : arr.insert(k, i + 1 + x) k += 1 x *= -1 i += 2 # calculate the desired sum sum = 0 for i in range(L, R + 1) : sum += arr[i] # return the sum return sum# Driver code # initialise the range L = 0R = 5print(findSum(L, R))# This code is contributed by Sanjit_Prasad |
C#
// C# program to find the// sum in given range L to Rusing System;using System.Collections;class GFG{ // Function to find the sum// within the given rangepublic static int findSum(int L, int R){ ArrayList arr = new ArrayList(); // Generating array from given sequence int i = 0; int x = 2; while (i <= R) { arr.Add(i + x); if (i + 1 <= R) arr.Add(i + 1 + x); x *= -1; i += 2; } // Calculate the desired sum int sum = 0; for(i = L; i <= R; ++i) sum += (int)arr[i]; // return the sum return sum;}// Driver codepublic static void Main(string[] args){ // Initialise the range int L = 0, R = 5; Console.Write(findSum(L, R));}}// This code is contributed by rutvik_56 |
Javascript
<script>//Javascript program to find the// sum in given range L to R// Function to find the sum// within the given rangefunction findSum( L, R){ var arr=[]; // generating array from given sequence var i = 0; var x = 2; while (i <= R) { arr.push(i + x); if (i + 1 <= R) arr.push(i + 1 + x); x *= -1; i += 2; } // calculate the desired sum var sum = 0; for (var i = L; i <= R; ++i) sum += arr[i]; // return the sum return sum;}var L = 0, R = 5;document.write( findSum(L, R));//This code is contributed by SoumikMondal</script> |
Output:
19
Time Complexity: O(R)
Auxiliary Space: O(R)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
