Dado un número representado en forma de array tal que cada elemento de la array almacena un solo dígito del número. Es decir, la array para el número 1234 será arr[] = {1,2,3,4}. La tarea es encontrar el menor número mayor que el número dado pero que tenga la suma de dígitos igual al número dado. Para simplificar : considere que la longitud del número puede ser 20 como máximo. Ejemplos :
Entrada : arr[] = {0, 0, 0, 0, 0, 0, 0, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8}; Salida : 00000004799999999999 Explicación : Suma de dígitos = 110 Entrada : arr[] = {0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5 , 9, 9, 0}; Salida : 00000003970029896089 Explicación : Suma de dígitos = 70
Un enfoque de fuerza bruta es:
- Comience desde ese número e incremente el número en uno.
- Verifica la suma. Si la suma es la misma, devuelve el número.
- De lo contrario, vuelva al paso uno.
Un mejor enfoque es saltar al siguiente número en complejidad de tiempo O(n), donde n es la longitud de la string.
Dividimos el número en 4 regiones: 1ª : ceros finales. 2º : El dígito más bajo que no está en la Región 1. 3º : Nueve consecutivos que comienzan con el dígito por encima de la Región 2. 4º : Todos los dígitos restantes. Luego, el siguiente número es: [Región 4+1] [Región 1] [Región 2-1] [Región 3] . Ejemplo : Número de entrada = 548995000 Región 1: 000 Región 2: 5 Región 3: 99 Región 4: 548 Número siguiente = 549000499
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find next greater number with
// same sum of digits.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void getnext(int arr[], int n)
{
// for storing 4 regions
vector<int> a1, a2, a3, a4;
// trailing zeros region1
int i = n - 1; // last index
while (arr[i] == 0)
{
a1.pb(0);
i--;
}
// lowest region(region 2) not in region 1
a2.pb(arr[i--]);
// Consecutive 9's (region 3)
while (arr[i] == 9)
{
a3.pb(9);
i--;
}
int j = 0;
while (arr[j] == 0)
j++; // Starting zeros
while (j <= i) // 4th region
{
a4.pb(arr[j]);
j++;
}
// Calculation of result
j = a4.size() - 1;
a4[j]++; // Region4 + 1
a2[0]--; // Region2 -1
int l = a1.size() + a2.size() + a3.size() + a4.size();
// Calculating the result
j = n-1;
i = a3.size() - 1;
// Copying the third region
while (i >= 0)
{
arr[j--] = a3[i--];
}
// Copying the 2nd region
i = a2.size() - 1;
while (i >= 0)
{
arr[j--] = a2[i--];
}
// Copying the 1st region
i = a1.size() - 1;
while (i >= 0)
{
arr[j--] = a1[i--];
}
// Copying the 4th region
i = a4.size() - 1;
while (i >= 0)
{
arr[j--] = a4[i--];
}
while (j >= 0)
arr[j--] = 0;
}
int main()
{
int arr[] = { 0, 0, 0, 0, 0, 0, 0, 3, 9, 7,
0, 0, 2, 9, 8, 9, 5, 9, 9, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
getnext(arr, n); // Calling the function
for (int i = 0; i < n; i++)
cout << arr[i];
return 0;
}
Java
// Java program to find next greater number with
// same sum of digits.
import java.util.*;
class GFG
{
static void getnext(int []arr, int n)
{
// for storing 4 regions
ArrayList<Integer> a1 = new ArrayList<Integer>();
ArrayList<Integer> a2 = new ArrayList<Integer>();
ArrayList<Integer> a3 = new ArrayList<Integer>();
ArrayList<Integer> a4 = new ArrayList<Integer>();
// trailing zeros region1
int i = n - 1; // last index
while (arr[i] == 0)
{
a1.add(0);
i--;
}
// lowest region(region 2) not in region 1
a2.add(arr[i--]);
// Consecutive 9's (region 3)
while (arr[i] == 9)
{
a3.add(9);
i--;
}
int j = 0;
while (arr[j] == 0)
j++; // Starting zeros
while (j <= i) // 4th region
{
a4.add(arr[j]);
j++;
}
// Calculation of result
j = a4.size() - 1;
a4.set(j,a4.get(j) + 1); // Region4 + 1
a2.set(0,a2.get(0) - 1); // Region2 -1
//int l = a1.size() + a2.size() + a3.size() + a4.size();
// Calculating the result
j = n - 1;
i = a3.size() - 1;
// Copying the third region
while (i >= 0)
{
arr[j--] = (int)a3.get(i);
i--;
}
// Copying the 2nd region
i = a2.size() - 1;
while (i >= 0)
{
arr[j--] = (int)a2.get(i);
i--;
}
// Copying the 1st region
i = a1.size() - 1;
while (i >= 0)
{
arr[j--] = a1.get(i);
i--;
}
// Copying the 4th region
i = a4.size() - 1;
while (i >= 0)
{
arr[j--] = a4.get(i);
i--;
}
while (j >= 0)
arr[j--] = 0;
}
// Driver code
public static void main (String[] args)
{
int []arr = { 0, 0, 0, 0, 0, 0, 0, 3, 9, 7,
0, 0, 2, 9, 8, 9, 5, 9, 9, 0 };
int n = arr.length;
getnext(arr, n); // Calling the function
for (int i = 0; i < n; i++)
System.out.print(arr[i]);
}
}
// This code is contributed by mits
Python3
# Python3 program to find next greater number with # same sum of digits. def getnext(arr, n): # for storing 4 regions a1=[]; a2=[]; a3=[]; a4=[]; # trailing zeros region1 i = n - 1; # last index while (arr[i] == 0): a1.append(0); i-=1; # lowest region(region 2) not in region 1 a2.append(arr[i]); i-=1; # Consecutive 9's (region 3) while (arr[i] == 9): a3.append(9); i-=1; j = 0; while (arr[j] == 0): j+=1; # Starting zeros while (j <= i): # 4th region a4.append(arr[j]); j+=1; # Calculation of result j = len(a4) - 1; a4[j]+=1; # Region4 + 1 a2[0]-=1; # Region2 -1 l = len(a1) + len(a2) + len(a3) + len(a4); # Calculating the result j = n-1; i = len(a3) - 1; # Copying the third region while (i >= 0): arr[j] = a3[i]; j-=1; i-=1; # Copying the 2nd region i = len(a2) - 1; while (i >= 0): arr[j] = a2[i]; j-=1; i-=1; # Copying the 1st region i = len(a1) - 1; while (i >= 0): arr[j] = a1[i]; j-=1; i-=1; # Copying the 4th region i = len(a4) - 1; while (i >= 0): arr[j] = a4[i]; j-=1; i-=1; while (j >= 0): arr[j] = 0; j-=1; # Driver code arr = [ 0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0 ]; n = len(arr); getnext(arr, n); # Calling the function for i in range(0,n): print(arr[i],end=""); # This code is contributed by mits
C#
// C# program to find next greater number with
// same sum of digits.
using System;
using System.Collections;
class GFG
{
static void getnext(int []arr, int n)
{
// for storing 4 regions
ArrayList a1 = new ArrayList();
ArrayList a2 = new ArrayList();
ArrayList a3 = new ArrayList();
ArrayList a4 = new ArrayList();
// trailing zeros region1
int i = n - 1; // last index
while (arr[i] == 0)
{
a1.Add(0);
i--;
}
// lowest region(region 2) not in region 1
a2.Add(arr[i--]);
// Consecutive 9's (region 3)
while (arr[i] == 9)
{
a3.Add(9);
i--;
}
int j = 0;
while (arr[j] == 0)
j++; // Starting zeros
while (j <= i) // 4th region
{
a4.Add(arr[j]);
j++;
}
// Calculation of result
j = a4.Count - 1;
a4[j] = (int)a4[j] + 1; // Region4 + 1
a2[0] = (int)a2[0] - 1; // Region2 -1
//int l = a1.Count + a2.Count + a3.Count + a4.Count;
// Calculating the result
j = n - 1;
i = a3.Count - 1;
// Copying the third region
while (i >= 0)
{
arr[j--] = (int)a3[i];
i--;
}
// Copying the 2nd region
i = a2.Count - 1;
while (i >= 0)
{
arr[j--] = (int)a2[i];
i--;
}
// Copying the 1st region
i = a1.Count - 1;
while (i >= 0)
{
arr[j--] = (int)a1[i];
i--;
}
// Copying the 4th region
i = a4.Count - 1;
while (i >= 0)
{
arr[j--] = (int)a4[i];
i--;
}
while (j >= 0)
arr[j--] = 0;
}
// Driver code
static void Main()
{
int []arr = { 0, 0, 0, 0, 0, 0, 0, 3, 9, 7,
0, 0, 2, 9, 8, 9, 5, 9, 9, 0 };
int n = arr.Length;
getnext(arr, n); // Calling the function
for (int i = 0; i < n; i++)
Console.Write(arr[i]);
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find next greater number with
// same sum of digits.
function getnext(&$arr, $n)
{
// for storing 4 regions
$a1=array();
$a2=array();
$a3=array();
$a4=array();
// trailing zeros region1
$i = $n - 1; // last index
while ($arr[$i] == 0)
{
array_push($a1,0);
$i--;
}
// lowest region(region 2) not in region 1
array_push($a2,$arr[$i--]);
// Consecutive 9's (region 3)
while ($arr[$i] == 9)
{
array_push($a3,9);
$i--;
}
$j = 0;
while ($arr[$j] == 0)
$j++; // Starting zeros
while ($j <= $i) // 4th region
{
array_push($a4,$arr[$j]);
$j++;
}
// Calculation of result
$j = count($a4) - 1;
$a4[$j]++; // Region4 + 1
$a2[0]--; // Region2 -1
$l = count($a1) + count($a2) + count($a3) + count($a4);
// Calculating the result
$j = $n-1;
$i = count($a3) - 1;
// Copying the third region
while ($i >= 0)
{
$arr[$j--] = $a3[$i--];
}
// Copying the 2nd region
$i = count($a2) - 1;
while ($i >= 0)
{
$arr[$j--] = $a2[$i--];
}
// Copying the 1st region
$i = count($a1) - 1;
while ($i >= 0)
{
$arr[$j--] = $a1[$i--];
}
// Copying the 4th region
$i = count($a4) - 1;
while ($i >= 0)
{
$arr[$j--] = $a4[$i--];
}
while ($j >= 0)
$arr[$j--] = 0;
}
// Driver code
$arr = array( 0, 0, 0, 0, 0, 0, 0, 3, 9, 7,
0, 0, 2, 9, 8, 9, 5, 9, 9, 0 );
$n = count($arr);
getnext($arr, $n); // Calling the function
for ($i = 0; $i < $n; $i++)
echo $arr[$i];
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program to find next greater number with
// same sum of digits.
function getnext(arr, n)
{
// for storing 4 regions
let a1 = [], a2 = [], a3 = [], a4 = [];
// trailing zeros region1
let i = n - 1; // last index
while (arr[i] == 0)
{
a1.push(0);
i--;
}
// lowest region(region 2) not in region 1
a2.push(arr[i--]);
// Consecutive 9's (region 3)
while (arr[i] == 9)
{
a3.push(9);
i--;
}
let j = 0;
while (arr[j] == 0)
j++; // Starting zeros
while (j <= i) // 4th region
{
a4.push(arr[j]);
j++;
}
// Calculation of result
j = a4.length - 1;
a4[j]++; // Region4 + 1
a2[0]--; // Region2 -1
let l = a1.length + a2.length + a3.length + a4.length;
// Calculating the result
j = n-1;
i = a3.length - 1;
// Copying the third region
while (i >= 0)
{
arr[j--] = a3[i--];
}
// Copying the 2nd region
i = a2.length - 1;
while (i >= 0)
{
arr[j--] = a2[i--];
}
// Copying the 1st region
i = a1.length - 1;
while (i >= 0)
{
arr[j--] = a1[i--];
}
// Copying the 4th region
i = a4.length - 1;
while (i >= 0)
{
arr[j--] = a4[i--];
}
while (j >= 0)
arr[j--] = 0;
}
// driver code
let arr = [ 0, 0, 0, 0, 0, 0, 0, 3, 9, 7,
0, 0, 2, 9, 8, 9, 5, 9, 9, 0 ];
let n = arr.length;
getnext(arr, n); // Calling the function
for (let i = 0; i < n; i++)
document.write(arr[i]);
// code is contributed by shinjanpatra
</script>
Producción:
00000003970029896089
Publicación traducida automáticamente
Artículo escrito por abhijeetkaurav1st y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA