Dado un número entero grande N , la tarea es encontrar el número entero más grande posible que sea divisible por 9 después de insertar exactamente un dígito del 0 al 9 en cualquier lugar de la N .
Nota: No se permiten ceros a la izquierda.
Ejemplos:
Entrada: N = «12»
Salida: 612
Explicación: Los números que son divisibles por 9 después de insertar dígitos son 612, 162, 126.
Y el entero más grande es 612. Entonces la salida es 612Entrada: N = “1346182944512412414214”
Salida: 81346182944512412414214
Enfoque: El problema se puede resolver con la ayuda de la siguiente observación:
La idea es insertar el dígito del 0 al 9 en cada posición de la N y verificar si es divisible por 9 (divisible solo si la suma de los dígitos es divisible por 9).
Si se encuentra que es cierto, almacene el valor máximo con la posición donde se inserta el dígito y finalmente imprima el valor máximo.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable de par, (digamos maxi = {“”, 0} ) para almacenar el entero más grande que es divisible por 9 con la posición donde se inserta el dígito.
- Iterar sobre el rango [0, len) y calcular la suma de dígitos del número (por ejemplo, almacenado en la variable sum ) .
- Iterar sobre el rango [0, len) y realizar los siguientes pasos:
- Iterar para ch = ‘0’ a ‘9’ y realizar los siguientes pasos:
- Verifique si hay 0 iniciales, si se encuentra que es cierto, continúe con la iteración.
- Compruebe si (ch – ‘0’) + suma es divisible por 9 (es decir, la suma después de insertar ese dígito en N ). Si se determina que es cierto, establezca o actualice el valor de maxi al nuevo valor.
- Iterar para ch = ‘0’ a ‘9’ y realizar los siguientes pasos:
- Finalmente, imprima el valor del número máximo (almacenado en maxi.first ).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check number is divisible by 9
bool isDivBy9(char c, int sum)
{
return (((c - '0') + sum) % 9 == 0);
}
// Function to find the largest number
pair<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 N
string 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 Code
int main()
{
string N = "12";
int len = N.length();
// Function call
cout << findLargestNumber(N, len);
return 0;
}
Java
// Java program for the above approach
import 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 9
def isDivBy9(c, sums):
return ((c + sums) % 9) == 0
# Function to find the largest number
def 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
def 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 Code
N = "12"
length = len(N)
# Function call
print(findLargestNumber(N, length))
# This code is contributed by phasing17
C#
// C# program to implement above approach
using 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>
Producción
612
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA