Given a large integer N, the task is to find the largest possible integer which is divisible by 9 after inserting exactly one digit from 0 to 9 anywhere in the N.
Note: Leading zeroes are not allowed.
Examples:
Input: N = “12”
Output: 612
Explanation: The numbers which are divisible by 9 after inserting digit are 612, 162, 126.
And the largest integer is 612. So the output is 612Input: N = “1346182944512412414214”
Output: 81346182944512412414214
Approach: The problem can be solved with the help of the below observation:
The idea is to insert the digit 0 to 9 at every position in the N and check is it divisible by 9 (divisible only if sum of digits is divisible by 9).
If it is found to be true then store the maximum value with position where digit is inserted and finally print the maximum value.
Follow the below steps to solve the problem:
- Initialize a pair variable, ( say maxi = {“”, 0}) to store the largest integer which is divisible by 9 with the position where the digit is inserted.
- Iterate over the range [0, len) and calculate the digit sum of the number (say stored in variable sum).
- Iterate over the range [0, len) and perform the following steps:
- Iterate for ch = ‘0’ to ‘9’ and perform the following steps:
- Check for leading 0s, if it is found to be true then continue with the iteration.
- Check if (ch – ‘0’) + sum is divisible by 9 (i.e. sum after inserting that digit in N). If it is found to be true then set or update the value of maxi to the new value.
- Iterate for ch = ‘0’ to ‘9’ and perform the following steps:
- Finally, print the value of the maximum number (stored in maxi.first).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check number is divisible by 9bool isDivBy9(char c, int sum){ return (((c - '0') + sum) % 9 == 0);}// Function to find the largest numberpair<string, int> maxNumber(pair<string, int> s1, string s2, int i){ if ((s1.first[s1.second] - '0') > (s2[s1.second] - '0')) return s1; return { s2, i };}// Function to find the largest integer// which is divisible by 9 after// inserting any digit in the Nstring findLargestNumber(string N, int len){ // Stores the largest integer which is // divisible by 9 pair<string, int> maxi = { "", 0 }; // Stores the sum of digits of N int sum = 0; for (int i = 0; i < len; i++) { // Update the value of sum sum += (N[i] - '0'); } for (int i = 0; i <= len; i++) { for (char ch = '0'; ch <= '9'; ch++) { // Skip leading zeroes if (i == 0 && ch == '0') continue; // Check number is divisible by 9 if (isDivBy9(ch, sum)) { // Check maxi is not set if (maxi.first.length() == 0) { // Set value of maxi maxi = { N.substr(0, i) + ch + N.substr(i), i }; } else { // Update value of maxi maxi = maxNumber(maxi, N.substr(0, i) + ch + N.substr(i), i); } } } } // Print the value of maxi.first return maxi.first;}// Driver Codeint main(){ string N = "12"; int len = N.length(); // Function call cout << findLargestNumber(N, len); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to check number is divisible by 9 static boolean isDivBy9(char c, int sum) { return (((c - '0') + sum) % 9 == 0); } // Function to find the largest number static String[] maxNumber(String[] s1, String s2, int i) { if ((s1[0].charAt(Integer.parseInt(s1[1])) - '0') > (s2.charAt(Integer.parseInt(s1[1])) - '0')) return s1; String[] map = { s2, Integer.toString(i) }; return map; } // Function to find the largest integer // which is divisible by 9 after // inserting any digit in the N static String findLargestNumber(String N, int len) { // Stores the largest integer which is // divisible by 9 String[] maxi = { "", "0" }; // Stores the sum of digits of N int sum = 0; for (int i = 0; i < len; i++) { // Update the value of sum sum += (N.charAt(i) - '0'); } for (int i = 0; i <= len; i++) { for (char ch = '0'; ch <= '9'; ch++) { // Skip leading zeroes if ((i == 0) && (ch == '0')) continue; // Check number is divisible by 9 if (isDivBy9(ch, sum)) { // Check maxi is not set if ((maxi[0]) == "") { // Set value of maxi maxi[0] = N.substring(0, i) + ch + N.substring(i); maxi[1] = Integer.toString(i); } else { // Update value of maxi maxi = maxNumber( maxi, N.substring(0, i) + ch + N.substring(i), i); } } } } // Print the value of maxi.first return maxi[0]; } // driver code public static void main(String[] args) { String N = "12"; int len = N.length(); // Function call System.out.print(findLargestNumber(N, len)); }}// This code is contributed by phasing17 |
Python3
# Python3 program for the above approach# Function to check number is divisible by 9def isDivBy9(c, sums): return ((c + sums) % 9) == 0# Function to find the largest numberdef maxNumber(s1, s2, i): if s1[0][s1[1]] > s2[s1[1]]: return s1 return [s2, i]# Function to find the largest integer# which is divisible by 9 after# inserting any digit in the Ndef findLargestNumber(N, length): # NOTE: we are using length as the variable name # instead of len because len is a predefined method in Python3 # that we will be using in this program # this is a good practice in code # Stores the largest integer which is # divisible by 9 maxi = ["", 0] # Stores the sum of digits of N sums = 0 for i in range(length): # Update the value of sum sums += ord(N[i]) - ord("0") for i in range(length + 1): for ch in range(10): # Skip leading zeroes if i == 0 and ch == 0: continue # Check number is divisible by 9 if isDivBy9(ch, sums): # Check maxi is not set if len(maxi[0]) == 0: # Set value of maxi maxi = [N[0:i] + str(ch) + N[i::], i] else: # Update value of maxi maxi = maxNumber(maxi, N[0:i] + str(ch) + N[i:], i) # Print the value of the first # element of maxi return maxi[0]# Driver CodeN = "12"length = len(N)# Function callprint(findLargestNumber(N, length))# This code is contributed by phasing17 |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to check number is divisible by 9 static bool isDivBy9(char c, int sum) { return ((((int)c - (int)('0')) + sum) % 9 == 0); } // Function to find the largest number static pair maxNumber(pair s1, String s2, int i) { if(s1.second == null){ return s1; } int x = int.Parse(s1.second); if(s1.first == null){ return s1; } if (((int)(s1.first[x]) - (int)('0')) > ((int)s2[x] - (int)('0'))){ return s1; } pair map = new pair(s2, i.ToString()); return map; } // Function to find the largest integer // which is divisible by 9 after // inserting any digit in the N static String findLargestNumber(String N, int len) { // Stores the largest integer which is // divisible by 9 pair maxi = new pair("", "0"); // Stores the sum of digits of N int sum = 0; for (int i = 0 ; i < len ; i++) { // Update the value of sum sum += ((int)N[i] - (int)('0')); } for (int i = 0 ; i <= len ; i++) { for (char ch = '0' ; ch <= '9' ; ch++) { // Skip leading zeroes if ((i == 0) && (ch == '0')) continue; // Check number is divisible by 9 if (isDivBy9(ch, sum)) { // Check maxi is not set if ((maxi.first) == "") { // Set value of maxi maxi.first = N.Substring(0, i) + ch + N.Substring(i); maxi.second = i.ToString(); } else { // Update value of maxi maxi = maxNumber(maxi, N.Substring(0, i) + ch + N.Substring(i), i); } } } } // Print the value of maxi.first return maxi.first; } public static void Main(string[] args){ String N = "12"; int len = N.Length; // Function call Console.Write(findLargestNumber(N, len)); }}public class pair{ public String first; public String second; public pair(String first, String second){ this.first = first; this.second = second; }}// This code is contributed by entertain2022. |
Javascript
<script> // JavaScript program for the above approach // Function to check number is divisible by 9 const isDivBy9 = (c, sum) => { return ((c + sum) % 9 == 0); } // Function to find the largest number const maxNumber = (s1, s2, i) => { if (s1[0][s1[1]] > s2[s1[1]]) return s1; return [s2, i]; } // Function to find the largest integer // which is divisible by 9 after // inserting any digit in the N const findLargestNumber = (N, len) => { // Stores the largest integer which is // divisible by 9 let maxi = ["", 0]; // Stores the sum of digits of N let sum = 0; for (let i = 0; i < len; i++) { // Update the value of sum sum += (N.charCodeAt(i) - '0'.charCodeAt(0)); } for (let i = 0; i <= len; i++) { for (let ch = 0; ch <= 9; ch++) { // Skip leading zeroes if (i == 0 && ch == 0) continue; // Check number is divisible by 9 if (isDivBy9(ch, sum)) { // Check maxi is not set if (maxi[0].length == 0) { // Set value of maxi maxi = [N.substring(0, i) + ch.toString() + N.substring(i), i]; } else { // Update value of maxi maxi = maxNumber(maxi, N.substr(0, i) + ch.toString() + N.substr(i), i); } } } } // Print the value of maxi.first return maxi[0]; } // Driver Code let N = "12"; let len = N.length; // Function call document.write(findLargestNumber(N, len));// This code is contributed by rakeshsahni</script> |
Output
612
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!
Share your thoughts in the comments
