Consultas de rango para encontrar la suma de todos los números de paridad pares

Posted on by Rudeus Greyrat

Dadas Q consultas donde cada consulta consta de dos números L y R que denota un rango [L, R] . La tarea es encontrar la suma de todos los números de paridad pares que se encuentran en el rango dado [L, R].
 

La paridad de un número se refiere a si contiene un número par o impar de 1 bit. El número tiene paridad par si contiene un número par de 1 bits. 
 

Ejemplos: 
 

Entrada: Q = [ [1, 10], [121, 211] ] 
Salida: 
33 
7493 
Explicación: 
binario(1) = 01, paridad = 1 
binario(2) = 10, paridad = 1 
binario(3) = 11, paridad = 2 
binario(4) = 100, paridad = 1 
binario(5) = 101, paridad = 2 
binario(6) = 110, paridad = 2 
binario(7) = 111, paridad = 3 
binario(8) = 1000, paridad = 1 
binario(9) = 1001, paridad = 2 
binario(10) = 1010, paridad = 2 
Del 1 al 10, 3, 5, 6, 9 y 10 son los números de paridad par. Por lo tanto la suma es 33. 
De 121 a 211 la suma de todos los números de paridad par es 7493.
Entrada: Q = [[ 10, 10 ], [ 258, 785 ], [45, 245], [ 1, 1000]] 
Salida: 
10 
137676 
14595 
250750 
 

Enfoque: 
La idea es utilizar una array de suma de prefijos . La suma de todos los números de paridad par hasta ese índice en particular se calcula previamente y se almacena en una array pref[] para que cada consulta se pueda responder en tiempo O(1) . 
 

  1. Inicialice la array de prefijos pref[] .
  2. Iterar de 1 a N y verificar si el número tiene paridad par o no: 
    • Si el número es Número de paridad par entonces, el índice actual de pref[] almacenará la suma de Números de paridad par encontrados hasta el momento. 
       
    • De lo contrario, el índice actual de pref[] es el mismo que el valor en el índice anterior de pref[] .
  3. Para consultas Q , la suma de todos los números de paridad par para el rango [L, R] se puede calcular de la siguiente manera: 
     
sum = pref[R] - pref[L - 1]
  1.  

A continuación se muestra la implementación del enfoque anterior. 
 

C++

// C++ program to find the sum
// of all Even Parity numbers
// in the given range
 
#include <bits/stdc++.h>
using namespace std;
 
// pref[] array to precompute
// the sum of all Even
// Parity Numbers
int pref[100001] = { 0 };
 
// Function that returns true
// if count of set bits in
// x is even
int isEvenParity(int num)
{
    // Parity will store the
    // count of set bits
    int parity = 0;
    int x = num;
    while (x != 0) {
        if (x & 1)
            parity++;
        x = x >> 1;
    }
 
    if (parity % 2 == 0)
        return num;
    else
        return 0;
}
 
// Function to precompute the
// sum of all even parity
// numbers upto 100000
void preCompute()
{
    for (int i = 1; i < 100001; i++) {
 
        // isEvenParity()
        // return the number i
        // if i has even parity
        // else return 0
        pref[i] = pref[i - 1]
                  + isEvenParity(i);
    }
}
 
// Function to print sum
// for each query
void printSum(int L, int R)
{
    cout << (pref[R] - pref[L - 1])
         << endl;
}
 
// Function to print sum of all
// even parity numbers between
// [L, R]
void printSum(int arr[2][2], int Q)
{
 
    // Function that pre computes
    // the sum of all even parity
    // numbers
    preCompute();
 
    // Iterate over all Queries
    // to print sum
    for (int i = 0; i < Q; i++) {
        printSum(arr[i][0],
                 arr[i][1]);
    }
}
// Driver code
int main()
{
    // Queries
    int N = 2;
    int Q[2][2] = { { 1, 10 },
                    { 121, 211 } };
 
    // Function that print
    // the sum of all even parity
    // numbers in Range [L, R]
    printSum(Q, N);
 
    return 0;
}

Java

// Java program to find the sum
// of all Even Parity numbers
// in the given range
import java.io.*;
import java.util.*;
 
