Construya el número de N dígitos más pequeño posible colocando los dígitos en las posiciones especificadas por la array dada

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *