Dada una array arr[] de N enteros junto con los enteros M, L, R . Considere una variable S (inicialmente 0 ). La tarea es encontrar el recuento máximo de valores de S % M que se encuentra en el rango [L, R] después de realizar las siguientes operaciones para cada elemento en la array dada:
- Agregue arr[i] o arr[i] – 1 a S .
- Cambie S a S % M .
Ejemplos:
Entrada: arr[] = {17, 11, 10, 8, 15}, M = 22, L = 14, R = 16
Salida: 3
Explicación:
Inicialmente S = 0,
Paso 1: Elija, arr[0] – 1 = 16 y súmelo a S = 16 y S%M = 16. Por lo tanto, count = 1
Paso 2: elija, arr[1] = 11 y súmelo a S = 16 + 11 = 27 y S%M = 5. Por lo tanto, cuenta = 1
Paso 3: Elige, arr[2] = 10 y súmalo a S = 16 + 10 +11 = 37 y S%M = 15. Por lo tanto, cuenta = 2
Paso 4: Elige, arr[3] = 8 y súmalo a S = 16 + 10 + 11 + 8 = 45 y S%M = 1. Por lo tanto, cuenta = 2
Paso 5: Elige, arr[4] = 15 y súmalo a S = 16 + 10 + 11 + 8 + 15 = 60 y S%M = 16. Por lo tanto, cuenta = 3.
Por lo tanto, la cuenta máxima es 3.Entrada: arr[] = {23, 1}, M = 24, L = 21, R = 23
Salida: 2
Enfoque ingenuo: el enfoque más simple es atravesar la array dada arr[] y agregar arr[i] o arr[i – 1] a la S dada y verificar si S%M se encuentra en el rango [L, R] o no. Dado que hay dos posibilidades para elegir los números dados. Por lo tanto, utilice la recursividad para obtener recursivamente el recuento máximo de valores de S%M que se encuentra en el rango [L, R] .
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar la programación dinámica para almacenar los subproblemas superpuestos y luego encontrar el recuento máximo de S%M que se encuentra en el rango [L, R] . Siga los pasos a continuación para resolver el problema:
- Inicialice un dp unordered_map para almacenar los valores de los estados que tienen subproblemas superpuestos.
- Inicialice la suma para que sea 0 y luego agregue recursivamente el valor arr[i] o arr[i] – 1 a la suma S .
- En cada paso, verifique si el S%M se encuentra en el rango [L, R] o no. Si se encuentra en el rango, cuente ese valor y actualice este estado actual en el mapa anterior dp como 1. De lo contrario, actualice como 0 .
- Después de buscar todas las combinaciones posibles, devuelve el recuento de valores de S%M que se encuentra en el rango [L, R] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Lookup table
map<pair<int, int>, int> dp;
// Function to count the value of S
// after adding arr[i] or arr[i - 1]
// to the sum S at each time
int countMagicNumbers(int idx, int sum,
int a[], int n,
int m, int l, int r)
{
// Base Case
if (idx == n) {
// Store the mod value
int temp = sum % m;
// If the mod value lies in
// the range then return 1
if (temp == l || temp == r
|| (temp > l && temp < r))
return dp[{ idx, sum }] = 1;
// Else return 0
else
return dp[{ idx, sum }] = 0;
}
// Store the current state
pair<int, int> curr
= make_pair(idx, sum);
// If already computed, return the
// computed value
if (dp.find(curr) != dp.end())
return dp[curr];
// Recursively adding the elements
// to the sum adding ai value
int ls = countMagicNumbers(idx + 1,
sum + a[idx],
a, n,
m, l, r);
// Adding arr[i] - 1 value
int rs = countMagicNumbers(idx + 1,
sum + (a[idx] - 1),
a, n, m, l, r);
// Return the maximum count to
// check for root value as well
int temp1 = max(ls, rs);
int temp = sum % m;
// Avoid counting idx = 0 as possible
// solution we are using idx != 0
if ((temp == l || temp == r
|| (temp > l && temp < r))
&& idx != 0) {
temp1 += 1;
}
// Return the value of current state
return dp[{ idx, sum }] = temp1;
}
// Driver Code
int main()
{
int N = 5, M = 22, L = 14, R = 16;
int arr[] = { 17, 11, 10, 8, 15 };
cout << countMagicNumbers(0, 0, arr,
N, M, L, R);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.awt.Point;
public class Main
{
// Lookup table
static HashMap<Point, Integer> dp = new HashMap<Point, Integer>();
// Function to count the value of S
// after adding arr[i] or arr[i - 1]
// to the sum S at each time
static int countMagicNumbers(int idx, int sum, int[] a,
int n, int m, int l, int r)
{
// Base Case
if (idx == n) {
// Store the mod value
int Temp = sum % m;
// If the mod value lies in
// the range then return 1
if (Temp == l || Temp == r || (Temp > l && Temp < r))
{
dp.put(new Point(idx, sum), 1);
return dp.get(new Point(idx, sum));
}
// Else return 0
else
{
dp.put(new Point(idx, sum), 0);
return dp.get(new Point(idx, sum));
}
}
// Store the current state
Point curr = new Point(idx, sum);
// If already computed, return the
// computed value
if (dp.containsKey(curr))
return dp.get(curr);
// Recursively adding the elements
// to the sum adding ai value
int ls = countMagicNumbers(idx + 1,
sum + a[idx],
a, n,
m, l, r);
// Adding arr[i] - 1 value
int rs = countMagicNumbers(idx + 1,
sum + (a[idx] - 1),
a, n, m, l, r);
// Return the maximum count to
// check for root value as well
int temp1 = Math.max(ls, rs);
int temp = sum % m;
// Avoid counting idx = 0 as possible
// solution we are using idx != 0
if ((temp == l || temp == r
|| (temp > l && temp < r))
&& idx != 0) {
temp1 += 1;
}
// Return the value of current state
dp.put(new Point(idx, sum), temp1);
return dp.get(new Point(idx, sum));
}
public static void main(String[] args) {
int N = 5, M = 22, L = 14, R = 16;
int[] arr = { 17, 11, 10, 8, 15 };
System.out.print(countMagicNumbers(0, 0, arr, N, M, L, R));
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 program for the above approach
# Lookup table
dp = {}
# Function to count the value of S
# after adding arr[i] or arr[i - 1]
# to the sum S at each time
def countMagicNumbers(idx, sum, a, n, m, l, r):
# Base Case
if (idx == n):
# Store the mod value
temp = sum % m
# If the mod value lies in
# the range then return 1
if (temp == l or temp == r or
(temp > l and temp < r)):
dp[(idx, sum)] = 1
return dp[(idx, sum)]
# Else return 0
else:
dp[(idx, sum)] = 0
return dp[(idx, sum)]
# Store the current state
curr = (idx, sum)
# If already computed, return the
# computed value
if (curr in dp):
return dp[curr]
# Recursively adding the elements
# to the sum adding ai value
ls = countMagicNumbers(idx + 1,
sum + a[idx],
a, n, m, l, r)
# Adding arr[i] - 1 value
rs = countMagicNumbers(idx + 1,
sum + (a[idx] - 1),
a, n, m, l, r)
# Return the maximum count to
# check for root value as well
temp1 = max(ls, rs)
temp = sum % m
# Avoid counting idx = 0 as possible
# solution we are using idx != 0
if ((temp == l or temp == r or
(temp > l and temp < r)) and
idx != 0):
temp1 += 1
# Return the value of current state
dp[(idx, sum)] = temp1
return dp[(idx, sum)]
# Driver Code
if __name__ == '__main__':
N = 5
M = 22
L = 14
R = 16
arr = [ 17, 11, 10, 8, 15 ]
print(countMagicNumbers(0, 0, arr, N, M, L, R))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Lookup table
static Dictionary<Tuple<int, int>, int> dp = new Dictionary<Tuple<int, int>, int>();
// Function to count the value of S
// after adding arr[i] or arr[i - 1]
// to the sum S at each time
static int countMagicNumbers(int idx, int sum, int[] a, int n, int m, int l, int r)
{
// Base Case
if (idx == n) {
// Store the mod value
int Temp = sum % m;
// If the mod value lies in
// the range then return 1
if (Temp == l || Temp == r
|| (Temp > l && Temp < r))
return dp[new Tuple<int,int>(idx, sum)] = 1;
// Else return 0
else
return dp[new Tuple<int,int>(idx, sum)] = 0;
}
// Store the current state
Tuple<int,int> curr
= new Tuple<int,int>(idx, sum);
// If already computed, return the
// computed value
if (dp.ContainsKey(curr))
return dp[curr];
// Recursively adding the elements
// to the sum adding ai value
int ls = countMagicNumbers(idx + 1,
sum + a[idx],
a, n,
m, l, r);
// Adding arr[i] - 1 value
int rs = countMagicNumbers(idx + 1,
sum + (a[idx] - 1),
a, n, m, l, r);
// Return the maximum count to
// check for root value as well
int temp1 = Math.Max(ls, rs);
int temp = sum % m;
// Avoid counting idx = 0 as possible
// solution we are using idx != 0
if ((temp == l || temp == r
|| (temp > l && temp < r))
&& idx != 0) {
temp1 += 1;
}
// Return the value of current state
return dp[new Tuple<int,int>(idx, sum)] = temp1;
}
static void Main() {
int N = 5, M = 22, L = 14, R = 16;
int[] arr = { 17, 11, 10, 8, 15 };
Console.Write(countMagicNumbers(0, 0, arr, N, M, L, R));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program for the above approach
// Lookup table
let dp = new Map();
// Function to count the value of S
// after adding arr[i] or arr[i - 1]
// to the sum S at each time
function countMagicNumbers(idx, sum, a, n, m, l, r)
{
// Base Case
if (idx == n) {
// Store the mod value
let temp = sum % m;
// If the mod value lies in
// the range then return 1
if (temp == l || temp == r
|| (temp > l && temp < r))
return dp[[ idx, sum ]] = 1;
// Else return 0
else
return dp[[ idx, sum ]] = 0;
}
// Store the current state
let curr = [idx, sum];
// If already computed, return the
// computed value
if (dp.has(curr))
return dp[curr];
// Recursively adding the elements
// to the sum adding ai value
let ls = countMagicNumbers(idx + 1,
sum + a[idx],
a, n,
m, l, r);
// Adding arr[i] - 1 value
let rs = countMagicNumbers(idx + 1,
sum + (a[idx] - 1),
a, n, m, l, r);
// Return the maximum count to
// check for root value as well
let temp1 = Math.max(ls, rs);
let temp = sum % m;
// Avoid counting idx = 0 as possible
// solution we are using idx != 0
if ((temp == l || temp == r
|| (temp > l && temp < r))
&& idx != 0) {
temp1 += 1;
}
// Return the value of current state
dp[[ idx, sum ]] = temp1;
return dp[[ idx, sum ]];
}
let N = 5, M = 22, L = 14, R = 16;
let arr = [ 17, 11, 10, 8, 15 ];
document.write(countMagicNumbers(0, 0, arr, N, M, L, R));
// This code is contributed by mukesh07.
</script>
Producción:
3
Complejidad de tiempo: O(S*N), donde N es el tamaño de la array dada y S es la suma de todos los elementos de la array.
Complejidad espacial: O(S*N)