Dado un entero positivo n. Cuente los diferentes números que se pueden generar usando los dígitos 1, 2, 3 y 4 de modo que la suma de los dígitos sea el número ‘n’. Aquí el dígito ‘4’ será tratado como ‘1’ . Por ejemplo,
32 = 3 + 2 = 5
1341 = 1 + 3 + 1 + 1 = 6
441 = 1 + 1 + 1 = 3
Nota : Conteste el valor en mod = 10 9 +7
Input: 2 Output: 5 Explanation There are only '5' numbers that can be made: 11 = 1 + 1 = 2 14 = 1 + 1 = 2 41 = 1 + 1 = 2 44 = 1 + 1 = 2 2 = 2 Input: 3 Output: 13 Explanation There are only '13' numbers that can be made i.e., 111, 114, 141, 144, 411, 414, 441, 444, 12, 21, 42, 24, 3.
El enfoque es utilizar la programación dinámica. El problema es el mismo que el cambio de moneda y Formas de escribir n como suma de dos o más problemas de números enteros positivos. La única diferencia es que, en lugar de iterar hasta ‘n’, iterar solo de 1 a 3, ya que según la pregunta, solo se permiten 1, 2, 3 y 4 dígitos. Pero dado que ‘4’ se puede reemplazar con ‘1’, repita 1, 2 y 3 y duplique la cuenta de ‘1’ para compensar el dígito ‘4’.
C++
// C++ program to count ways to write // 'n' as sum of digits #include<iostream> using namespace std; // Function to count 'num' as sum of // digits(1, 2, 3, 4) int countWays(int num) { // Initialize dp[] array int dp[num+1]; const int MOD = 1e9 + 7; // Base case dp[1] = 2; for(int i = 2; i <= num; ++i) { // Initialize the current dp[] // array as '0' dp[i] = 0; for(int j = 1; j <= 3; ++j) { /* if i == j then there is only one way to write with element itself 'i' */ if(i - j == 0) dp[i] += 1; /* If j == 1, then there exist two ways, one from '1' and other from '4' */ else if (j == 1) dp[i] += dp[i-j] * 2; /* if i - j is positive then pick the element from 'i-j' element of dp[] array */ else if(i - j > 0) dp[i] += dp[i-j]; // Check for modulus if(dp[i] >= MOD) dp[i] %= MOD; } } // return the final answer return dp[num]; } // Driver code int main() { int n = 3; cout << countWays(n); return 0; }
Java
// Java program to count ways to // write 'n' as sum of digits import java.io.*; public class GFG { // Function to count 'num' as // sum of digits(1, 2, 3, 4) static int countWays(int num) { // Initialize dp[] array int []dp= new int[num + 1]; int MOD = (int)1E9 + 7; // Base case dp[1] = 2; for(int i = 2; i <= num; ++i) { // Initialize the current // dp[] array as '0' dp[i] = 0; for(int j = 1; j <= 3; ++j) { // if i == j then there is // only one way to write with // element itself 'i' if(i - j == 0) dp[i] += 1; // If j == 1, then there exist // two ways, one from '1' and // other from '4' else if (j == 1) dp[i] += dp[i - j] * 2; // if i - j is positive then // pick the element from 'i-j' // element of dp[] array else if(i - j > 0) dp[i] += dp[i - j]; // Check for modulus if(dp[i] >= MOD) dp[i] %= MOD; } } // return the final answer return dp[num]; } // Driver code static public void main (String[] args) { int n = 3; System.out.println(countWays(n)); } } // This code is contributed by vt_m
Python3
# Python3 program to count ways to write # 'n' as sum of digits # Function to count 'num' as sum of # digits(1, 2, 3, 4) def countWays(num): # Initialize dp[] array dp = [0] * (num + 1); MOD = 100000000 + 7; # Base case dp[1] = 2; for i in range(2, num + 1): # Initialize the current dp[] # array as '0' dp[i] = 0; for j in range(1, 4): # if i == j then there is only # one way to write with element # itself 'i' if(i - j == 0): dp[i] += 1; # If j == 1, then there exist # two ways, one from '1' and # other from '4' elif (j == 1): dp[i] += dp[i - j] * 2; # if i - j is positive then # pick the element from 'i-j' # element of dp[] array elif(i - j > 0): dp[i] += dp[i - j]; # Check for modulus if(dp[i] >= MOD): dp[i] %= MOD; # return the final answer return dp[num]; # Driver code n = 3; print(countWays(n)); # This code is contributed by mits
C#
// C# program to count ways to // write 'n' as sum of digits using System; public class GFG { // Function to count 'num' as // sum of digits(1, 2, 3, 4) static int countWays(int num) { // Initialize dp[] array int []dp= new int[num + 1]; int MOD = (int)1E9 + 7; // Base case dp[1] = 2; for(int i = 2; i <= num; ++i) { // Initialize the current // dp[] array as '0' dp[i] = 0; for(int j = 1; j <= 3; ++j) { // if i == j then there is // only one way to write with // element itself 'i' if(i - j == 0) dp[i] += 1; // If j == 1, then there exist // two ways, one from '1' and // other from '4' else if (j == 1) dp[i] += dp[i - j] * 2; // if i - j is positive then // pick the element from 'i-j' // element of dp[] array else if(i - j > 0) dp[i] += dp[i - j]; // Check for modulus if(dp[i] >= MOD) dp[i] %= MOD; } } // return the final answer return dp[num]; } // Driver code static public void Main (String []args) { int n = 3; Console.WriteLine(countWays(n)); } } // This code is contributed by vt_m
PHP
<?php // PHP program to count ways to write // 'n' as sum of digits // Function to count 'num' as sum of // digits(1, 2, 3, 4) function countWays($num) { // Initialize dp[] array $dp[$num + 1] = array(); $MOD = 100000000 + 7; // Base case $dp[1] = 2; for($i = 2; $i <= $num; ++$i) { // Initialize the current dp[] // array as '0' $dp[$i] = 0; for($j = 1; $j <= 3; ++$j) { /* if i == j then there is only one way to write with element itself 'i' */ if($i - $j == 0) $dp[$i] += 1; /* If j == 1, then there exist two ways, one from '1' and other from '4' */ else if ($j == 1) $dp[$i] += $dp[$i - $j] * 2; /* if i - j is positive then pick the element from 'i-j' element of dp[] array */ else if($i - $j > 0) $dp[$i] += $dp[$i - $j]; // Check for modulus if($dp[$i] >= $MOD) $dp[$i] %= $MOD; } } // return the final answer return $dp[$num]; } // Driver code $n = 3; echo countWays($n); // This code is contributed by jit_t ?>
Javascript
<script> // JavaScript program to count ways to // write 'n' as sum of digits // Function to count 'num' as // sum of digits(1, 2, 3, 4) function countWays(num) { // Initialize dp[] array let dp = []; let MOD = 1E9 + 7; // Base case dp[1] = 2; for(let i = 2; i <= num; ++i) { // Initialize the current // dp[] array as '0' dp[i] = 0; for(let j = 1; j <= 3; ++j) { // If i == j then there is // only one way to write with // element itself 'i' if (i - j == 0) dp[i] += 1; // If j == 1, then there exist // two ways, one from '1' and // other from '4' else if (j == 1) dp[i] += dp[i - j] * 2; // If i - j is positive then // pick the element from 'i-j' // element of dp[] array else if (i - j > 0) dp[i] += dp[i - j]; // Check for modulus if (dp[i] >= MOD) dp[i] %= MOD; } } // Return the final answer return dp[num]; } // Driver Code let n = 3; document.write(countWays(n)); // This code is contributed by susmitakundugoaldanga </script>
Producción
13
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Nota: Preguntado en ronda de codificación Directi (2014 y 2017)
Publicación traducida automáticamente
Artículo escrito por Shubham Bansal 13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA