Nos dan una string que consta de dígitos, podemos agrupar estos dígitos en subgrupos (pero manteniendo su orden original). La tarea es contar el número de agrupaciones de modo que para cada subgrupo, excepto el último, la suma de los dígitos de un subgrupo sea menor o igual que la suma de los dígitos del subgrupo inmediatamente a su derecha. .
Por ejemplo, una agrupación válida de dígitos del número 1119 es (1-11-9). La suma de los dígitos en el primer subgrupo es 1, el siguiente subgrupo es 2 y el último subgrupo es 9. La suma de cada subgrupo es menor o igual que su derecho inmediato.
Ejemplos:
Input : "1119"
Output: 7
Sub-groups: [1-119], [1-1-19], [1-11-9], [1-1-1-9],
[11-19] and [111-9].
Note : Here we have included [1119] in the group and
the sum of digits is 12 and this group has no
immediate right.
Input : "1234"
Output: 6
Sub-groups : [1234], [1-234], [12-34], [1-2-3-4],
[12-3-4] and [1-2-34]
Sea «longitud» la longitud del número de entrada. Una solución recursiva es considerar cada posición desde 0 longitud-1. Para cada posición, cuente recursivamente todos los subgrupos posibles después de ella. A continuación se muestra la implementación en C++ de la solución recursiva ingenua.
C++
// C++ program to count number of
// ways to group digits of a number
// such that sum of digits in every
// subgroup is less than or equal to
// its immediate right subgroup.
#include<bits/stdc++.h>
using namespace std;
// Function to find the subgroups
int countGroups(int position,
int previous_sum,
int length, char *num)
{
// Terminating Condition
if (position == length)
return 1;
int res = 0;
// sum of digits
int sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (int i = position; i < length; i++)
{
sum += (num[i] - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum,
length, num);
}
// Total number of subgroups
// till current position
return res;
}
// Driver Code
int main()
{
char num[] = "1119";
int len = strlen(num);
cout << countGroups(0, 0, len, num);
return 0;
}
Java
// Java program to count number
// of ways to group digits of
// a number such that sum of
// digits in every subgroup is
// less than or equal to its
// immediate right subgroup.
import java.io.*;
class GFG
{
// Function to find
// the subgroups
static int countGroups(int position,
int previous_sum,
int length,
String num)
{
// Terminating Condition
if (position == length)
return 1;
int res = 0;
// sum of digits
int sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (int i = position; i < length; i++)
{
sum += (num.charAt(i) - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum,
length, num);
}
// Total number of subgroups
// till current position
return res;
}
// Driver Code
public static void main (String[] args)
{
String num = "1119";
int len =num .length();
System.out.println(countGroups(0, 0,
len, num));
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to count # number of ways to group digits # of a number such that sum of # digits in every subgroup # is less than or equal to its immediate # right subgroup. # Function to find the subgroups def countGroups(position, previous_sum, length, num): # Terminating Condition if(position == length): return 1 res = 0 # sum of digits sum = 0 # Traverse all digits from # current position to rest # of the length of string for i in range(position, length): sum = sum + int(num[i]) # If forward_sum is greater # than the previous sum, # then call the method again if (sum >= previous_sum): # Note : We pass current # sum as previous sum res = res + countGroups(i + 1, sum, length, num) # Total number of subgroups # till the current position return res # Driver Code if __name__=='__main__': num = "1119" len = len(num) print(countGroups(0, 0, len, num)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to count number
// of ways to group digits of
// a number such that sum of
// digits in every subgroup is
// less than or equal to its
// immediate right subgroup.
using System;
class GFG
{
// Function to find
// the subgroups
static int countGroups(int position,
int previous_sum,
int length,
String num)
{
// Terminating Condition
if (position == length)
return 1;
int res = 0;
// sum of digits
int sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (int i = position; i < length; i++)
{
sum += (num[i] - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum,
length, num);
}
// Total number of subgroups
// till current position
return res;
}
// Driver Code
public static void Main ()
{
String num = "1119";
int len = num.Length;
Console.Write(countGroups(0, 0, len, num));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to count number of
// ways to group digits of a number
// such that sum of digits in every
// subgroup is less than or equal
// to its immediate right subgroup.
// Function to find the subgroups
function countGroups($position,
$previous_sum,
$length,$num)
{
// Terminating Condition
if ($position == $length)
return 1;
$res = 0;
// sum of digits
$sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for ($i = $position; $i < $length; $i++)
{
$sum += ($num[$i] - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if ($sum >= $previous_sum)
// Note : We pass current
// sum as previous sum
$res += countGroups($i + 1, $sum,
$length, $num);
}
// Total number of subgroups
// till current position
return $res;
}
// Driver Code
$num = "1119";
$len = strlen($num);
echo countGroups(0, 0, $len, $num);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to count number
// of ways to group digits of
// a number such that sum of
// digits in every subgroup is
// less than or equal to its
// immediate right subgroup.
// Function to find
// the subgroups
function countGroups(position,
previous_sum,
length, num)
{
// Terminating Condition
if (position == length)
return 1;
let res = 0;
// sum of digits
let sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (let i = position; i < length; i++)
{
sum += (num[i].charCodeAt() - '0'.charCodeAt());
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum, length, num);
}
// Total number of subgroups
// till current position
return res;
}
let num = "1119";
let len = num.length;
document.write(countGroups(0, 0, len, num));
</script>
Producción :
7
Si observamos más de cerca la solución recursiva anterior, notamos que puede haber subproblemas superpuestos. Por ejemplo, si el número de entrada es 12345, entonces para posición = 3 y suma_anterior = 3, recurrimos dos veces. De manera similar, para la posición 4 y anterior_sum = 7, recurrimos dos veces. Por lo tanto, la solución anterior se puede optimizar utilizando Programación Dinámica . A continuación se muestra una solución basada en programación dinámica para este problema.
- La suma máxima de dígitos puede ser 9*longitud donde ‘longitud’ es la longitud del número de entrada.
- Cree una array 2D int dp[MAX][9*MAX] donde MAX es la longitud máxima posible del número de entrada. Un valor dp[posición][anterior] almacenará el resultado de ‘posición’ y ‘previous_sum’.
- Si el subproblema actual ha sido evaluado, es decir; dp[posición][previous_sum] != -1, luego use este resultado, de lo contrario calcule recursivamente su valor.
- Si al incluir el dígito de la posición actual en la suma, es decir; sum = sum + num[posición]-‘0’, sum se vuelve mayor que igual a la suma anterior, luego incrementa el resultado y llama al problema para la siguiente posición en el num.
- Si position == length, entonces hemos atravesado el subgrupo actual con éxito y devolvemos 1;
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to count number of
// ways to group digits of a number
// such that sum of digits in every
// subgroup is less than or equal
// to its immediate right subgroup.
#include<bits/stdc++.h>
using namespace std;
// Maximum length of
// input number string
const int MAX = 40;
// A memoization table to store
// results of subproblems length
// of string is 40 and maximum
// sum will be 9 * 40 = 360.
int dp[MAX][9*MAX + 1];
// Function to find the count
// of splits with given condition
int countGroups(int position,
int previous_sum,
int length, char *num)
{
// Terminating Condition
if (position == length)
return 1;
// If already evaluated for
// a given sub problem then
// return the value
if (dp[position][previous_sum] != -1)
return dp[position][previous_sum];
// countGroups for current
// sub-group is 0
dp[position][previous_sum] = 0;
int res = 0;
// sum of digits
int sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (int i = position; i < length; i++)
{
sum += (num[i] - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum,
length, num);
}
dp[position][previous_sum] = res;
// total number of subgroups
// till current position
return res;
}
// Driver Code
int main()
{
char num[] = "1119";
int len = strlen(num);
// Initialize dp table
memset(dp, -1, sizeof(dp));
cout << countGroups(0, 0, len, num);
return 0;
}
Java
// Java program to count the number of
// ways to group digits of a number
// such that sum of digits in every
// subgroup is less than or equal
// to its immediate right subgroup.
class GFG
{
// Maximum length of
// input number string
static int MAX = 40;
// A memoization table to store
// results of subproblems length
// of string is 40 and maximum
// sum will be 9 * 40 = 360.
static int dp[][] = new int[MAX][9 * MAX + 1];
// Function to find the count
// of splits with given condition
static int countGroups(int position,
int previous_sum,
int length, char []num)
{
// Terminating Condition
if (position == length)
return 1;
// If already evaluated for
// a given sub problem then
// return the value
if (dp[position][previous_sum] != -1)
return dp[position][previous_sum];
// countGroups for current
// sub-group is 0
dp[position][previous_sum] = 0;
int res = 0;
// sum of digits
int sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (int i = position; i < length; i++)
{
sum += (num[i] - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum,
length, num);
}
dp[position][previous_sum] = res;
// total number of subgroups
// till current position
return res;
}
// Driver Code
public static void main(String[] args)
{
char num[] = "1119".toCharArray();
int len = num.length;
// Initialize dp table
for(int i = 0; i < dp.length; i++)
{
for(int j = 0;j < 9 * MAX + 1; j++){
dp[i][j] = -1;
}
}
System.out.println(countGroups(0, 0, len, num));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to count the number of
# ways to group digits of a number
# such that sum of digits in every
# subgroup is less than or equal
# to its immediate right subgroup.
# Maximum length of
# input number string
MAX = 40
# A memoization table to store
# results of subproblems length
# of string is 40 and maximum
# sum will be 9 * 40 = 360.
dp = [[ -1 for i in range(9 * MAX + 1)]
for i in range(MAX)]
# Function to find the count
# of splits with given condition
def countGroups(position, previous_sum,
length, num):
# Terminating Condition
if (position == length):
return 1
# If already evaluated for
# a given sub problem then
# return the value
if (dp[position][previous_sum] != -1):
return dp[position][previous_sum]
# countGroups for current
# sub-group is 0
dp[position][previous_sum] = 0
res = 0
# sum of digits
sum = 0
# Traverse all digits from
# current position to rest
# of the length of string
for i in range(position,length):
sum += (ord(num[i]) - ord('0'))
# If forward_sum is greater
# than the previous sum,
# then call the method again
if (sum >= previous_sum):
# Note : We pass current
# sum as previous sum
res += countGroups(i + 1, sum,
length, num)
dp[position][previous_sum] = res
# total number of subgroups
# till the current position
return res
# Driver Code
num = "1119"
len = len(num)
print(countGroups(0, 0, len, num))
# This code is contributed by Mohit Kumar
C#
// C# program to count number of
// ways to group digits of a number
// such that sum of digits in every
// subgroup is less than or equal
// to its immediate right subgroup.
using System;
class GFG
{
// Maximum length of
// input number string
static int MAX = 40;
// A memoization table to store
// results of subproblems length
// of string is 40 and maximum
// sum will be 9 * 40 = 360.
static int[,] dp = new int[MAX, 9 * MAX + 1];
// Function to find the count
// of splits with given condition
static int countGroups(int position,
int previous_sum,
int length, char[] num)
{
// Terminating Condition
if (position == length)
return 1;
// If already evaluated for
// a given sub problem then
// return the value
if (dp[position,previous_sum] != -1)
return dp[position,previous_sum];
// countGroups for current
// sub-group is 0
dp[position,previous_sum] = 0;
int res = 0;
// sum of digits
int sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (int i = position; i < length; i++)
{
sum += (num[i] - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum,
length, num);
}
dp[position,previous_sum] = res;
// total number of subgroups
// till current position
return res;
}
// Driver Code
static void Main()
{
char[] num = {'1', '1', '1', '9'};
int len = num.Length;
// Initialize dp table
for(int i = 0; i < MAX; i++)
for(int j = 0; j < 9 * MAX + 1; j++)
dp[i, j] = -1;
Console.Write(countGroups(0, 0, len, num));
}
}
// This code is contributed by DrRoot_
Javascript
<script>
// Javascript program to count the number of
// ways to group digits of a number
// such that sum of digits in every
// subgroup is less than or equal
// to its immediate right subgroup.
// Maximum length of
// input number string
let MAX = 40;
// A memoization table to store
// results of subproblems length
// of string is 40 and maximum
// sum will be 9 * 40 = 360.
let dp=new Array(MAX);
// Function to find the count
// of splits with given condition
function countGroups( position,previous_sum,length,num)
{
// Terminating Condition
if (position == length)
return 1;
// If already evaluated for
// a given sub problem then
// return the value
if (dp[position][previous_sum] != -1)
return dp[position][previous_sum];
// countGroups for current
// sub-group is 0
dp[position][previous_sum] = 0;
let res = 0;
// sum of digits
let sum = 0;
// Traverse all digits from
// current position to rest
// of the length of string
for (let i = position; i < length; i++)
{
sum += (num[i] - '0');
// If forward_sum is greater
// than the previous sum,
// then call the method again
if (sum >= previous_sum)
// Note : We pass current
// sum as previous sum
res += countGroups(i + 1, sum,
length, num);
}
dp[position][previous_sum] = res;
// total number of subgroups
// till current position
return res;
}
// Driver Code
let num = "1119".split("");
let len = num.length;
// Initialize dp table
for(let i = 0; i < dp.length; i++)
{
dp[i]=new Array(9 * MAX + 1)
for(let j = 0;j < 9 * MAX + 1; j++){
dp[i][j] = -1;
}
}
document.write(countGroups(0, 0, len, num));
// This code is contributed by unknown2108
</script>
Producción :
7
Este artículo es una contribución de Shashank Mishra (Gullu) . Este artículo está revisado por el equipo GeeksForGeeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA