Dado un número N, cree una array tal que la primera mitad de la array se llene con números impares hasta N, y la segunda mitad de la array se llene con números pares. También se dan los índices L y R, la tarea es imprimir la suma de los elementos en la array en el rango [L, R].
Ejemplos:
Entrada: N = 12, L = 1, R = 11
Salida: 66
La array así formada es {1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10, 12}
La suma entre índice 1 y el índice 11 es 66 {1+3+5+7+9+11+2+4+6+8+10}Entrada: N = 11, L = 3 y R = 7
Salida: 34
La array formada es {1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10}
La suma entre el índice 3 y el índice 7 es 34 {5+7+9+11+2}
Un enfoque ingenuo será formar la array de tamaño N e iterar de L a R y devolver la suma.
C++
// C++ program to find the sum between L-R
// range by creating the array
// Naive Approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the sum between L and R
int rangesum(int n, int l, int r)
{
// array created
int arr[n];
// fill the first half of array
int c = 1, i = 0;
while (c <= n) {
arr[i++] = c;
c += 2;
}
// fill the second half of array
c = 2;
while (c <= n) {
arr[i++] = c;
c += 2;
}
int sum = 0;
// find the sum between range
for (i = l - 1; i < r; i++) {
sum += arr[i];
}
return sum;
}
// Driver Code
int main()
{
int n = 12;
int l = 1, r = 11;
cout<<(rangesum(n, l, r));
}
// This code is contributed by
// Sanjit_Prasad
Java
// Java program to find the sum between L-R
// range by creating the array
// Naive Approach
import java.io.*;
public class GFG {
// Function to find the sum between L and R
static int rangesum(int n, int l, int r)
{
// array created
int[] arr = new int[n];
// fill the first half of array
int c = 1, i = 0;
while (c <= n) {
arr[i++] = c;
c += 2;
}
// fill the second half of array
c = 2;
while (c <= n) {
arr[i++] = c;
c += 2;
}
int sum = 0;
// find the sum between range
for (i = l - 1; i < r; i++) {
sum += arr[i];
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
int n = 12;
int l = 1, r = 11;
System.out.println(rangesum(n, l, r));
}
}
Python3
# Python3 program to find the sum between L-R # range by creating the array # Naive Approach # Function to find the sum between L and R def rangesum(n, l, r): # array created arr = [0] * n; # fill the first half of array c = 1; i = 0; while (c <= n): arr[i] = c; i += 1; c += 2; # fill the second half of array c = 2; while (c <= n): arr[i] = c; i += 1; c += 2; sum = 0; # find the sum between range for i in range(l - 1, r, 1): sum += arr[i]; return sum; # Driver Code if __name__ == '__main__': n = 12; l, r = 1, 11; print(rangesum(n, l, r)); # This code contributed by PrinciRaj1992
C#
// C# program to find the sum
// between L-R range by creating
// the array Naive Approach
using System;
class GFG
{
// Function to find the
// sum between L and R
static int rangesum(int n,
int l, int r)
{
// array created
int[] arr = new int[n];
// fill the first
// half of array
int c = 1, i = 0;
while (c <= n)
{
arr[i++] = c;
c += 2;
}
// fill the second
// half of array
c = 2;
while (c <= n)
{
arr[i++] = c;
c += 2;
}
int sum = 0;
// find the sum
// between range
for (i = l - 1; i < r; i++)
{
sum += arr[i];
}
return sum;
}
// Driver Code
public static void Main()
{
int n = 12;
int l = 1, r = 11;
Console.WriteLine(rangesum(n, l, r));
}
}
// This code is contributed
// by inder_verma.
PHP
<?php
// PHP program to find the sum between
// L-R range by creating the array
// Naive Approach
// Function to find the sum between L and R
function rangesum($n, $l, $r)
{
// array created
$arr = array_fill(0, $n, 0);
// fill the first half of array
$c = 1;
$i = 0;
while ($c <= $n)
{
$arr[$i++] = $c;
$c += 2;
}
// fill the second half of array
$c = 2;
while ($c <= $n)
{
$arr[$i++] = $c;
$c += 2;
}
$sum = 0;
// find the sum between range
for ($i = $l - 1; $i < $r; $i++)
{
$sum += $arr[$i];
}
return $sum;
}
// Driver Code
$n = 12;
$l = 1;
$r = 11;
echo(rangesum($n, $l, $r));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find the sum between L-R
// range by creating the array
// Naive Approach
// Function to find the sum between L and R
function rangesum(n, l, r)
{
// array created
let arr = new Array(n);
// fill the first half of array
let c = 1, i = 0;
while (c <= n) {
arr[i++] = c;
c += 2;
}
// fill the second half of array
c = 2;
while (c <= n) {
arr[i++] = c;
c += 2;
}
let sum = 0;
// find the sum between range
for (i = l - 1; i < r; i++) {
sum += arr[i];
}
return sum;
}
// Driver Code
let n = 12;
let l = 1, r = 11;
document.write(rangesum(n, l, r));
// This code is contributed by rishavmahato348.
</script>
Producción:
66
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente: sin construir la array, el problema se puede resolver con una complejidad O(1). Considere el punto medio de la secuencia así formada. Entonces puede haber 3 posibilidades para L y R.
- l y r están a la derecha del punto medio.
- l y r están a la izquierda del punto medio.
- l está a la izquierda del punto medio y r está a la izquierda del punto medio.
Para el primer y segundo caso, simplemente encuentre el número que corresponde a la posición l-ésima desde el inicio o medio y el número que corresponde a la posición r-ésima desde el inicio o medio. La siguiente fórmula se puede utilizar para encontrar la suma:
sum = (no. of terms in the range)*(first term + last term)/2
Para el tercer caso, considérelo como [L-mid] y [mid-R] y luego aplique las fórmulas del caso 1 y caso 2 como se mencionó anteriormente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum between L-R
// range by creating the array
// Naive Approach
#include<bits/stdc++.h>
using namespace std;
// // Function to calculate the sum if n is even
int sumeven(int n, int l, int r)
{
int sum = 0;
int mid = n / 2;
// both l and r are to the left of mid
if (r <= mid)
{
// first and last element
int first = (2 * l - 1);
int last = (2 * r - 1);
// Total number of terms in
// the sequence is r-l+1
int no_of_terms = r - l + 1;
// use of formula derived
sum = ((no_of_terms) * ((first + last))) / 2;
}
// both l and r are to the right of mid
else if (l >= mid)
{
// first and last element
int first = (2 * (l - n / 2));
int last = (2 * (r - n / 2));
int no_of_terms = r - l + 1;
// Use of formula derived
sum = ((no_of_terms) * ((first + last))) / 2;
}
// left is to the left of mid and
// right is to the right of mid
else
{
// Take two sums i.e left and
// right differently and add
int sumleft = 0, sumright = 0;
// first and last element
int first_term1 = (2 * l - 1);
int last_term1 = (2 * (n / 2) - 1);
// total terms
int no_of_terms1 = n / 2 - l + 1;
// no of terms
sumleft = ((no_of_terms1) *
((first_term1 + last_term1))) / 2;
// The first even number is 2
int first_term2 = 2;
// The last element is given by 2*(r-n/2)
int last_term2 = (2 * (r - n / 2));
int no_of_terms2 = r - mid;
// formula applied
sumright = ((no_of_terms2) *
((first_term2 + last_term2))) / 2;
sum = (sumleft + sumright);
}
return sum;
}
// Function to calculate the sum if n is odd
int sumodd(int n, int l, int r)
{
// take ceil value if n is odd
int mid = n / 2 + 1;
int sum = 0;
// // both l and r are to the left of mid
if (r <= mid)
{
// first and last element
int first = (2 * l - 1);
int last = (2 * r - 1);
// number of terms
int no_of_terms = r - l + 1;
// formula
sum = ((no_of_terms) *
((first + last))) / 2;
}
// // both l and r are to the right of mid
else if (l > mid)
{
// first and last term,
int first = (2 * (l - mid));
int last = (2 * (r - mid));
// no of terms
int no_of_terms = r - l + 1;
// formula used
sum = ((no_of_terms) *
((first + last))) / 2;
}
// If l is on left and r on right
else
{
// calculate separate sums
int sumleft = 0, sumright = 0;
// first half
int first_term1 = (2 * l - 1);
int last_term1 = (2 * mid - 1);
// calculate terms
int no_of_terms1 = mid - l + 1;
sumleft = ((no_of_terms1) *
((first_term1 + last_term1))) / 2;
// second half
int first_term2 = 2;
int last_term2 = (2 * (r - mid));
int no_of_terms2 = r - mid;
sumright = ((no_of_terms2) *
((first_term2 + last_term2))) / 2;
// add both halves
sum = (sumleft + sumright);
}
return sum;
}
// Function to find the sum between L and R
int rangesum(int n, int l, int r)
{
int sum = 0;
// If n is even
if (n % 2 == 0)
return sumeven(n, l, r);
// If n is odd
else
return sumodd(n, l, r);
}
// Driver Code
int main()
{
int n = 12;
int l = 1, r = 11;
cout << (rangesum(n, l, r));
}
// This code is contributed by 29AjayKumar
Java
// Java program to find the sum between L-R
// range by creating the array
// Efficient Approach
import java.io.*;
public class GFG {
// // Function to calculate the sum if n is even
static int sumeven(int n, int l, int r)
{
int sum = 0;
int mid = n / 2;
// both l and r are to the left of mid
if (r <= mid) {
// first and last element
int first = (2 * l - 1);
int last = (2 * r - 1);
// Total number of terms in
// the sequence is r-l+1
int no_of_terms = r - l + 1;
// use of formula derived
sum = ((no_of_terms) * ((first + last))) / 2;
}
// both l and r are to the right of mid
else if (l >= mid) {
// // first and last element
int first = (2 * (l - n / 2));
int last = (2 * (r - n / 2));
int no_of_terms = r - l + 1;
// Use of formula derived
sum = ((no_of_terms) * ((first + last))) / 2;
}
// left is to the left of mid and
// right is to the right of mid
else {
// Take two sums i.e left and
// right differently and add
int sumleft = 0, sumright = 0;
// first and last element
int first_term1 = (2 * l - 1);
int last_term1 = (2 * (n / 2) - 1);
// total terms
int no_of_terms1 = n / 2 - l + 1;
// no of terms
sumleft = ((no_of_terms1) * ((first_term1 + last_term1))) / 2;
// The first even number is 2
int first_term2 = 2;
// The last element is given by 2*(r-n/2)
int last_term2 = (2 * (r - n / 2));
int no_of_terms2 = r - mid;
// formula applied
sumright = ((no_of_terms2) * ((first_term2 + last_term2))) / 2;
sum = (sumleft + sumright);
}
return sum;
}
// Function to calculate the sum if n is odd
static int sumodd(int n, int l, int r)
{
// take ceil value if n is odd
int mid = n / 2 + 1;
int sum = 0;
// // both l and r are to the left of mid
if (r <= mid) {
// first and last element
int first = (2 * l - 1);
int last = (2 * r - 1);
// number of terms
int no_of_terms = r - l + 1;
// formula
sum = ((no_of_terms) * ((first + last))) / 2;
}
// // both l and r are to the right of mid
else if (l > mid) {
// first and last term,
int first = (2 * (l - mid));
int last = (2 * (r - mid));
// no of terms
int no_of_terms = r - l + 1;
// formula used
sum = ((no_of_terms) * ((first + last))) / 2;
}
// If l is on left and r on right
else {
// calculate separate sums
int sumleft = 0, sumright = 0;
// first half
int first_term1 = (2 * l - 1);
int last_term1 = (2 * mid - 1);
// calculate terms
int no_of_terms1 = mid - l + 1;
sumleft = ((no_of_terms1) * ((first_term1 + last_term1))) / 2;
// second half
int first_term2 = 2;
int last_term2 = (2 * (r - mid));
int no_of_terms2 = r - mid;
sumright = ((no_of_terms2) * ((first_term2 + last_term2))) / 2;
// add both halves
sum = (sumleft + sumright);
}
return sum;
}
// Function to find the sum between L and R
static int rangesum(int n, int l, int r)
{
int sum = 0;
// If n is even
if (n % 2 == 0)
return sumeven(n, l, r);
// If n is odd
else
return sumodd(n, l, r);
}
// Driver Code
public static void main(String[] args)
{
int n = 12;
int l = 1, r = 11;
System.out.println(rangesum(n, l, r));
}
}
Python3
# Python3 program to find # the sum between L-R range # by creating the array # Naive Approach # Function to calculate # the sum if n is even def sumeven(n, l, r): sum = 0 mid = n // 2 # Both l and r are # to the left of mid if (r <= mid): # First and last element first = (2 * l - 1) last = (2 * r - 1) # Total number of terms in # the sequence is r-l+1 no_of_terms = r - l + 1 # Use of formula derived sum = ((no_of_terms) * ((first + last))) // 2 # Both l and r are to the right of mid elif (l >= mid): # First and last element first = (2 * (l - n // 2)) last = (2 * (r - n // 2)) no_of_terms = r - l + 1 # Use of formula derived sum = ((no_of_terms) * ((first + last))) // 2 # Left is to the left of mid and # right is to the right of mid else : # Take two sums i.e left and # right differently and add sumleft, sumright = 0, 0 # First and last element first_term1 = (2 * l - 1) last_term1 = (2 * (n // 2) - 1) # total terms no_of_terms1 = n // 2 - l + 1 # no of terms sumleft = (((no_of_terms1) * ((first_term1 + last_term1))) // 2) # The first even number is 2 first_term2 = 2 # The last element is # last_term2 = (2 * (r - n // 2)) no_of_terms2 = r - mid # formula applied sumright = (((no_of_terms2) * ((first_term2 + last_term2))) // 2) sum = (sumleft + sumright); return sum # Function to calculate # the sum if n is odd def sumodd(n, l, r): # Take ceil value if n is odd mid = n // 2 + 1; sum = 0 # Both l and r are to # the left of mid if (r <= mid): # First and last element first = (2 * l - 1) last = (2 * r - 1) # number of terms no_of_terms = r - l + 1 # formula sum = (((no_of_terms) * ((first + last))) // 2) # both l and r are to the right of mid elif (l > mid): # first and last term, first = (2 * (l - mid)) last = (2 * (r - mid)) # no of terms no_of_terms = r - l + 1 # formula used sum = (((no_of_terms) * ((first + last))) // 2) # If l is on left and r on right else : # calculate separate sums sumleft, sumright = 0, 0 # first half first_term1 = (2 * l - 1) last_term1 = (2 * mid - 1) # calculate terms no_of_terms1 = mid - l + 1 sumleft = (((no_of_terms1) * ((first_term1 + last_term1))) // 2) # second half first_term2 = 2 last_term2 = (2 * (r - mid)) no_of_terms2 = r - mid sumright = (((no_of_terms2) * ((first_term2 + last_term2))) // 2) # add both halves sum = (sumleft + sumright) return sum # Function to find the # sum between L and R def rangesum(n, l, r): sum = 0 # If n is even if (n % 2 == 0): return sumeven(n, l, r); # If n is odd else: return sumodd(n, l, r) # Driver Code if __name__ == "__main__": n = 12 l = 1 r = 11; print (rangesum(n, l, r)) # This code is contributed by Chitranayal
C#
// C# program to find the sum
// between L-R range by creating
// the array Efficient Approach
using System;
class GFG
{
// Function to calculate
// the sum if n is even
static int sumeven(int n,
int l, int r)
{
int sum = 0;
int mid = n / 2;
// both l and r are
// to the left of mid
if (r <= mid)
{
// first and last element
int first = (2 * l - 1);
int last = (2 * r - 1);
// Total number of terms in
// the sequence is r-l+1
int no_of_terms = r - l + 1;
// use of formula derived
sum = ((no_of_terms) *
((first + last))) / 2;
}
// both l and r are
// to the right of mid
else if (l >= mid)
{
// first and last element
int first = (2 * (l - n / 2));
int last = (2 * (r - n / 2));
int no_of_terms = r - l + 1;
// Use of formula derived
sum = ((no_of_terms) *
((first + last))) / 2;
}
// left is to the left of
// mid and right is to the
// right of mid
else
{
// Take two sums i.e left and
// right differently and add
int sumleft = 0, sumright = 0;
// first and last element
int first_term1 = (2 * l - 1);
int last_term1 = (2 * (n / 2) - 1);
// total terms
int no_of_terms1 = n / 2 - l + 1;
// no of terms
sumleft = ((no_of_terms1) *
((first_term1 +
last_term1))) / 2;
// The first even
// number is 2
int first_term2 = 2;
// The last element is
// given by 2*(r-n/2)
int last_term2 = (2 * (r - n / 2));
int no_of_terms2 = r - mid;
// formula applied
sumright = ((no_of_terms2) *
((first_term2 +
last_term2))) / 2;
sum = (sumleft + sumright);
}
return sum;
}
// Function to calculate
// the sum if n is odd
static int sumodd(int n,
int l, int r)
{
// take ceil value
// if n is odd
int mid = n / 2 + 1;
int sum = 0;
// both l and r are
// to the left of mid
if (r <= mid)
{
// first and last element
int first = (2 * l - 1);
int last = (2 * r - 1);
// number of terms
int no_of_terms = r - l + 1;
// formula
sum = ((no_of_terms) *
((first + last))) / 2;
}
// both l and r are
// to the right of mid
else if (l > mid)
{
// first and last term,
int first = (2 * (l - mid));
int last = (2 * (r - mid));
// no of terms
int no_of_terms = r - l + 1;
// formula used
sum = ((no_of_terms) *
((first + last))) / 2;
}
// If l is on left
// and r on right
else
{
// calculate separate sums
int sumleft = 0, sumright = 0;
// first half
int first_term1 = (2 * l - 1);
int last_term1 = (2 * mid - 1);
// calculate terms
int no_of_terms1 = mid - l + 1;
sumleft = ((no_of_terms1) *
((first_term1 +
last_term1))) / 2;
// second half
int first_term2 = 2;
int last_term2 = (2 * (r - mid));
int no_of_terms2 = r - mid;
sumright = ((no_of_terms2) *
((first_term2 +
last_term2))) / 2;
// add both halves
sum = (sumleft + sumright);
}
return sum;
}
// Function to find the
// sum between L and R
static int rangesum(int n,
int l, int r)
{
// If n is even
if (n % 2 == 0)
return sumeven(n, l, r);
// If n is odd
else
return sumodd(n, l, r);
}
// Driver Code
public static void Main()
{
int n = 12;
int l = 1, r = 11;
Console.WriteLine(rangesum(n, l, r));
}
}
// This code is contributed
// by chandan_jnu.
Javascript
<script>
// Javascript program to find the sum between L-R
// range by creating the array
// Efficient Approach
// Function to calculate the sum if n is even
function sumeven(n,l,r)
{
let sum = 0;
let mid = Math.floor(n / 2);
// both l and r are to the left of mid
if (r <= mid) {
// first and last element
let first = (2 * l - 1);
let last = (2 * r - 1);
// Total number of terms in
// the sequence is r-l+1
let no_of_terms = r - l + 1;
// use of formula derived
sum = ((no_of_terms) * ((first + last))) / 2;
}
// both l and r are to the right of mid
else if (l >= mid) {
// // first and last element
let first = (2 * (l - n / 2));
let last = (2 * (r - n / 2));
let no_of_terms = r - l + 1;
// Use of formula derived
sum = ((no_of_terms) * ((first + last))) / 2;
}
// left is to the left of mid and
// right is to the right of mid
else {
// Take two sums i.e left and
// right differently and add
let sumleft = 0, sumright = 0;
// first and last element
let first_term1 = (2 * l - 1);
let last_term1 = (2 * (n / 2) - 1);
// total terms
let no_of_terms1 = n / 2 - l + 1;
// no of terms
sumleft = ((no_of_terms1) * ((first_term1 + last_term1))) / 2;
// The first even number is 2
let first_term2 = 2;
// The last element is given by 2*(r-n/2)
let last_term2 = (2 * (r - n / 2));
let no_of_terms2 = r - mid;
// formula applied
sumright = ((no_of_terms2) * ((first_term2 + last_term2))) / 2;
sum = (sumleft + sumright);
}
return sum;
}
// Function to calculate the sum if n is odd
function sumodd(n,l,r)
{
// take ceil value if n is odd
let mid = Math.floor(n / 2) + 1;
let sum = 0;
// // both l and r are to the left of mid
if (r <= mid) {
// first and last element
let first = (2 * l - 1);
let last = (2 * r - 1);
// number of terms
let no_of_terms = r - l + 1;
// formula
sum = ((no_of_terms) * ((first + last))) / 2;
}
// // both l and r are to the right of mid
else if (l > mid) {
// first and last term ,
let first = (2 * (l - mid));
let last = (2 * (r - mid));
// no of terms
let no_of_terms = r - l + 1;
// formula used
sum = ((no_of_terms) * ((first + last))) / 2;
}
// If l is on left and r on right
else {
// calculate separate sums
let sumleft = 0, sumright = 0;
// first half
let first_term1 = (2 * l - 1);
let last_term1 = (2 * mid - 1);
// calculate terms
let no_of_terms1 = mid - l + 1;
sumleft = ((no_of_terms1) * ((first_term1 + last_term1))) / 2;
// second half
let first_term2 = 2;
let last_term2 = (2 * (r - mid));
let no_of_terms2 = r - mid;
sumright = ((no_of_terms2) * ((first_term2 + last_term2))) / 2;
// add both halves
sum = (sumleft + sumright);
}
return sum;
}
// Function to find the sum between L and R
function rangesum(n,l,r)
{
let sum = 0;
// If n is even
if (n % 2 == 0)
return sumeven(n, l, r);
// If n is odd
else
return sumodd(n, l, r);
}
// Driver Code
let n = 12;
let l = 1, r = 11;
document.write(rangesum(n, l, r));
// This code is contributed by rag2127
</script>
Producción:
66
Complejidad temporal: O(1)
Espacio auxiliar: O(1)