Total number of non-decreasing numbers with n digits

A number is non-decreasing if every digit (except the first one) is greater than or equal to previous digit. For example, 223, 4455567, 899, are non-decreasing numbers.
So, given the number of digits n, you are required to find the count of total non-decreasing numbers with n digits.

Examples : 

Input : digits = 1
Output : count = 10

Input : digits = 2
Output : count = 55

Input : digits = 3
Output : count = 220

Program : 

import java.util.Scanner;

public class TotalNumberOfNonDecreasingNumbers {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of digits : ");
int noOfdigits = sc.nextInt();
/*Calculate the highest number to repeat the loop
  for example, if number of digits is 1, then we need to repeat loop until 9 
  if number of digits is 2, then we need to repeat loop until 99.*/
int n = 1;
for(int i=1; i<=noOfdigits; i++) {
n = n * 10;
}
n = n - 1;
/*loop until highest number and verify each number is non-decreasing or not ?
If yes, increase the count.*/
int count = 0;
for(int i=0; i<=n ; i++) {
if(isNonDecreasingNumber(i))
count ++;
}
System.out.println("Number of non-descreasing numbers : "+count);
}
/* First initialize the prevDigit value as -1.
* Take the last digit and compare previous digit (prevDigit) is greater than or equal to current digit (curDigit).
* If yes repeat the process, else break the loop and return false.
*/
public static boolean isNonDecreasingNumber(int n) {
boolean isNonDecreasngNum = true;
int prevDigit = -1;
while(n > 0) {
int curDigit = n % 10;
if(prevDigit == -1 || prevDigit >= curDigit)
prevDigit = curDigit;
else {
isNonDecreasngNum = false;
break;
}
n = n / 10;
}
return isNonDecreasngNum;
}
}

Output :

Enter number of digits : 1
Number of non-descreasing numbers : 10

Enter number of digits : 2
Number of non-descreasing numbers : 55

Enter number of digits : 3
Number of non-descreasing numbers : 220

No comments:

Post a Comment