Somme de tous les nombres pouvant être formés avec des permutations de n chiffres
Essayez-le sur GfG Practice 
#practiceLinkDiv { display : aucun !important; }
Sortir
#practiceLinkDiv { display : aucun !important; } Étant donné n chiffres distincts (de 0 à 9), trouvez la somme de tous les nombres à n chiffres pouvant être formés à l'aide de ces chiffres. On suppose que les nombres formés avec un 0 en tête sont autorisés.
Exemple:
Input: 1 2 3 Output: 1332 Explanation Numbers Formed: 123 132 312 213 231 321 123 + 132 + 312 + 213 + 231 + 321 = 1332Recommended Practice Somme des permutations Essayez-le !
Le nombre total qui peut être formé à l'aide de n chiffres est le nombre total de permutations de n chiffres, c'est-à-dire factoriel (n). Maintenant, puisque le nombre formé est un nombre à n chiffres, chaque chiffre apparaîtra factoriellement (n)/n fois à chaque position, du chiffre le moins significatif au chiffre le plus significatif. Par conséquent somme des chiffres à une position = (somme de tous les chiffres) * (factorielle(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
Mise en œuvre:
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>
Sortir
1332
Complexité temporelle : O(n)
Espace auxiliaire : O(1)
