Find the closest and smaller tidy number
Tidy Number are those number whose digits are arranged in non-decreasing order. Here, we are given a number and we have to find another number that is smaller but closest to the given number and also that number should be tidy, i.e., their digit should be in non-decreasing order.
Examples:
Input : 91234 Output : 89999 Tidy property is violated by appearing 1 after 9. So, we will reduce 9 by 1 and the number right to it will be replaced by 9. So, generated tidy number is 89999. Input : 45000 Output : 44999
The idea is to traverse from end. Whenever tidy property is violated, we reduce digit by one and make all subsequent digits 9.
C++
// C++ program to find closest// tidy number smaller than the // given number#include<bits/stdc++.h>using namespace std;char* tidyNum(char str[], int len){ for (int i = len-2; i >= 0; i--) { // check whether string violates tidy property if (str[i] > str[i+1]) { // if string violates tidy property, then // decrease the value stored at that index by 1 // and replace all the value stored right to // that index by 9 (char)str[i]--; for (int j=i+1; j<len; j++) str[j] = '9'; } } return str;}// Driver codeint main(){ char str[] = "11333445538"; int len = strlen(str); // num will store closest tidy number char *num = tidyNum(str, len); printf("%s\n", num); return 0;} |
Java
// Java program to find closest// tidy number smaller than the // given numberimport java.io.*;class GFG{static String tidyNum(String str1, int len){ char[] str = str1.toCharArray(); for (int i = len - 2; i >= 0; i--) { // check whether string // violates tidy property if (str[i] > str[i + 1]) { // if string violates tidy // property, then decrease the // value stored at that index // by 1 and replace all the value // stored right to that index by 9 str[i]--; for (int j = i + 1; j < len; j++) str[j] = '9'; } } return String.valueOf(str);}// Driver codepublic static void main(String[] args){ String str = "11333445538"; int len = str.length(); // num will store closest tidy number System.out.println(tidyNum(str, len));} }// This code is contributed by mits |
Python3
# Python 3 program to find closest# tidy number smaller than the # given numberdef tidyNum(str, len): for i in range(len-2, -1, -1): # check whether string # violates tidy property if (str[i] > str[i+1]): # if string violates tidy # property, then decrease the # value stored at that index by 1 # and replace all the value # stored right to that index by 9 str[i] -= 1 for j in range(i+1, len): str[j] = 9 return str# Driver codestr = [1,1,3,3,3,4,4,5,5,3,8] len = len(str) # num will store closest tidy numbernum = tidyNum(str, len) for i in range(0,len): print(str[i], end = "")# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# program to find closest// tidy number smaller than the // given numberusing System;class GFG{static String tidyNum(String str1, int len){ char[] str = str1.ToCharArray(); for (int i = len - 2; i >= 0; i--) { // check whether string // violates tidy property if (str[i] > str[i + 1]) { // if string violates tidy // property, then decrease the // value stored at that index // by 1 and replace all the value // stored right to that index by 9 str[i]--; for (int j = i + 1; j < len; j++) str[j] = '9'; } } string s = new string(str); return s;}// Driver codestatic void Main(){ String str = "11333445538"; int len = str.Length; // num will store closest tidy number Console.WriteLine(tidyNum(str, len));} }// This code is contributed by mits |
PHP
<?php// PHP program to find closest// tidy number smaller than the // given numberfunction tidyNum($str, $len){ for ($i = $len - 2; $i >= 0; $i--) { // check whether string // violates tidy property if ($str[$i] > $str[$i + 1]) { // if string violates tidy // property, then decrease // the value stored at that // index by 1 and replace all // the value stored right to // that index by 9 $x = ord($str[$i]); $x--; $str[$i] = chr($x); for ($j = $i + 1; $j < $len; $j++) $str[$j] = '9'; } } return $str;}// Driver code$str = "11333445538";$len = strlen($str);// num will store // closest tidy number$num = tidyNum($str, $len);echo $num;// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find closest// tidy number smaller than the // given numberfunction tidyNum(str1, len){ var str = str1.split(''); for (i = len - 2; i >= 0; i--) { // Check whether string // violates tidy property if (str[i] > str[i + 1]) { // If string violates tidy // property, then decrease the // value stored at that index // by 1 and replace all the value // stored right to that index by 9 str[i]--; for(j = i + 1; j < len; j++) str[j] = '9'; } } return str.join("");}// Driver codevar str = "11333445538";var len = str.length;// num will store closest tidy numberdocument.write(tidyNum(str, len));// This code is contributed by Amit Katiyar </script> |
Output:
11333444999
References :
This question is asked in Google Code Jam 2017 qualification round.
This article is contributed by Aditya kumar. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
