Monotone Increasing Digits
Given a non-negative integer N, find the largest number that is less
than or equal to N with monotone increasing digits.
(An integer has monotone increasing digits if and only if each pair
of adjacent digits x and y satisfy x <= y.)
Examples :
Input: N = 10
Output: 9
Input: N = 1234
Output: 1234
Input: N = 332
Output: 299
import java.util.*;
class Solution {
public static int monotoneIncreasingDigits(int N) {
String S = String.valueOf(N);
String ans = "";
search: for (int i = 0; i < S.length(); ++i) {
for (char d = '1'; d <= '9'; ++d) {
if (S.compareTo(ans + repeat(d, S.length() - i)) < 0) {
ans += (char) (d - 1);
continue search;
}
}
ans += '9';
}
return Integer.parseInt(ans);
}
public static String repeat(char c, int count) {
StringBuilder sb = new StringBuilder(count);
for (int i = 0; i < count; ++i) sb.append(c);
return sb.toString();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = Integer.parseInt(sc.nextLine());
int output = monotoneIncreasingDigits(num);
System.out.print(output);
}
}
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment