Dada una array arr[] de tamaño N y un entero X , la tarea es encontrar el número de pares ordenados (i, j) tales que i != j y X es la concatenación de los números arr[i] y arr[ j]
Ejemplos :
Entrada: N = 4, arr[] = {1, 212, 12, 12}, X = 1212
Salida: 3
Explicación: X = 1212 se puede obtener concatenando:
- numeros[0] = 1 con numeros[1] = 212
- numeros[2] = 12 con numeros[3] = 12
- números[3] = 12 con números[2] = 12
- Por lo tanto, el número de pares ordenados posibles es 3
Entrada: N = 3, arr[] = {11, 11, 110}, X = 11011
Salida: 2
Enfoque: la tarea se puede resolver usando un hashmap Siga los pasos a continuación para resolver el problema
- Almacene las longitudes de todos los números en un vector.
- Itere sobre la array de números dada y verifique si se puede obtener X del número. Si es así, aumente la cuenta para verificar con cuántos números el número actual puede formar un par.
- Aumenta el valor del número actual en el mapa.
- Borre el mapa y repita los mismos pasos en la array de números dada desde atrás .
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 the number of possible
// ordered pairs
long long countPairs(int n, int x, vector<int> v)
{
int power[10]
= { 1, 10, 100,
1000, 10000, 100000,
1000000, 10000000,
100000000,
1000000000 };
// Stores the count of digits of each number
vector<int> len;
long long count = 0;
for (int i = 0; i < n; i++)
len.push_back(log10(v[i]) + 1);
unordered_map<int, int> mp;
mp[v[0]]++;
// Iterating from the start
for (int i = 1; i < n; i++) {
if (x % power[len[i]] == v[i])
count += mp[x / power[len[i]]];
cout<<"count = "<<count<<endl;
mp[v[i]]++;
}
mp.clear();
mp[v[n - 1]]++;
// Iterating from the end
for (int i = n - 2; i >= 0; i--) {
if (x % power[len[i]] == v[i])
count += mp[x / power[len[i]]];
cout<<"c = "<<count<<endl;
mp[v[i]]++;
}
return count;
}
// Driver Code
int main()
{
int N = 4;
int X = 1212;
vector<int> numbers = { 1, 212, 12, 12 };
long long ans = countPairs(N, X, numbers);
cout << ans << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the number of possible
// ordered pairs
static long countPairs(int n, int x, int[] v) {
int power[] = { 1, 10, 100, 1000, 10000, 100000,
1000000, 10000000, 100000000, 1000000000 };
// Stores the count of digits of each number
Vector<Integer> len = new Vector<Integer>();
long count = 0;
for (int i = 0; i < n; i++)
len.add((int) (Math.log10(v[i]) + 1));
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
if (mp.containsKey(v[0])) {
mp.put(v[0], mp.get(v[0]) + 1);
} else {
mp.put(v[0], 1);
}
// Iterating from the start
for (int i = 1; i < n; i++) {
if (x % power[len.get(i)] == v[i]&&mp.containsKey(x / power[len.get(i)]))
count += mp.get(x / power[len.get(i)]);
System.out.println("count = " + count);
if (mp.containsKey(v[i])) {
mp.put(v[i], mp.get(v[i]) + 1);
} else {
mp.put(v[i], 1);
}
}
mp.clear();
if (mp.containsKey(v[n - 1])) {
mp.put(v[n - 1], mp.get(v[n - 1]) + 1);
} else {
mp.put(v[n - 1], 1);
}
// Iterating from the end
for (int i = n - 2; i >= 0; i--) {
if (x % power[len.get(i)] == v[i]&&mp.containsKey(x / power[len.get(i)]))
count += mp.get(x / power[len.get(i)]);
System.out.println("c = " + count);
if (mp.containsKey(v[i])) {
mp.put(v[i], mp.get(v[i]) + 1);
} else {
mp.put(v[i], 1);
}
}
return count;
}
// Driver Code
public static void main(String[] args) {
int N = 4;
int X = 1212;
int[] numbers = { 1, 212, 12, 12 };
long ans = countPairs(N, X, numbers);
System.out.print(ans + "\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach from collections import defaultdict import math # Function to find the number of possible # ordered pairs def countPairs(n, x, v): power = [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000] # Stores the count of digits of each number length = [] count = 0 for i in range(n): length.append(int(math.log10(v[i])) + 1) mp = defaultdict(int) mp[v[0]] += 1 # Iterating from the start for i in range(1, n): if (x % power[length[i]] == v[i]): count += mp[x // power[length[i]]] mp[v[i]] += 1 mp.clear() mp[v[n - 1]] += 1 # Iterating from the end for i in range(n - 2, -1, -1): if (x % power[length[i]] == v[i]): count += mp[x // power[length[i]]] mp[v[i]] += 1 return count # Driver Code if __name__ == "__main__": N = 4 X = 1212 numbers = [1, 212, 12, 12] ans = countPairs(N, X, numbers) print(ans) # This code is contributed by ukasp.
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to find the number of possible
// ordered pairs
static long countPairs(int n, int x, int[] v) {
int[] power = new int[]{ 1, 10, 100, 1000, 10000, 100000,
1000000, 10000000, 100000000, 1000000000 };
// Stores the count of digits of each number
List<int> len = new List<int>();
long count = 0;
for (int i = 0 ; i < n ; i++){
len.Add((int)(Math.Log10(v[i]) + 1));
}
Dictionary<int, int> mp = new Dictionary<int, int>();
if (mp.ContainsKey(v[0])) {
mp[v[0]]+=1;
}else {
mp.Add(v[0], 1);
}
// Iterating from the start
for (int i = 1; i < n; i++) {
if (x % power[len[i]] == v[i] && mp.ContainsKey(x / power[len[i]])){
count += mp[x / power[len[i]]];
}
// Console.WriteLine("count = " + count);
if (mp.ContainsKey(v[i])) {
mp[v[i]]+=1;
} else {
mp.Add(v[i], 1);
}
}
mp.Clear();
if (mp.ContainsKey(v[n - 1])) {
mp[v[n - 1]] += 1;
} else {
mp.Add(v[n - 1], 1);
}
// Iterating from the end
for (int i = n - 2; i >= 0; i--) {
if (x % power[len[i]] == v[i] && mp.ContainsKey(x / power[len[i]])){
count += mp[x / power[len[i]]];
}
// Console.WriteLine("c = " + count);
if (mp.ContainsKey(v[i])) {
mp[v[i]] += 1;
} else {
mp.Add(v[i], 1);
}
}
return count;
}
public static void Main(string[] args){
int N = 4;
int X = 1212;
int[] numbers = new int[]{ 1, 212, 12, 12 };
long ans = countPairs(N, X, numbers);
Console.WriteLine(ans);
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the number of possible
// ordered pairs
function countPairs(n, x, v) {
let power = [1, 10, 100,
1000, 10000, 100000,
1000000, 10000000,
100000000,
1000000000];
// Stores the count of digits of each number
let len = [];
let count = 0;
for (let i = 0; i < n; i++)
len.push(Math.floor(Math.log10(v[i])) + 1);
let mp = new Map();
mp.set(v[0], 1);
// Iterating from the start
for (let i = 1; i < n; i++) {
if (x % power[len[i]] == v[i] && mp.has(Math.floor(x / power[len[i]])))
count += mp.get(Math.floor(x / power[len[i]]));
if (mp.has(v[i])) {
mp.set(v[i], mp.get(v[i]) + 1)
}
else {
mp.set(v[i], 1)
}
}
mp = new Map();
mp.set(v[n - 1], 1);
// Iterating from the end
for (let i = n - 2; i >= 0; i--) {
if (x % power[len[i]] == v[i] && mp.has(Math.floor(x / power[len[i]])))
count += mp.get(Math.floor(x / power[len[i]]));
if (mp.has(v[i])) {
mp.set(v[i], mp.get(v[i]) + 1)
}
else {
mp.set(v[i], 1)
}
}
return count;
}
// Driver Code
let N = 4;
let X = 1212;
let numbers = [1, 212, 12, 12];
let ans = countPairs(N, X, numbers);
document.write(ans + '<br>')
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal : O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por harshalkhond y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA