Dados dos números enteros N y M y una array 2D arr[] , la tarea es construir el número entero más pequeño posible de N dígitos ( sin ceros a la izquierda ) de modo que el arr[i][0] th dígito de la izquierda sea arr[i ][1] . Si no es posible construir ningún entero de este tipo, imprima «No» . De lo contrario, imprima ese número.
Ejemplos:
Entrada: N = 3, arr[]={{0, 7}, {2, 2}}
Salida: 702
Explicación: De acuerdo con las condiciones, el 1er y 3er dígito debe ser igual a 7 y 2. El número debe ser de la forma 7 _ 2. Por lo tanto, el número entero mínimo posible es 702.Entrada: N = 3, arr[]={{1, 1}, {1, 3}}
Salida: No
Enfoque ingenuo: dado que los dígitos siempre serán del 0 al 9 , el enfoque más simple es buscar una combinación de todos los números enteros que superen el 0 y sean inferiores a 10 N colocando los dígitos de acuerdo con las condiciones dadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if num satisfies the
// arrangement specified by the vector A
bool check(int num, int N, int M,
vector<pair<int, char> >& A)
{
// Convert num to equivalent string
string temp = to_string(num);
// If the number of digits
// is not equal to N
if (temp.size() != N) {
return false;
}
// Iterate over the vector A
for (int i = 0; i < M; i++) {
// If the digit at A[i].first position
// not the same as A[i].second
if (temp[A[i].first] != A[i].second) {
return false;
}
}
return true;
}
// Function to find the smallest integer
// satisfying the given conditions
void find_num(int N, vector<pair<int, char> >& A)
{
int ans = -1;
// Check for every combination upto 10^N
for (int i = 0; i < pow(10, N); i++) {
// If condition satisfies
if (check(i, N, A.size(), A)) {
ans = i;
break;
}
}
if (ans == -1)
cout << "No";
else
cout << ans;
}
// Driver Code
int main()
{
int N = 3;
vector<pair<int, char> > A
= { { 0, '7' }, { 2, '2' }, { 0, '7' } };
find_num(N, A);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static class pair
{
int first;
char second;
public pair(int first, char second)
{
this.first = first;
this.second = second;
}
};
// Function to check if num satisfies the
// arrangement specified by the vector A
static boolean check(int num, int N, int M,
Vector<pair> A)
{
// Convert num to equivalent String
String temp = String.valueOf(num);
// If the number of digits
// is not equal to N
if (temp.length() != N) {
return false;
}
// Iterate over the vector A
for (int i = 0; i < M; i++) {
// If the digit at A[i].first position
// not the same as A[i].second
if (temp.charAt(A.get(i).first) != A.get(i).second) {
return false;
}
}
return true;
}
// Function to find the smallest integer
// satisfying the given conditions
static void find_num(int N, Vector<pair> A)
{
int ans = -1;
// Check for every combination upto 10^N
for (int i = 0; i < Math.pow(10, N); i++) {
// If condition satisfies
if (check(i, N, A.size(), A)) {
ans = i;
break;
}
}
if (ans == -1)
System.out.print("No");
else
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
Vector<pair> A = new Vector<>();
A.add(new pair(0, '7' ));
A.add(new pair(2, '2'));
A.add(new pair( 0, '7'));
find_num(N, A);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to check if num satisfies the
# arrangement specified by the vector A
def check(num, N, M, A) :
# Convert num to equivalent string
temp = str(num)
# If the number of digits
# is not equal to N
if (len(temp) != N) :
return False
# Iterate over the vector A
for i in range(M) :
# If the digit at A[i].first position
# not the same as A[i].second
if (temp[A[i][0]] != A[i][1]) :
return False
return True
# Function to find the smallest integer
# satisfying the given conditions
def find_num(N, A) :
ans = -1
# Check for every combination upto 10^N
for i in range(pow(10, N)) :
# If condition satisfies
if (check(i, N, len(A), A)) :
ans = i
break
if (ans == -1) :
print("No")
else :
print(ans)
N = 3
A = [ [ 0, '7' ], [ 2, '2' ], [ 0, '7' ] ]
find_num(N, A)
# This code is contributed by divyesh072019
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
public class pair
{
public int first;
public char second;
public pair(int first, char second)
{
this.first = first;
this.second = second;
}
};
// Function to check if num satisfies the
// arrangement specified by the vector A
static bool check(int num, int N, int M,
List<pair> A)
{
// Convert num to equivalent String
String temp = String.Join("",num);
// If the number of digits
// is not equal to N
if (temp.Length != N) {
return false;
}
// Iterate over the vector A
for (int i = 0; i < M; i++) {
// If the digit at A[i].first position
// not the same as A[i].second
if (temp[A[i].first] != A[i].second) {
return false;
}
}
return true;
}
// Function to find the smallest integer
// satisfying the given conditions
static void find_num(int N, List<pair> A)
{
int ans = -1;
// Check for every combination upto 10^N
for (int i = 0; i < Math.Pow(10, N); i++) {
// If condition satisfies
if (check(i, N, A.Count, A)) {
ans = i;
break;
}
}
if (ans == -1)
Console.Write("No");
else
Console.Write(ans);
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
List<pair> A = new List<pair>();
A.Add(new pair(0, '7' ));
A.Add(new pair(2, '2'));
A.Add(new pair( 0, '7'));
find_num(N, A);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if num satisfies the
// arrangement specified by the vector A
function check(num, N, M, A)
{
// Convert num to equivalent string
var temp = (num.toString());
// If the number of digits
// is not equal to N
if (temp.length != N) {
return false;
}
// Iterate over the vector A
for (var i = 0; i < M; i++) {
// If the digit at A[i][0] position
// not the same as A[i][1]
if (temp[A[i][0]] != A[i][1]) {
return false;
}
}
return true;
}
// Function to find the smallest integer
// satisfying the given conditions
function find_num(N, A)
{
var ans = -1;
// Check for every combination upto 10^N
for (var i = 0; i < Math.pow(10, N); i++) {
// If condition satisfies
if (check(i, N, A.length, A)) {
ans = i;
break;
}
}
if (ans == -1)
document.write( "No");
else
document.write( ans);
}
// Driver Code
var N = 3;
var A = [ [ 0, '7' ], [ 2, '2' ], [ 0, '7' ] ];
find_num(N, A);
</script>
Producción:
702
Complejidad temporal: O(10 N * M)
Espacio auxiliar: O(N)
Enfoque eficiente: siga los pasos a continuación para resolver el problema:
- Inicialice un Mapa , digamos mp , para asignar dígitos a las posiciones correspondientes.
- Si el primer dígito que debe colocarse es 0 , imprima «No» , ya que el número no puede contener ceros a la izquierda.
- Recorra la array arr[] e inserte los dígitos en los índices respectivos en el Mapa .
- Ejecute un ciclo de 1 a N y para cada i , verifique si un dígito está asignado a la i -ésima posición en el Mapa . Si está presente en el Mapa , agréguelo a la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest integer
// satisfying the given conditions
void find_num(int N, vector<pair<int, int> >& A)
{
// Stores the digits at their
// respective positions
map<int, int> mp;
// Traverse the array
for (int i = 0; i < A.size(); i++) {
// If first digit required
// to be placed is 0
if (N > 1 and A[i].first == 0
and A[i].second == 0) {
// Not possible
cout << "No";
return;
}
// If multiple numbers are assigned
// to be placed in a single position
if (mp.find(A[i].first) != mp.end()
and mp[A[i].first] != A[i].second) {
// Not possible
cout << "No";
return;
}
// Assign the digits to their
// respective positions
mp[A[i].first] = A[i].second;
}
// Stores the result
string ans = "";
// Traverse for all N digits
for (int i = 0; i < N; i++) {
// For the first position
if (N > 1 and i == 0) {
// If digit is assigned
// to the position
if (mp.find(0) != mp.end()) {
ans += to_string(mp[0]);
}
// Otherwise
else {
ans += to_string(1);
}
}
else {
// Add it to answer
ans += to_string(mp[i]);
}
}
cout << ans << "\n";
}
// Driver Code
int main()
{
int N = 3;
vector<pair<int, int> > A
= { { 0, 7 }, { 2, 2 }, { 0, 7 } };
find_num(N, A);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find the smallest integer
// satisfying the given conditions
static void find_num(int N, pair []A)
{
// Stores the digits at their
// respective positions
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse the array
for(int i = 0; i < A.length; i++)
{
// If first digit required
// to be placed is 0
if (N > 1 && A[i].first == 0 &&
A[i].second == 0)
{
// Not possible
System.out.print("No");
return;
}
// If multiple numbers are assigned
// to be placed in a single position
if (mp.containsKey(A[i].first) &&
mp.get(A[i].first) != A[i].second)
{
// Not possible
System.out.print("No");
return;
}
// Assign the digits to their
// respective positions
mp.put(A[i].first, A[i].second);
}
// Stores the result
String ans = "";
// Traverse for all N digits
for(int i = 0; i < N; i++)
{
// For the first position
if (N > 1 && i == 0)
{
// If digit is assigned
// to the position
if (mp.containsKey(0))
{
ans += String.valueOf(mp.get(0));
}
// Otherwise
else
{
ans += String.valueOf(1);
}
}
else
{
// Add it to answer
if (mp.get(i) == null)
ans += String.valueOf(0);
else
ans += String.valueOf(mp.get(i));
}
}
System.out.print(ans + "\n");
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
pair []A = { new pair(0, 7),
new pair(2, 2),
new pair(0, 7)};
find_num(N, A);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement
# the above approach
# Function to find the smallest integer
# satisfying the given conditions
def find_num(N, A) :
# Stores the digits at their
# respective positions
mp = {}
# Traverse the array
for i in range(len(A)) :
# If first digit required
# to be placed is 0
if ((N > 1) and (A[i][0] == 0) and (A[i][1] == 0)) :
# Not possible
print("No")
return
# If multiple numbers are assigned
# to be placed in a single position
if ((A[i][0] in mp) and (mp[A[i][0]] != A[i][1])) :
# Not possible
print("No")
return
# Assign the digits to their
# respective positions
mp[A[i][0]] = A[i][1]
# Stores the result
ans = ""
# Traverse for all N digits
for i in range(N) :
# For the first position
if (N > 1 and i == 0) :
# If digit is assigned
# to the position
if (0 in mp) :
ans = ans + str(mp[0])
# Otherwise
else :
ans = ans + str(1)
else :
# Add it to answer
if i in mp :
ans = ans + str(mp[i])
else :
ans = ans + str(0)
print(ans)
# Driver code
N = 3
A = [ [ 0, 7 ], [ 2, 2 ], [ 0, 7 ] ]
find_num(N, A)
# This code is contributed by divyesh072019
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
public
class pair
{
public
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find the smallest integer
// satisfying the given conditions
static void find_num(int N, pair []A)
{
// Stores the digits at their
// respective positions
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < A.Length; i++)
{
// If first digit required
// to be placed is 0
if (N > 1 && A[i].first == 0 &&
A[i].second == 0)
{
// Not possible
Console.Write("No");
return;
}
// If multiple numbers are assigned
// to be placed in a single position
if (mp.ContainsKey(A[i].first) &&
mp[A[i].first] != A[i].second)
{
// Not possible
Console.Write("No");
return;
}
// Assign the digits to their
// respective positions
if(mp.ContainsKey(A[i].first))
mp[A[i].first] = A[i].second;
else
mp.Add(A[i].first, A[i].second);
}
// Stores the result
String ans = "";
// Traverse for all N digits
for(int i = 0; i < N; i++)
{
// For the first position
if (N > 1 && i == 0)
{
// If digit is assigned
// to the position
if (mp.ContainsKey(0))
{
ans += String.Join("", mp[0]);
}
// Otherwise
else
{
ans += String.Join("", 1);
}
}
else
{
// Add it to answer
if ( ! mp.ContainsKey(i) )
ans += String.Join("", 0);
else
ans += String.Join("", mp[i]);
}
}
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
pair []A = { new pair(0, 7),
new pair(2, 2),
new pair(0, 7)};
find_num(N, A);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the smallest integer
// satisfying the given conditions
function find_num(N, A){
// Stores the digits at their
// respective positions
let mp = new Map()
// Traverse the array
for(let i=0;i<A.length;i++){
// If first digit required
// to be placed is 0
if ((N > 1) && (A[i][0] == 0) && (A[i][1] == 0)){
// Not possible
document.write("No")
return
}
// If multiple numbers are assigned
// to be placed in a single position
if (mp.has(A[i][0])==true && (mp.get(A[i][0]) != A[i][1])){
// Not possible
document.write("No")
return
}
// Assign the digits to their
// respective positions
mp.set(A[i][0] , A[i][1])
}
// Stores the result
let ans = ""
// Traverse for all N digits
for(let i=0;i<N;i++){
// For the first position
if (N > 1 && i == 0){
// If digit is assigned
// to the position
if (mp.has(0))
ans = ans + mp.get(0).toString()
// Otherwise
else{
let temp = 1
ans = ans + temp.toString(1)
}
}
else{
// Add it to answer
if(mp.has(i))
ans = ans + mp.get(i).toString()
else{
let temp = 0
ans = ans + temp.toString()
}
}
}
document.write(ans)
}
// Driver code
let N = 3
let A = [ [ 0, 7 ], [ 2, 2 ], [ 0, 7 ] ]
find_num(N, A)
// This code is contributed by shinjanpatra
</script>
Producción:
702
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA