Maximize the number N by inserting given digit at any position
Given a positive integer N and a digit K, the task is to find the maximum value of the given number N by inserting the given digit K in it N.
Examples:
Input: N = 6673, K = 6
Output: 66763
Explanation:
All the numbers formed by inserting K at any position in N are {66673, 66763, 66736}. The maximum among all the formed number is 66763.Input: N = 1234, K = 5
Output: 51234
Approach: The given problem can be solved by inserting K at that position where the next digit is smaller than K. Follow the steps below to solve the problem:
- Initialize two strings say S, by typecasting the given number N into a string and a string result as “” to store the maximum possible number after inserting K in it.
- Initialize two variables, say L as the length of string S and i as 0.
- Traverse the string S until K is less than S[i] and append the character S[i] to the string result.
- Now append K to the result and then append all the remaining characters of the string to the result.
- After completing the above steps, print the string result and the maximum possible number.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum value // of N after inserting the digit K void maximizeNumber( int N, int K) { // Convert it into N to string string s = to_string(N); int L = s.length(); // Stores the maximum value of N // after inserting K string result; int i = 0; // Iterate till all digits that // are not less than K while ((i < L) && (K <= (s[i] - '0' ))) { // Add the current digit to // the string result result.push_back(s[i]); ++i; } // Add digit 'K' to result result.push_back( char (K + '0' )); // Iterate through all remaining // characters while (i < L) { // Add current digit to result result.push_back(s[i]); ++i; } // Print the maximum number formed cout << result; } // Driver Code int main() { int N = 6673, K = 6; maximizeNumber(N, K); return 0; } |
Java
// Java program for the above approach class GFG { // Function to find the maximum value // of N after inserting the digit K public static void maximizeNumber( int N, int K) { // Convert it into N to string String s = Integer.toString(N); int L = s.length(); // Stores the maximum value of N // after inserting K String result = "" ; int i = 0 ; // Iterate till all digits that // are not less than K while ((i < L) && (K <= (( int )s.charAt(i) - ( int ) '0' ))) { // Add the current digit to // the string result result += (s.charAt(i)); ++i; } // Add digit 'K' to result result += (( char )(K + ( int ) '0' )); // Iterate through all remaining // characters while (i < L) { // Add current digit to result result += (s.charAt(i)); ++i; } // Print the maximum number formed System.out.println(result); } // Driver Code public static void main (String args[]) { int N = 6673 , K = 6 ; maximizeNumber(N, K); } } // This code is contributed by _saurabh_Jaiswal. |
Python3
# Python 3 program for the above approach # Function to find the maximum value # of N after inserting the digit K def maximizeNumber(N, K): # Convert it into N to string s = str (N) L = len (s) # Stores the maximum value of N # after inserting K result = "" i = 0 # Iterate till all digits that # are not less than K while ((i < L) and (K < = ( ord (s[i]) - ord ( '0' )))): # Add the current digit to # the string result result + = (s[i]) i + = 1 # Add digit 'K' to result result + = ( chr (K + ord ( '0' ))) # Iterate through all remaining # characters while (i < L): # Add current digit to result result + = (s[i]) i + = 1 # Print the maximum number formed print (result) # Driver Code if __name__ = = "__main__" : N = 6673 K = 6 maximizeNumber(N, K) # This code is contributed by ukasp. |
C#
// C# program for above approach using System; class GFG{ // Function to find the maximum value // of N after inserting the digit K public static void maximizeNumber( int N, int K) { // Convert it into N to string String s = N.ToString(); int L = s.Length; // Stores the maximum value of N // after inserting K string result = "" ; int i = 0; // Iterate till all digits that // are not less than K while ((i < L) && (K <= (( int )s[i]- ( int ) '0' ))) { // Add the current digit to // the string result result += (s[i]); ++i; } // Add digit 'K' to result result += (( char )(K + ( int ) '0' )); // Iterate through all remaining // characters while (i < L) { // Add current digit to result result += (s[i]); ++i; } // Print the maximum number formed Console.Write(result); } // Driver Code static void Main() { int N = 6673, K = 6; maximizeNumber(N, K); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // Javascript program for the above approach // Function to find the maximum value // of N after inserting the digit K function maximizeNumber(N, K) { // Convert it into N to string let s = String(N); let L = s.length; // Stores the maximum value of N // after inserting K let result = []; let i = 0; // Iterate till all digits that // are not less than K while ((i < L) && (K <= (s[i].charCodeAt(0) - '0' .charCodeAt(0)))) { // Add the current digit to // the string result result.push(s[i]); ++i; } // Add digit 'K' to result result.push(String.fromCharCode(K + '0' .charCodeAt(0))); // Iterate through all remaining // characters while (i < L) { // Add current digit to result result.push(s[i]); ++i; } // Print the maximum number formed document.write(result.join( "" )); } // Driver Code let N = 6673, K = 6; maximizeNumber(N, K); // This code is contributed by gfgking. </script> |
Output:
66763
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us