Dada una array que contiene digits[] , donde cada elemento es un entero de un solo dígito. La array puede contener duplicados. La tarea es encontrar todos los enteros únicos que cumplan con los requisitos dados:
- El número entero consiste en la concatenación de tres elementos de dígitos en cualquier orden arbitrario.
- El entero no tiene ceros a la izquierda.
Ejemplos:
Entrada: dígitos[] = {2, 1, 3, 0}
Salida: {102, 103, 120, 123, 130, 132, 201, 203, 210, 213, 230, 231, 301, 302, 310, 312, 320, 321}
Explicación: Los anteriores son los números de tres dígitos formados.Entrada: dígitos[] = {3, 7, 5}
Salida: [357, 375, 537, 573, 735, 753]
Enfoque: este problema se puede resolver utilizando el mapa de frecuencias . Encuentre el recuento de todos los elementos en una array de dígitos dada. Siga los pasos a continuación para resolver el problema dado.
- Compruebe todos los números entre 100 y 999 si pueden estar formados por los dígitos presentes en el vector de dígitos.
- Usa 2 mapas para lo mismo. Si se puede formar el número, entonces súmalo a la respuesta.
- Al final, devuelve la respuesta.
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 find all the unique
// 3 digit number that can be formed
// from the given digits
vector<int> find3DigitNumbers(vector<int>&
digits)
{
// Generating frequency map
// of the given digits
vector<int> count(10, 0);
for (auto& d : digits)
count[d]++;
vector<int> res;
for (int num = 100; num < 999; num++) {
// Generating frequency map
// of the current number
vector<int> currCount(10, 0);
int temp = num;
while (temp) {
currCount[temp % 10]++;
temp /= 10;
}
// Checking if the number
// can be generated or not
bool flag = true;
for (int i = 0; i < 10; i++) {
if (currCount[i] > count[i]) {
flag = false;
break;
}
}
if (flag) {
res.push_back(num);
}
}
return res;
}
// Function to print answer
void printAnswer(vector<int>& v1)
{
for (int i = 0; i < v1.size(); i++) {
cout << v1[i] << " ";
}
cout << endl;
}
// Driver code
int main()
{
vector<int> v1 = { 2, 1, 3, 0 };
// Function Call
vector<int> ans = find3DigitNumbers(v1);
// Printing answer
printAnswer(ans);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find all the unique
// 3 digit number that can be formed
// from the given digits
static void find3DigitNumbers(int digits[], List<Integer> res)
{
// Generating frequency map
// of the given digits
int count[] = new int[10];;
for (int i = 0; i < digits.length; i++)
count[digits[i]]++;
for (int num = 100; num < 999; num++) {
// Generating frequency map
// of the current number
int currCount[] = new int[10];
int temp = num;
while (temp > 0) {
currCount[temp % 10]++;
temp /= 10;
}
// Checking if the number
// can be generated or not
Boolean flag = true;
for (int i = 0; i < 10; i++) {
if (currCount[i] > count[i]) {
flag = false;
break;
}
}
if (flag == true) {
res.add(num);
}
}
}
// Function to print answer
static void printAnswer(List<Integer> res)
{
for(int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 1, 3, 0 };
List<Integer> ans=new ArrayList<Integer>();
// Function Call
find3DigitNumbers(arr, ans);
// Printing answer
printAnswer(ans);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach
# Function to find all the unique
# 3 digit number that can be formed
# from the given digits
def find3DigitNumbers(digits):
# Generating frequency map
# of the given digits
count = [0] * 10
for d in digits:
count[d] += 1
res = []
for num in range(100, 999):
# Generating frequency map
# of the current number
currCount = [0] * 10
temp = num
while (temp):
currCount[temp % 10] += 1
temp = temp // 10
# Checking if the number
# can be generated or not
flag = True
for i in range(10):
if (currCount[i] > count[i]):
flag = False
break
if (flag):
res.append(num)
return res
# Function to print answer
def printAnswer(v1):
for i in range(len(v1)):
print(v1[i], end=" ")
print('')
# Driver code
v1 = [2, 1, 3, 0]
# Function Call
ans = find3DigitNumbers(v1)
# Printing answer
printAnswer(ans)
# This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG {
// Function to find all the unique
// 3 digit number that can be formed
// from the given digits
static void find3DigitNumbers(int []digits, ArrayList res)
{
// Generating frequency map
// of the given digits
int []count = new int[10];;
for (int i = 0; i < digits.Length; i++)
count[digits[i]]++;
for (int num = 100; num < 999; num++) {
// Generating frequency map
// of the current number
int []currCount = new int[10];
int temp = num;
while (temp > 0) {
currCount[temp % 10]++;
temp /= 10;
}
// Checking if the number
// can be generated or not
bool flag = true;
for (int i = 0; i < 10; i++) {
if (currCount[i] > count[i]) {
flag = false;
break;
}
}
if (flag == true) {
res.Add(num);
}
}
}
// Function to print answer
static void printAnswer(ArrayList res)
{
for(int i = 0; i < res.Count; i++)
Console.Write(res[i] + " ");
}
// Driver code
public static void Main ()
{
int []arr = { 2, 1, 3, 0 };
ArrayList ans=new ArrayList();
// Function Call
find3DigitNumbers(arr, ans);
// Printing answer
printAnswer(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find all the unique
// 3 digit number that can be formed
// from the given digits
function find3DigitNumbers(
digits) {
// Generating frequency map
// of the given digits
let count = new Array(10).fill(0);
for (let d of digits)
count[d]++;
let res = [];
for (let num = 100; num < 999; num++) {
// Generating frequency map
// of the current number
let currCount = new Array(10).fill(0);
let temp = num;
while (temp) {
currCount[temp % 10]++;
temp = Math.floor(temp / 10);
}
// Checking if the number
// can be generated or not
let flag = true;
for (let i = 0; i < 10; i++) {
if (currCount[i] > count[i]) {
flag = false;
break;
}
}
if (flag) {
res.push(num);
}
}
return res;
}
// Function to print answer
function printAnswer(v1) {
for (let i = 0; i < v1.length; i++) {
document.write(v1[i] + " ");
}
document.write('<br>')
}
// Driver code
let v1 = [2, 1, 3, 0];
// Function Call
let ans = find3DigitNumbers(v1);
// Printing answer
printAnswer(ans);
// This code is contributed by Potta Lokesh
</script>
Producción
102 103 120 123 130 132 201 203 210 213 230 231 301 302 310 312 320 321
Complejidad temporal: O(1000)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sauarbhyadav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA