Dada una array arr[] que tiene N enteros, la tarea es encontrar el siguiente número mayor X , es decir, X >= arr[i] para cada i en el rango [0, N) tal que el recuento de dígitos únicos en X sea exactamente 2 _
Ejemplo:
Entrada: arr[] = {123, 234}
Salida: 131 242
Explicación: Para la array dada, 131 es el número más pequeño mayor que 123 que tiene exactamente 2 dígitos únicos. De manera similar, 242 es el número más pequeño mayor que 234 que tiene exactamente 2 dígitos únicos.Entrada: arr[] = {35466666}
Salida: 35533333
Enfoque ingenuo: el problema dado se puede resolver iterando sobre todos los enteros mayores que arr[i] para cada i en el rango [0, N) y haciendo un seguimiento de los primeros enteros de modo que el recuento de dígitos únicos en el entero sea exactamente 2
Complejidad temporal: O(N * M), donde M representa el elemento máximo en el arr[].
Espacio auxiliar: O(log N)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Bitmasking . Se puede observar que todos los números enteros que tienen dos dígitos en el rango dado se pueden calcular iterando sobre todos los pares posibles de dos dígitos únicos y generando todos los dígitos que se pueden formar a partir de ellos. Puede ser hecho por el algoritmo discutido en este artículo. Posteriormente, se puede usar una estructura de datos establecida para almacenar todos los enteros, y para cada valor de arr[i] , se puede encontrar el entero más pequeño mayor que arr[i] usando la función lower_bound usando la búsqueda binaria .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
#define int long long
// Stores the set of integers with 2 unique digits
set<int> helper;
vector<int> nums;
// Function to find the value of a^b
int power(int a, int b)
{
// Stores the value
int ans = 1;
while (b > 0) {
if (b & 1) {
ans = ans * a;
}
b = b >> 1;
a = a * a;
}
// Return Answer
return ans;
}
void nextGreaterEle(int arr[], int N)
{
// Loop to iterate the given array
for (int i = 0; i < N; i++) {
// For each array element, find next
// greater element in the vector nums
// of integers using lower_bound
cout << *lower_bound(nums.begin(), nums.end(),
arr[i])
<< " ";
}
}
// Function to calculate the digits having
// exactly two unique digits
void preProcess()
{
// Loop to iterate over all possible
// pairs of digits from 0 to 9
for (int i = 0; i <= 9; i++) {
for (int j = 0; j <= 9; j++) {
// Stores the maximum length of integer
int len = 10;
for (int k = 0; k <= (1 << len); k++) {
int temp = k;
int number = 0;
int curLen = 0;
while (temp > 0) {
if (temp & 1) {
// Include numbers with the
// next digit as i
number = i * power(10, curLen)
+ number;
}
else {
// Include numbers with the next
// next digit as j
number = j * power(10, curLen)
+ number;
}
// Update temp
temp = (temp >> 1);
curLen++;
}
// Insert the current number into the set
helper.insert(number);
while (curLen <= len) {
number = j * power(10, curLen) + number;
helper.insert(number);
curLen++;
}
}
}
}
// Loop to insert all the integers into
// a vector from the set if the unique digits
// in the integer is exactly two.
for (auto cur : helper) {
// Stores the unique digits
set<int> count;
int orz = cur;
while (cur > 0) {
count.insert(cur % 10);
cur = cur / 10;
}
// If count of exactly two
if (count.size() == 2) {
nums.push_back(orz);
}
}
}
// Driver Code
signed main()
{
int arr[] = { 123, 234 };
int N = sizeof(arr) / sizeof(arr[0]);
preProcess();
nextGreaterEle(arr, N);
return 0;
}
Python3
## Python program for the above approach:
import bisect
## Stores the set of integers with 2 unique digits
helper = set({})
nums = []
## Function to find the value of a^b
def power(a, b):
## Stores the value
ans = 1;
while (b > 0):
if (b & 1) == 1:
ans = ans * a;
b = b // 2;
a = a * a;
## Return Answer
return ans;
def nextGreaterEle(arr, N):
## Loop to iterate the given array
for i in range(0, N):
## For each array element, find next
## greater element in the vector nums
## of integers using lower_bound
print(nums[bisect.bisect_left(nums, arr[i])], end=" ")
print("")
## Function to calculate the digits having
## exactly two unique digits
def preProcess():
## Loop to iterate over all possible
## pairs of digits from 0 to 9
for i in range(0, 10):
for j in range(0, 10):
## Stores the maximum length of integer
leng = 10
for k in range(0, (1<<leng) + 1):
temp = k
number = 0
curLen = 0
while (temp > 0):
if (temp & 1) == 1:
## Include numbers with the
## next digit as i
number = i * power(10, curLen) + number;
else:
## Include numbers with the next
## next digit as j
number = j * power(10, curLen) + number;
## Update temp
temp = (temp // 2);
curLen+=1
## Insert the current number into the set
helper.add(number);
while curLen <= leng:
number = j * power(10, curLen) + number;
helper.add(number);
curLen+=1
## Loop to insert all the integers into
## a vector from the set if the unique digits
## in the integer is exactly two.
for cur in helper:
## Stores the unique digits
count = set({})
orz = cur
while (cur > 0):
count.add(cur % 10)
cur = cur // 10
## If count of exactly two
if len(count) == 2:
nums.append(orz)
nums.sort()
## Driver code
if __name__=='__main__':
arr = [ 123, 234 ];
N = len(arr)
preProcess()
nextGreaterEle(arr, N)
# This code is contributed by subhamgoyal2014.
131 242
Complejidad de tiempo: O(10 6 + N * log N) = O(N * log N)
Espacio auxiliar: O(10 6 ) = O(1)
Publicación traducida automáticamente
Artículo escrito por Sashibhushanrajput y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA