Dado un número entero n y un rango [l, r] , la tarea es encontrar el recuento de subconjuntos totales de tamaño n con números enteros del rango dado tal que la suma total de sus elementos sea divisible por 3 .
Ejemplos:
Entrada: n = 2, l = 1, r = 5
Salida: 9
Los posibles subconjuntos son {1, 2}, {2, 1}, {3, 3}, {5, 1}, {1, 5} , {4, 2}, {2, 4}, {5, 4} y {4, 5}
Entrada: n = 3, l = 9, r = 9
Salida: 1
{9, 9, 9} es el único posible subconjunto
Enfoque: Dado que necesitamos que la suma de los elementos del subconjunto sea divisible por 3, entonces, en lugar de preocuparnos por los números, contaremos los números de modo que den resto 0 , 1 y 2 al dividir con 3 por separado por el fórmula dada a continuación:
Por ejemplo, un elemento k tal que k % 3 = 2 se puede encontrar como k = 3 * x + 2 para algún número entero x .
Entonces tenemos l ≤ (3 * x) + 2 ≤ r
l – 2 ≤ (3 * x) ≤ r – 2
techo ((l – 2) / 3) ≤ x ≤ piso ((r – 2) / 3)
Ahora, mediante la programación dinámica dp[i][j] podemos verificar cuántos elementos darán una suma que sea divisible por 3 . Aquí dp[i][j] representa la suma de los primeros i elementos que dan el resto j al dividir por 3 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define MOD 1000000007
#define ll long long int
using namespace std;
// Function to return the total number of
// required sub-sets
int totalSubSets(ll n, ll l, ll r)
{
// Variable to store total elements
// which on dividing by 3 give
// remainder 0, 1 and 2 respectively
ll zero = floor((double)r / 3)
- ceil((double)l / 3) + 1;
ll one = floor((double)(r - 1) / 3)
- ceil((double)(l - 1) / 3) + 1;
ll two = floor((double)(r - 2) / 3)
- ceil((double)(l - 2) / 3) + 1;
// Create a dp table
ll dp[n][3];
memset(dp, 0, sizeof(dp));
dp[0][0] = zero;
dp[0][1] = one;
dp[0][2] = two;
// Process for n states and store
// the sum (mod 3) for 0, 1 and 2
for (ll i = 1; i < n; ++i) {
// Use of MOD for large numbers
dp[i][0] = ((dp[i - 1][0] * zero)
+ (dp[i - 1][1] * two)
+ (dp[i - 1][2] * one))
% MOD;
dp[i][1] = ((dp[i - 1][0] * one)
+ (dp[i - 1][1] * zero)
+ (dp[i - 1][2] * two))
% MOD;
dp[i][2] = ((dp[i - 1][0] * two)
+ (dp[i - 1][1] * one)
+ (dp[i - 1][2] * zero))
% MOD;
}
// Final answer store at dp[n - 1][0]
return dp[n - 1][0];
}
// Driver Program
int main()
{
ll n = 5;
ll l = 10;
ll r = 100;
cout << totalSubSets(n, l, r);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MOD = 1000000007;
// Function to return the total number of
// required sub-sets
static int totalSubSets(int n, int l, int r)
{
// Variable to store total elements
// which on dividing by 3 give
// remainder 0, 1 and 2 respectively
int zero = (int)Math.floor((double)r / 3)
- (int)Math.ceil((double)l / 3) + 1;
int one = (int)Math.floor((double)(r - 1) / 3)
- (int)Math.ceil((double)(l - 1) / 3) + 1;
int two = (int)Math.floor((double)(r - 2) / 3)
- (int)Math.ceil((double)(l - 2) / 3) + 1;
// Create a dp table
int [][] dp = new int[n][3];
dp[0][0] = zero;
dp[0][1] = one;
dp[0][2] = two;
// Process for n states and store
// the sum (mod 3) for 0, 1 and 2
for (int i = 1; i < n; ++i)
{
// Use of MOD for large numbers
dp[i][0] = ((dp[i - 1][0] * zero)
+ (dp[i - 1][1] * two)
+ (dp[i - 1][2] * one))
% MOD;
dp[i][1] = ((dp[i - 1][0] * one)
+ (dp[i - 1][1] * zero)
+ (dp[i - 1][2] * two))
% MOD;
dp[i][2] = ((dp[i - 1][0] * two)
+ (dp[i - 1][1] * one)
+ (dp[i - 1][2] * zero))
% MOD;
}
// Final answer store at dp[n - 1][0]
return dp[n - 1][0];
}
// Driver Program
public static void main(String []args)
{
int n = 5;
int l = 10;
int r = 100;
System.out.println(totalSubSets(n, l, r));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the approach import math # Function to return the total # number of required sub-sets def totalSubSets(n, l, r): MOD = 1000000007 ; # Variable to store total elements # which on dividing by 3 give # remainder 0, 1 and 2 respectively zero = (math.floor(r / 3) - math.ceil(l / 3) + 1); one = (math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1); two = (math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1); # Create a dp table dp = [[0 for x in range(3)] for y in range(n)] dp[0][0] = zero; dp[0][1] = one; dp[0][2] = two; # Process for n states and store # the sum (mod 3) for 0, 1 and 2 for i in range(1, n): # Use of MOD for large numbers dp[i][0] = ((dp[i - 1][0] * zero) + (dp[i - 1][1] * two) + (dp[i - 1][2] * one)) % MOD; dp[i][1] = ((dp[i - 1][0] * one) + (dp[i - 1][1] * zero) + (dp[i - 1][2] * two)) % MOD; dp[i][2] = ((dp[i - 1][0] * two)+ (dp[i - 1][1] * one) + (dp[i - 1][2] * zero)) % MOD; # Final answer store at dp[n - 1][0] return dp[n - 1][0]; # Driver Code n = 5; l = 10; r = 100; print(totalSubSets(n, l, r)); # This code is contributed # by chandan_jnu
C#
// C# implementation of the approach
using System;
class GFG
{
static int MOD = 1000000007;
// Function to return the total number of
// required sub-sets
static int totalSubSets(int n, int l, int r)
{
// Variable to store total elements
// which on dividing by 3 give
// remainder 0, 1 and 2 respectively
int zero = (int)Math.Floor((double)r / 3)
- (int)Math.Ceiling((double)l / 3) + 1;
int one = (int)Math.Floor((double)(r - 1) / 3)
- (int)Math.Ceiling((double)(l - 1) / 3) + 1;
int two = (int)Math.Floor((double)(r - 2) / 3)
- (int)Math.Ceiling((double)(l - 2) / 3) + 1;
// Create a dp table
int [, ] dp = new int[n, 3];
dp[0,0] = zero;
dp[0,1] = one;
dp[0,2] = two;
// Process for n states and store
// the sum (mod 3) for 0, 1 and 2
for (int i = 1; i < n; ++i)
{
// Use of MOD for large numbers
dp[i,0] = ((dp[i - 1, 0] * zero)
+ (dp[i - 1, 1] * two)
+ (dp[i - 1, 2] * one))
% MOD;
dp[i,1] = ((dp[i - 1, 0] * one)
+ (dp[i - 1, 1] * zero)
+ (dp[i - 1, 2] * two))
% MOD;
dp[i,2] = ((dp[i - 1, 0] * two)
+ (dp[i - 1, 1] * one)
+ (dp[i - 1, 2] * zero))
% MOD;
}
// Final answer store at dp[n - 1,0]
return dp[n - 1, 0];
}
// Driver Program
public static void Main()
{
int n = 5;
int l = 10;
int r = 100;
Console.WriteLine(totalSubSets(n, l, r));
}
}
// This code is contributed by ihritik
PHP
<?php
# Php implementation of the approach
# Function to return the total number of
# required sub-sets
function totalSubSets($n, $l, $r)
{
$MOD = 1000000007 ;
// Variable to store total elements
// which on dividing by 3 give
// remainder 0, 1 and 2 respectively
$zero = floor($r / 3)
- ceil($l / 3) + 1;
$one = floor(($r - 1) / 3)
- ceil(($l - 1) / 3) + 1;
$two = floor(($r - 2) / 3)
- ceil(($l - 2) / 3) + 1;
// Create a dp table
$dp = array() ;
for($i = 0; $i < $n; $i++)
for($j = 0; $j < 3; $j++)
$dp[$i][$j] = 0 ;
$dp[0][0] = $zero;
$dp[0][1] = $one;
$dp[0][2] = $two;
// Process for n states and store
// the sum (mod 3) for 0, 1 and 2
for ($i = 1; $i < $n; ++$i)
{
// Use of MOD for large numbers
$dp[$i][0] = (($dp[$i - 1][0] * $zero)
+ ($dp[$i - 1][1] * $two)
+ ($dp[$i - 1][2] * $one))
% $MOD;
$dp[$i][1] = (($dp[$i - 1][0] * $one)
+ ($dp[$i - 1][1] * $zero)
+ ($dp[$i - 1][2] * $two))
% $MOD;
$dp[$i][2] = (($dp[$i - 1][0] * $two)
+ ($dp[$i - 1][1] * $one)
+ ($dp[$i - 1][2] * $zero))
% $MOD;
}
// Final answer store at dp[n - 1][0]
return $dp[$n - 1][0];
}
// Driver Program
$n = 5;
$l = 10;
$r = 100;
echo totalSubSets($n, $l, $r);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
let MOD = 1000000007;
// Function to return the total number of
// required sub-sets
function totalSubSets(n, l, r)
{
// Variable to store total elements
// which on dividing by 3 give
// remainder 0, 1 and 2 respectively
let zero = Math.floor(r / 3)
- Math.ceil(l / 3) + 1;
let one = Math.floor((r - 1) / 3)
- Math.ceil((l - 1) / 3) + 1;
let two = Math.floor((r - 2) / 3)
- Math.ceil((l - 2) / 3) + 1;
// Create a dp table
let dp = new Array(n);
for(let i = 0; i < n; i++)
{
dp[i] = new Array(3);
for(let j = 0; j < 3; j++)
{
dp[i][j] = 0;
}
}
dp[0][0] = zero;
dp[0][1] = one;
dp[0][2] = two;
// Process for n states and store
// the sum (mod 3) for 0, 1 and 2
for (let i = 1; i < n; ++i)
{
// Use of MOD for large numbers
dp[i][0] = ((dp[i - 1][0] * zero)
+ (dp[i - 1][1] * two)
+ (dp[i - 1][2] * one))
% MOD;
dp[i][1] = ((dp[i - 1][0] * one)
+ (dp[i - 1][1] * zero)
+ (dp[i - 1][2] * two))
% MOD;
dp[i][2] = ((dp[i - 1][0] * two)
+ (dp[i - 1][1] * one)
+ (dp[i - 1][2] * zero))
% MOD;
}
// Final answer store at dp[n - 1][0]
return dp[n - 1][0];
}
let n = 5;
let l = 10;
let r = 100;
document.write(totalSubSets(n, l, r));
</script>
Producción:
80107136
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por himanshu_rathore y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA