top of page
Caută
Poza scriitoruluioanaunciuleanu

Total number of non-decreasing numbers with n digits in JAVA

A non-decreasing number has every digit greater than or equal to the previous digit. Given the number of digits, find how many numbers exist with non-decreasing digits.


Input: int digits = 3; Output: 220 Explanation: There are 220 numbers with 3 digits that have non-decreasing digits: …, 111, 112, …, 222, 223, 224, ….


Solution:


1. static int countNonDecreasing(int digits) { 2. int[][] nonDecreasingNumbers = new int[10][digits + 1]; 3. 4. for (int i = 0; i < 10; i++) { 5. nonDecreasingNumbers[i][1] = 1; 6. } 7. 8. for (int digit = 0; digit <= 9; digit++) { 9. for (int length = 2; length <= digits; length++) { 10. for (int lastDigit = 0; lastDigit <= digit; lastDigit++) { 11. nonDecreasingNumbers[digit][length] += nonDecreasingNumbers[lastDigit][length - 1]; 12. } 13. } 14. } 15. 16. int count = 0; 17. for (int i = 0; i < 10; i++) { 18. count += nonDecreasingNumbers[i][digits]; 19. } 20. return count; 21. } 22.

6 afișări0 comentarii

Postări recente

Afișează-le pe toate

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Subset Sum Problem in JAVA

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with the sum equal to the given...

Comments


bottom of page