Largest number smaller than or equal to n and digits in non-decreasing order - GeeksforGeeks
Given a number n, find the Largest number smaller than or equal to n and digits in non-decreasing order.
Read full article from Largest number smaller than or equal to n and digits in non-decreasing order - GeeksforGeeks
Given a number n, find the Largest number smaller than or equal to n and digits in non-decreasing order.
Step 1: Store the digits of the number in array or a vector.
Step 2: Start traversing the array from the digit from rightmost position to leftmost in given number.
Step 3: If a digit is greater than the digit in the right to it, note the index of that digit in that array and decrease that digit by one.
Step 4 : Keep updating that index until you completely traverse the array accordingly as discussed in step 3.
Step 4: Set all the digits right to that index as 9 .
Step 5 : Print the array as this is the required number.
Suppose the number is 200 the digits will be 2, 0, 0. The index at which leftmost digit is greater than the right digit is index 1 (following 1-index) so the number at index 1 will be 2 – 1 = 1 and all the digits right to it will be 9. So the final array will be 1, 9, 9. And the required number will be 199.
Time Complexity Time complexity is O(d) where d is no. of digits in the number.
void
nondecdigits(string s)
{
long
long
m = s.size();
/* array to store digits of number */
long
long
a[m];
/* conversion of characters of string int number */
for
(
long
long
i=0; i<m; i++)
a[i] = s[i] -
'0'
;
/* variable holds the value of index after which
all digits are set 9 */
long
long
level = m-1;
for
(
long
long
i=m-1; i>0; i--)
{
/* Checking the condition if the digit is
less than its left digit */
if
(a[i] < a[i-1])
{
a[i-1]--;
level=i-1;
}
}
/* If first digit is 0 no need to print it */
if
(a[0] != 0)
{
for
(
long
long
i=0; i<=level; i++)
cout << a[i];
for
(
long
long
i=level+1; i<m; i++)
cout <<
"9"
;
}
else
{
for
(
long
long
i=1; i<level; i++)
cout << a[i];
for
(
long
long
i=level+1; i<m; i++)
cout <<
"9"
;
}
}
long
long
nondecdigits(
long
long
n)
{
/* loop to recursively check the numbers less
than or equal to given number*/
long
long
int
x = 0;
for
(x=n; x>=1; x--)
{
int
no = x;
int
prev_dig = 11;
// Keep traversing digits from
// right to left. For every digit
// check if it is smaller than prev_dig
bool
flag =
true
;
while
(no != 0)
{
if
(prev_dig < no%10)
{
flag =
false
;
break
;
}
prev_dig = no % 10;
no /= 10;
}
// We found the required number
if
(flag ==
true
)
break
;
}
return
x;
}