Soma de todos os números que podem ser formados com permutações de n dígitos
Experimente no GfG Practice 
#practiceLinkDiv { display: nenhum! Importante; }
Saída
#practiceLinkDiv { display: nenhum! Importante; } Dados n dígitos distintos (de 0 a 9), encontre a soma de todos os números de n dígitos que podem ser formados usando esses dígitos. Supõe-se que números formados com 0 à esquerda sejam permitidos.
Exemplo:
Input: 1 2 3 Output: 1332 Explanation Numbers Formed: 123 132 312 213 231 321 123 + 132 + 312 + 213 + 231 + 321 = 1332Recommended Practice Soma de permutações Experimente!
O total de números que podem ser formados usando n dígitos é o número total de permutações de n dígitos, ou seja, fatorial (n). Agora, como o número formado é um número de n dígitos, cada dígito aparecerá fatorial(n)/n vezes em cada posição, do dígito menos significativo ao dígito mais significativo. Portanto soma dos dígitos em uma posição = (soma de todos os dígitos) * (fatorial(n)/n).
Considering the example digits as 1 2 3 factorial(3)/3 = 2 Sum of digits at least significant digit = (1 + 2 + 3) * 2 = 12 Similarly sum of digits at tens hundreds place is 12. (This sum will contribute as 12 * 100) Similarly sum of digits at tens thousands place is 12. (This sum will contribute as 12 * 1000) Required sum of all numbers = 12 + (10 * 12) + (100 * 12) = 1332
Implementação:
C++ // C++ program to find sum of numbers formed // by all permutations of given set of digits #include // function to calculate factorial of a number int factorial ( int n ) { int f = 1 ; if ( n == 0 || n == 1 ) return 1 ; for ( int i = 2 ; i <= n ; i ++ ) f = f * i ; return f ; } // Function to calculate sum of all numbers int getSum ( int arr [] int n ) { // calculate factorial int fact = factorial ( n ); // sum of all the given digits at different // positions is same and is going to be stored // in digitsum. int digitsum = 0 ; for ( int i = 0 ; i < n ; i ++ ) digitsum += arr [ i ]; digitsum *= ( fact / n ); // Compute result (sum of all the numbers) int res = 0 ; for ( int i = 1 k = 1 ; i <= n ; i ++ ) { res += ( k * digitsum ); k = k * 10 ; } return res ; } // Driver program to test above function int main () { // n distinct digits int arr [] = { 1 2 3 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // Print sum of all the numbers formed printf ( '%d' getSum ( arr n )); return 0 ; }
Java // Java program to find sum // of numbers formed by all // permutations of given set // of digits import java.io.* ; class GFG { // function to calculate // factorial of a number static int factorial ( int n ) { int f = 1 ; if ( n == 0 || n == 1 ) return 1 ; for ( int i = 2 ; i <= n ; i ++ ) f = f * i ; return f ; } // Function to calculate // sum of all numbers static int getSum ( int arr [] int n ) { // calculate factorial int fact = factorial ( n ); // sum of all the given // digits at different // positions is same and // is going to be stored // in digitsum. int digitsum = 0 ; for ( int i = 0 ; i < n ; i ++ ) digitsum += arr [ i ] ; digitsum *= ( fact / n ); // Compute result (sum // of all the numbers) int res = 0 ; for ( int i = 1 k = 1 ; i <= n ; i ++ ) { res += ( k * digitsum ); k = k * 10 ; } return res ; } // Driver Code public static void main ( String [] args ) { // n distinct digits int arr [] = { 1 2 3 }; int n = arr . length ; // Print sum of all // the numbers formed System . out . println ( getSum ( arr n )); } } // This code is contributed // by ajit
Python3 # Python3 program to find sum of # numbers formed by all permutations # of given set of digits # function to calculate factorial # of a number def factorial ( n ): f = 1 if ( n == 0 or n == 1 ): return 1 for i in range ( 2 n + 1 ): f = f * i return f # Function to calculate sum # of all numbers def getSum ( arr n ): # calculate factorial fact = factorial ( n ) # sum of all the given digits at # different positions is same and # is going to be stored in digitsum. digitsum = 0 for i in range ( n ): digitsum += arr [ i ] digitsum *= ( fact // n ) # Compute result (sum of # all the numbers) res = 0 i = 1 k = 1 while i <= n : res += ( k * digitsum ) k = k * 10 i += 1 return res # Driver Code if __name__ == '__main__' : # n distinct digits arr = [ 1 2 3 ] n = len ( arr ) # Print sum of all the numbers formed print ( getSum ( arr n )) # This code is contributed by ita_c
C# // C# program to find sum // of numbers formed by all // permutations of given set // of digits using System ; class GFG { // function to calculate // factorial of a number static int factorial ( int n ) { int f = 1 ; if ( n == 0 || n == 1 ) return 1 ; for ( int i = 2 ; i <= n ; i ++ ) f = f * i ; return f ; } // Function to calculate // sum of all numbers static int getSum ( int [] arr int n ) { // calculate factorial int fact = factorial ( n ); // sum of all the given // digits at different // positions is same and // is going to be stored // in digitsum. int digitsum = 0 ; for ( int i = 0 ; i < n ; i ++ ) digitsum += arr [ i ]; digitsum *= ( fact / n ); // Compute result (sum // of all the numbers) int res = 0 ; for ( int i = 1 k = 1 ; i <= n ; i ++ ) { res += ( k * digitsum ); k = k * 10 ; } return res ; } // Driver Code static public void Main () { // n distinct digits int [] arr = { 1 2 3 }; int n = arr . Length ; // Print sum of all // the numbers formed Console . WriteLine ( getSum ( arr n )); } } // This code is contributed // by akt_mit
PHP // PHP program to find sum // of numbers formed by all // permutations of given set // of digits function to // calculate factorial of a number function factorial ( $n ) { $f = 1 ; if ( $n == 0 || $n == 1 ) return 1 ; for ( $i = 2 ; $i <= $n ; $i ++ ) $f = $f * $i ; return $f ; } // Function to calculate // sum of all numbers function getSum ( $arr $n ) { // calculate factorial $fact = factorial ( $n ); // sum of all the given // digits at different // positions is same and // is going to be stored // in digitsum. $digitsum = 0 ; for ( $i = 0 ; $i < $n ; $i ++ ) $digitsum += $arr [ $i ]; $digitsum *= ( $fact / $n ); // Compute result (sum // of all the numbers) $res = 0 ; for ( $i = 1 $k = 1 ; $i <= $n ; $i ++ ) { $res += ( $k * $digitsum ); $k = $k * 10 ; } return $res ; } // Driver Code // n distinct digits $arr = array ( 1 2 3 ); $n = sizeof ( $arr ); // Print sum of all // the numbers formed echo getSum ( $arr $n ); // This code is contributed by ajit ?>
JavaScript < script > // Javascript program to find sum of // numbers formed by all permutations // of given set of digits // Function to calculate // factorial of a number function factorial ( n ) { let f = 1 ; if ( n == 0 || n == 1 ) return 1 ; for ( let i = 2 ; i <= n ; i ++ ) f = f * i ; return f ; } // Function to calculate // sum of all numbers function getSum ( arr n ) { // Calculate factorial let fact = factorial ( n ); // Sum of all the given // digits at different // positions is same and // is going to be stored // in digitsum. let digitsum = 0 ; for ( let i = 0 ; i < n ; i ++ ) digitsum += arr [ i ]; digitsum *= ( fact / n ); // Compute result (sum // of all the numbers) let res = 0 ; for ( let i = 1 k = 1 ; i <= n ; i ++ ) { res += ( k * digitsum ); k = k * 10 ; } return res ; } // Driver code // n distinct digits let arr = [ 1 2 3 ]; let n = arr . length ; // Print sum of all // the numbers formed document . write ( getSum ( arr n )); // This code is contributed by susmitakundugoaldanga < /script>
Saída
1332
Complexidade de tempo: O(n)
Espaço Auxiliar: O(1)
Criar questionário
