Given a string N and a digit X ([1, 9]), the task is to find the minimum integer number formed by inserting digit X anywhere in N.
Examples:
Input: N = “89”, X = 1
Output: “189″
Explanation: X can be inserted at 3 positions {189, 891, 819} and 189 is the minimum.Input: N = “-12”, X = 3
Output: “-312″
Naive Approach: A simple approach to this problem is to insert X in all the positions (except the left of the negative sign if present) and find the minimum among all the numbers formed.The approach is inefficient in the case of larger strings.
Efficient Approach: The main idea is that if N is a positive insert in such a way that the number formed is minimum whereas if N is negative, then insert in X such as the number formed is maximum, ignoring the negative sign. Follow the steps below to optimize the above approach:
- Initialize two variables, say len = length of string N and position = n + 1.
- If N is negative (N[0] = ‘-‘), traverse the string from (n-1)th index to 1th index and check if N[i] – ‘0’ < X, if true then update position = i.
- If N is positive, traverse the string from (n-1)th index to 0th index and check if N[i] – ‘0’ > X, if true then update position = i.
- Insert X at index position in N.
- Finally, return the string N.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to insert X in N and// return the minimum value stringstring MinValue(string N, int X){ // Variable to store length // of string N int len = N.size(); // Variable to denote the position // where X must be added int position = len + 1; // If the given string N represent // a negative value if (N[0] == '-') { // X must be place at the last // index where is greater than N[i] for (int i = len - 1; i >= 1; i--) { if ((N[i] - '0') < X) { position = i; } } } else { // For positive numbers, X must be // placed at the last index where // it is smaller than N[i] for (int i = len - 1; i >= 0; i--) { if ((N[i] - '0') > X) { position = i; } } } // Insert X at that position N.insert(N.begin() + position, X + '0'); // Return the string return N;}// Driver Codeint main(){ // Given Input string N = "89"; int X = 1; // Function Call cout << MinValue(N, X) << "\n";} |
Java
// Java implementation of above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to insert X in N and // return the minimum value string static String MinValue(String number, int x) { // Variable to store length // of string N int length = number.length(); // Variable to denote the position // where X must be added int position = length + 1; // If the given string N represent // a negative value if (number.charAt(0) == '-') { // X must be place at the last // index where is greater than N[i] for (int i = number.length() - 1; i >= 1; --i) { if ((number.charAt(i) - 48) < x) { position = i; } } } else { // For positive numbers, X must be // placed at the last index where // it is smaller than N[i] for (int i = number.length() - 1; i >= 0; --i) { if ((number.charAt(i) - 48) > x) { position = i; } } } // Insert X at that position number = number.substring(0, position) + x + number.substring(position, number.length()); // return string return number.toString(); } // Driver call public static void main(String[] args) { // given input String number = "89"; int x = 1; // function call System.out.print(MinValue(number, x)); }}// This code is contributed by zack_aayush. |
Python3
# Python Program for the above approach# Function to insert X in N and# return the minimum value stringdef MinValue(N, X): # Variable to store length # of string N N = list(N); ln = len(N) # Variable to denote the position # where X must be added position = ln + 1 # If the given string N represent # a negative value if (N[0] == '-'): # X must be place at the last # index where is greater than N[i] for i in range(ln - 1, 0, -1): if ((ord(N[i]) - ord('0')) < X): position = i else: # For positive numbers, X must be # placed at the last index where # it is smaller than N[i] for i in range(ln - 1, -1, -1): if ((ord(N[i]) - ord('0')) > X): position = i # Insert X at that position c = chr(X + ord('0')) str = N.insert(position, c); # Return the string return ''.join(N)# Driver Code# Given InputN = "89"X = 1# Function Callprint(MinValue(N, X))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG { // Function to insert X in N and // return the minimum value string static String MinValue(string number, int x) { // Variable to store length // of string N int length = number.Length; // Variable to denote the position // where X must be added int position = length + 1; // If the given string N represent // a negative value if (number[0] == '-') { // X must be place at the last // index where is greater than N[i] for (int i = number.Length - 1; i >= 1; --i) { if ((number[i] - 48) < x) { position = i; } } } else { // For positive numbers, X must be // placed at the last index where // it is smaller than N[i] for (int i = number.Length - 1; i >= 0; --i) { if ((number[i] - 48) > x) { position = i; } } } // Insert X at that position number = number.Substring(0, position) + x + number.Substring(position, number.Length); // return string return number.ToString(); } // Driver code public static void Main() { // given input string number = "89"; int x = 1; // function call Console.WriteLine(MinValue(number, x)); }}// This code is contributed by avijitmondal1998. |
Javascript
<script> // JavaScript Program for the above approach // Function to insert X in N and // return the minimum value string function MinValue(N, X) { // Variable to store length // of string N let len = N.length; // Variable to denote the position // where X must be added let position = len + 1; // If the given string N represent // a negative value if (N[0] == '-') { // X must be place at the last // index where is greater than N[i] for (let i = len - 1; i >= 1; i--) { if ((N[i].charCodeAt(0) - '0'.charCodeAt(0)) < X) { position = i; } } } else { // For positive numbers, X must be // placed at the last index where // it is smaller than N[i] for (let i = len - 1; i >= 0; i--) { if ((N[i].charCodeAt(0) - '0'.charCodeAt(0)) > X) { position = i; } } } // Insert X at that position const c = String.fromCharCode(X + '0'.charCodeAt(0)); let str = N.slice(0, position) + c + N.slice(position); // Return the string return str; } // Driver Code // Given Input let N = "89"; let X = 1; // Function Call document.write(MinValue(N, X)); // This code is contributed by Potta Lokesh </script> |
Output
189
Time Complexity: O(N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
