Dados dos enteros positivos L y R , la tarea es encontrar el número de pares ordenados en el rango [L, R] tal que la suma de los elementos de cada par sea par .
Ejemplos:
Entrada: L = 1, R =3
Salida: 5
Explicación:
Los pares cuya suma de elementos es par y está en el rango [1, 3] son { (1, 3), (1, 1), (2, 2) , (3, 3), (3, 1) }Entrada: L = 1, R = 1
Salida: 1
Enfoque: el problema se puede resolver usando el hecho de que la suma de dos números es par solo cuando ambos números son pares o ambos números son impares. Siga los pasos a continuación para resolver este problema:
- Cuente todos los números pares, digamos cnt_even , en el rango [L, R] . Siga los siguientes pasos para calcular:
- Si L es par , entonces cnt_par = (R/2) – (L/2) + 1 .
- Si L es impar , entonces cnt_par = (R / 2) – (L / 2) .
- El recuento de pares cuya suma de elementos es par y ambos elementos de los pares también son pares es count_even * count_even .
- Del mismo modo, cuente todos los números impares, digamos count_odd , en el rango [L, R] . Siga los siguientes pasos para calcular:
- Si L es par , entonces count_odd = ((R + 1) / 2) – ((L + 1) / 2) .
- Si L es impar , entonces count_odd = ( (R+1) / 2) – ((L + 1) / 2) + 1 .
- El recuento de pares cuya suma de elementos es par y ambos elementos de los pares también son impares es count_odd * count_odd
- Finalmente, imprima el valor de (count_odd * count_odd + count_even * count_even)
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of
// ordered pairs having even sum
int countPairs(int L, int R)
{
// Stores count of even numbers
// in the range [L, R]
int count_even;
// If L is even
if (L % 2 == 0) {
// Update count_even
count_even = (R / 2) - (L / 2) + 1;
}
else {
// Update count_odd
count_even = (R / 2) - (L / 2);
}
// Stores count of odd numbers
// in the range [L, R]
int count_odd;
if (L % 2 == 0) {
// Update count_odd
count_odd = ((R + 1) / 2) - ((L + 1) / 2);
}
else {
// Update count_odd
count_odd = ((R + 1) / 2) - ((L + 1) / 2) + 1;
}
// Stores count of pairs whose sum is even and
// both elements of the pairs are also even
count_even *= count_even;
// Stores count of pairs whose sum is even and
// both elements of the pairs are odd
count_odd *= count_odd;
// Print total ordered pairs whose sum is even
cout << count_even + count_odd;
}
// Driver Code
int main()
{
// Given L & R
int L = 1, R = 3;
// Function Call
countPairs(L, R);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find the count of
// ordered pairs having even sum
static void countPairs(int L, int R)
{
// Stores count of even numbers
// in the range [L, R]
int count_even;
// If L is even
if (L % 2 == 0)
{
// Update count_even
count_even = (R / 2) - (L / 2) + 1;
}
else {
// Update count_odd
count_even = (R / 2) - (L / 2);
}
// Stores count of odd numbers
// in the range [L, R]
int count_odd;
if (L % 2 == 0)
{
// Update count_odd
count_odd = ((R + 1) / 2) - ((L + 1) / 2);
}
else
{
// Update count_odd
count_odd = ((R + 1) / 2) - ((L + 1) / 2) + 1;
}
// Stores count of pairs whose sum is even and
// both elements of the pairs are also even
count_even *= count_even;
// Stores count of pairs whose sum is even and
// both elements of the pairs are odd
count_odd *= count_odd;
// Print total ordered pairs whose sum is even
System.out.println(count_even + count_odd);
}
// Driver Code
public static void main (String[] args)
{
// Given L & R
int L = 1, R = 3;
// Function Call
countPairs(L, R);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find the count of # ordered pairs having even sum def countPairs(L, R): # Stores count of even numbers # in the range [L, R] count_even = 0 # If L is even if (L % 2 == 0): # Update count_even count_even = ((R // 2) - (L // 2) + 1) else: # Update count_odd count_even = ((R // 2) - (L // 2)) # Stores count of odd numbers # in the range [L, R] count_odd = 0 if (L % 2 == 0): # Update count_odd count_odd = (((R + 1) // 2) - ((L + 1) // 2)) else: # Update count_odd count_odd = (((R + 1) // 2) - ((L + 1) // 2) + 1) # Stores count of pairs whose sum is # even and both elements of the pairs # are also even count_even *= count_even # Stores count of pairs whose sum is # even and both elements of the pairs # are odd count_odd *= count_odd # Print total ordered pairs whose # sum is even print (count_even + count_odd) # Driver Code if __name__ == '__main__': # Given L & R L, R = 1, 3 # Function Call countPairs(L, R) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the count of
// ordered pairs having even sum
static void countPairs(int L, int R)
{
// Stores count of even numbers
// in the range [L, R]
int count_even;
// If L is even
if (L % 2 == 0)
{
// Update count_even
count_even = (R / 2) - (L / 2) + 1;
}
else
{
// Update count_odd
count_even = (R / 2) - (L / 2);
}
// Stores count of odd numbers
// in the range [L, R]
int count_odd;
if (L % 2 == 0)
{
// Update count_odd
count_odd = ((R + 1) / 2) - ((L + 1) / 2);
}
else
{
// Update count_odd
count_odd = ((R + 1) / 2) - ((L + 1) / 2) + 1;
}
// Stores count of pairs whose sum is even and
// both elements of the pairs are also even
count_even *= count_even;
// Stores count of pairs whose sum is even and
// both elements of the pairs are odd
count_odd *= count_odd;
// Print total ordered pairs whose sum is even
Console.WriteLine(count_even + count_odd);
}
// Driver Code
public static void Main(String[] args)
{
// Given L & R
int L = 1, R = 3;
// Function Call
countPairs(L, R);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program of the above approach
// Function to find the count of
// ordered pairs having even sum
function countPairs(L, R)
{
// Stores count of even numbers
// in the range [L, R]
let count_even;
// If L is even
if (L % 2 == 0)
{
// Update count_even
count_even = (R / 2) - (L / 2) + 1;
}
else
{
// Update count_odd
count_even = (R / 2) - (L / 2);
}
// Stores count of odd numbers
// in the range [L, R]
let count_odd;
if (L % 2 == 0)
{
// Update count_odd
count_odd = ((R + 1) / 2) -
((L + 1) / 2);
}
else
{
// Update count_odd
count_odd = ((R + 1) / 2) -
((L + 1) / 2) + 1;
}
// Stores count of pairs whose sum is even and
// both elements of the pairs are also even
count_even *= count_even;
// Stores count of pairs whose sum is even and
// both elements of the pairs are odd
count_odd *= count_odd;
// Print total ordered pairs whose sum is even
document.write(count_even + count_odd);
}
// Driver Code
// Given L & R
let L = 1, R = 3;
// Function Call
countPairs(L, R);
// This code is contributed by avijitmondal1998
</script>
Producción:
5
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)