class GFG {
     
// pref[] array to precompute
// the sum of all Even
// Parity Numbers
static int[] pref = new int[100001];
 
// Function that returns true
// if count of set bits in
// x is even
static int isEvenParity(int num)
{
     
    // Parity will store the
    // count of set bits
    int parity = 0;
    int x = num;
     
    while (x != 0)
    {
        if ((x & 1) == 1)
            parity++;
             
        x = x >> 1;
    }
     
    if (parity % 2 == 0)
        return num;
    else
        return 0;
}
 
// Function to precompute the
// sum of all even parity
// numbers upto 100000
static void preCompute()
{
    for(int i = 1; i < 100001; i++)
    {
 
       // isEvenParity()
       // return the number i
       // if i has even parity
       // else return 0
       pref[i] = pref[i - 1] + isEvenParity(i);
    }
}
 
// Function to print sum
// for each query
static void printSum(int L, int R)
{
    System.out.println(pref[R] - pref[L - 1]);
}
 
// Function to print sum of all
// even parity numbers between
// [L, R]
static void printSum(int arr[][], int Q)
{
     
    // Function that pre computes
    // the sum of all even parity
    // numbers
    preCompute();
 
    // Iterate over all Queries
    // to print sum
    for(int i = 0; i < Q; i++)
    {
       printSum(arr[i][0], arr[i][1]);
    }
}
     
// Driver code
public static void main(String[] args)
{
     
    // Queries
    int N = 2;
    int[][] Q = { { 1, 10 },
                  { 121, 211 } };
 
    // Function that print
    // the sum of all even parity
    // numbers in Range [L, R]
    printSum(Q, N);
}
}
 
// This code is contributed by coder001

C#

// C# program to find the sum
// of all Even Parity numbers
// in the given range
using System;
 
class GFG {
     
// pref[] array to precompute
// the sum of all Even
// Parity Numbers
static int[] pref = new int[100001];
 
// Function that returns true
// if count of set bits in
// x is even
static int isEvenParity(int num)
{
     
    // Parity will store the
    // count of set bits
    int parity = 0;
    int x = num;
     
    while (x != 0)
    {
        if ((x & 1) == 1)
            parity++;
             
        x = x >> 1;
    }
     
    if (parity % 2 == 0)
        return num;
    else
        return 0;
}
 
// Function to precompute the
// sum of all even parity
// numbers upto 100000
static void preCompute()
{
    for(int i = 1; i < 100001; i++)
    {
         
       // isEvenParity()
       // return the number i
       // if i has even parity
       // else return 0
       pref[i] = pref[i - 1] + isEvenParity(i);
    }
}
 
// Function to print sum
// for each query
static void printSum(int L, int R)
{
    Console.WriteLine(pref[R] - pref[L - 1]);
}
 
// Function to print sum of all
// even parity numbers between
// [L, R]
static void printSum(int[,] arr, int Q)
{
     
    // Function that pre computes
    // the sum of all even parity
    // numbers
    preCompute();
 
    // Iterate over all Queries
    // to print sum
    for(int i = 0; i < Q; i++)
    {
       printSum(arr[i, 0], arr[i, 1]);
    }
}
     
// Driver code
public static void Main()
{
     
    // Queries
    int N = 2;
    int[,] Q = { { 1, 10 },
                 { 121, 211 } };
 
    // Function that print
    // the sum of all even parity
    // numbers in Range [L, R]
    printSum(Q, N);
}
}
 
// This code is contributed by AbhiThakur

Javascript

<script>
// Javascript program to find the sum
// of all Even Parity numbers
// in the given range
 
// pref[] array to precompute
// the sum of all Even
// Parity Numbers
let pref = new Array(100001).fill(0);
 
// Function that returns true
// if count of set bits in
// x is even
function isEvenParity(num)
{
 
    // Parity will store the
    // count of set bits
    let parity = 0;
    let x = num;
    while (x != 0) {
        if (x & 1 == 1)
            parity++;
        x = x >> 1;
    }
 
    if (parity % 2 == 0)
        return num;
    else
        return 0;
}
 
// Function to precompute the
// sum of all even parity
// numbers upto 100000
function preCompute() {
    for (let i = 1; i < 100001; i++) {
 
        // isEvenParity()
        // return the number i
        // if i has even parity
        // else return 0
        pref[i] = pref[i - 1] + isEvenParity(i);
    }
}
 
// Function to print sum
// for each query
function printSum2(L, R) {
    document.write(pref[R] - pref[L - 1] + "<br>");
}
 
// Function to print sum of all
// even parity numbers between
// [L, R]
function printSum(arr, Q) {
 
    // Function that pre computes
    // the sum of all even parity
    // numbers
    preCompute();
 
    // Iterate over all Queries
    // to print sum
    for (let i = 0; i < Q; i++) {
        printSum2(arr[i][0], arr[i][1]);
    }
}
 
// Driver code
 
// Queries
let N = 2;
let Q = [[1, 10],
[121, 211]];
 
// Function that print
// the sum of all even parity
// numbers in Range [L, R]
printSum(Q, N);
 
// This code is contributed by _saurabh_jaiswal.
</script>
Producción: 

33
7493

 

Complejidad de tiempo: O(N) , donde N es el elemento máximo en la consulta.
 

Publicación traducida automáticamente

Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *