Dada una array de N números. Averigüe el número de pares i y j tales que i < j y A i y A j tienen al menos un dígito común (por ejemplo, (11, 19) tienen 1 dígito común pero (36, 48) no tienen dígito común)
Ejemplos:
Entrada: A[] = { 10, 12, 24 }
Salida: 2
Explicación: Dos pares válidos son (10, 12) y (12, 24) que tienen al menos un dígito común
Método 1 (Fuerza bruta) Un enfoque ingenuo para resolver este problema es ejecutar dos bucles anidados y considerar todos los pares posibles. Podemos verificar si los dos números tienen al menos un dígito común, extrayendo cada dígito del primer número e intentando encontrarlo en los dígitos extraídos del segundo número. La tarea sería mucho más fácil, simplemente los convertimos en strings.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP Program to count pairs in an array
// with some common digit
#include <bits/stdc++.h>
using namespace std;
// Returns true if the pair is valid,
// otherwise false
bool checkValidPair(int num1, int num2)
{
// converting integers to strings
string s1 = to_string(num1);
string s2 = to_string(num2);
// Iterate over the strings and check
// if a character in first string is also
// present in second string, return true
for (int i = 0; i < s1.size(); i++)
for (int j = 0; j < s2.size(); j++)
if (s1[i] == s2[j])
return true;
// No common digit found
return false;
}
// Returns the number of valid pairs
int countPairs(int arr[], int n)
{
int numberOfPairs = 0;
// Iterate over all possible pairs
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (checkValidPair(arr[i], arr[j]))
numberOfPairs++;
return numberOfPairs;
}
// Driver Code to test above functions
int main()
{
int arr[] = { 10, 12, 24 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countPairs(arr, n) << endl;
return 0;
}
Java
// Java Program to count
// pairs in an array
// with some common digit
import java.io.*;
class GFG
{
// Returns true if the pair
// is valid, otherwise false
static boolean checkValidPair(int num1,
int num2)
{
// converting integers
// to strings
String s1 = Integer.toString(num1);
String s2 = Integer.toString(num2);
// Iterate over the strings
// and check if a character
// in first string is also
// present in second string,
// return true
for (int i = 0; i < s1.length(); i++)
for (int j = 0; j < s2.length(); j++)
if (s1.charAt(i) == s2.charAt(j))
return true;
// No common
// digit found
return false;
}
// Returns the number
// of valid pairs
static int countPairs(int []arr, int n)
{
int numberOfPairs = 0;
// Iterate over all
// possible pairs
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (checkValidPair(arr[i], arr[j]))
numberOfPairs++;
return numberOfPairs;
}
// Driver Code
public static void main(String args[])
{
int []arr = new int[]{ 10, 12, 24 };
int n = arr.length;
System.out.print(countPairs(arr, n));
}
}
// This code is contributed
// by manish shaw.
Python3
# Python3 Program to count pairs in # an array with some common digit # Returns true if the pair is # valid, otherwise false def checkValidPair(num1, num2) : # converting integers to strings s1 = str(num1) s2 = str(num2) # Iterate over the strings and check if # a character in first string is also # present in second string, return true for i in range(len(s1)) : for j in range(len(s2)) : if (s1[i] == s2[j]) : return True; # No common digit found return False; # Returns the number of valid pairs def countPairs(arr, n) : numberOfPairs = 0 # Iterate over all possible pairs for i in range(n) : for j in range(i + 1, n) : if (checkValidPair(arr[i], arr[j])) : numberOfPairs += 1 return numberOfPairs # Driver Code if __name__ == "__main__" : arr = [ 10, 12, 24 ] n = len(arr) print(countPairs(arr, n)) # This code is contributed by Ryuga
C#
// C# Program to count pairs in an array
// with some common digit
using System;
class GFG {
// Returns true if the pair is valid,
// otherwise false
static bool checkValidPair(int num1, int num2)
{
// converting integers to strings
string s1 = num1.ToString();
string s2 = num2.ToString();
// Iterate over the strings and check
// if a character in first string is also
// present in second string, return true
for (int i = 0; i < s1.Length; i++)
for (int j = 0; j < s2.Length; j++)
if (s1[i] == s2[j])
return true;
// No common digit found
return false;
}
// Returns the number of valid pairs
static int countPairs(int []arr, int n)
{
int numberOfPairs = 0;
// Iterate over all possible pairs
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (checkValidPair(arr[i], arr[j]))
numberOfPairs++;
return numberOfPairs;
}
// Driver Code to test above functions
static void Main()
{
int []arr = new int[]{ 10, 12, 24 };
int n = arr.Length;
Console.WriteLine(countPairs(arr, n));
}
}
// This code is contributed by manish shaw.
PHP
<?php
// PHP Program to count pairs in an array
// with some common digit
// Returns true if the pair is valid,
// otherwise false
function checkValidPair($num1, $num2)
{
// converting integers to strings
$s1 = (string)$num1;
$s2 = (string)$num2;
// Iterate over the strings and check
// if a character in first string is also
// present in second string, return true
for ($i = 0; $i < strlen($s1); $i++)
for ($j = 0; $j < strlen($s2); $j++)
if ($s1[$i] == $s2[$j])
return true;
// No common digit found
return false;
}
// Returns the number of valid pairs
function countPairs(&$arr, $n)
{
$numberOfPairs = 0;
// Iterate over all possible pairs
for ($i = 0; $i < $n; $i++)
for ($j = $i + 1; $j < $n; $j++)
if (checkValidPair($arr[$i],
$arr[$j]))
$numberOfPairs++;
return $numberOfPairs;
}
// Driver Code
$arr = array(10, 12, 24 );
$n = sizeof($arr);
echo (countPairs($arr, $n));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript Program to count pairs in an array
// with some common digit
// Returns true if the pair is valid,
// otherwise false
function checkValidPair(num1, num2)
{
// converting integers to strings
var s1 = num1.toString();
var s2 = num2.toString();
var i,j;
// Iterate over the strings and check
// if a character in first string is also
// present in second string, return true
for(i = 0; i < s1.length; i++)
for(j = 0; j < s2.length; j++)
if (s1[i] == s2[j])
return true;
// No common digit found
return false;
}
// Returns the number of valid pairs
function countPairs(arr, n)
{
var numberOfPairs = 0;
// Iterate over all possible pairs
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
if(checkValidPair(arr[i], arr[j]))
numberOfPairs++;
return numberOfPairs;
}
// Driver Code to test above functions
var arr = [10, 12, 24];
var n = arr.length;;
document.write(countPairs(arr, n));
</script>
Producción
2
Complejidad de tiempo: O(N 2 ) donde N es el tamaño de la array.
Método 2 (Enmascaramiento de bits): un enfoque eficiente para resolver este problema es crear una máscara de bits para cada dígito presente en un número en particular. Así, para que cada dígito esté presente en un número si tenemos una máscara de 1111111111.
Digits - 0 1 2 3 4 5 6 7 8 9
| | | | | | | | | |
Mask - 1 1 1 1 1 1 1 1 1 1
Here 1 denotes that the corresponding ith digit is set.
For e.g. 1235 can be represented as
Digits - 0 1 2 3 4 5 6 7 8 9
| | | | | | | | | |
Mask for 1235 - 0 1 1 1 0 1 0 0 0 0
Ahora solo tenemos que extraer cada dígito de un número y establecer el bit correspondiente (1 << i -ésimo dígito) y almacenar el número completo como una máscara. Un análisis cuidadoso sugiere que el valor máximo de la máscara es 1023 en decimal (que contiene todos los dígitos del 0 al 9). Dado que el mismo conjunto de dígitos puede existir en más de un número, necesitamos mantener una array de frecuencias para almacenar el recuento del valor de la máscara.
Deje que las frecuencias de dos máscaras i y j sean freq i y freq j respectivamente,
si (i Y j) devuelven verdadero, significa que la i -ésima y la j -ésima máscara contienen al menos un bit conjunto común que a su vez implica que los números de los que provienen estas máscaras han sido construidos también contienen un dígito común
entonces,
incremente la respuesta
ans += freq i * freq j [ if i != j ]
ans += (freq i * (freq i – 1)) / 2 [ if j == i ]
A continuación se muestra la implementación de este enfoque eficiente:
C++
// CPP Program to count pairs in an array with
// some common digit
#include <bits/stdc++.h>
using namespace std;
// This function calculates the mask frequencies
// for every present in the array
void calculateMaskFrequencies(int arr[], int n,
unordered_map<int, int>& freq)
{
// Iterate over the array
for (int i = 0; i < n; i++) {
int num = arr[i];
// Creating an empty mask
int mask = 0;
// Extracting every digit of the number
// and updating corresponding bit in the
// mask
while (num > 0) {
mask = mask | (1 << (num % 10));
num /= 10;
}
// Update the frequency array
freq[mask]++;
}
}
// Function return the number of valid pairs
int countPairs(int arr[], int n)
{
// Store the mask frequencies
unordered_map<int, int> freq;
calculateMaskFrequencies(arr, n, freq);
long long int numberOfPairs = 0;
// Considering every possible pair of masks
// and calculate pairs according to their
// frequencies
for (int i = 0; i < 1024; i++) {
numberOfPairs += (freq[i] * (freq[i] - 1)) / 2;
for (int j = i + 1; j < 1024; j++) {
// if it contains a common digit
if (i & j)
numberOfPairs += (freq[i] * freq[j]);
}
}
return numberOfPairs;
}
// Driver Code to test above functions
int main()
{
int arr[] = { 10, 12, 24 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countPairs(arr, n) << endl;
return 0;
}
Java
// Java Program to count pairs in an array with
// some common digit
import java.io.*;
import java.util.*;
class GFG
{
// Store the mask frequencies
public static Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
// This function calculates the mask frequencies
// for every present in the array
public static void calculateMaskFrequencies(int[] arr,int n)
{
// Iterate over the array
for(int i = 0; i < n; i++)
{
int num = arr[i];
// Creating an empty mask
int mask = 0;
// Extracting every digit of the number
// and updating corresponding bit in the
// mask
while(num > 0)
{
mask = mask | (1 << (num % 10));
num /= 10;
}
// Update the frequency array
if(freq.containsKey(mask))
{
freq.put(new Integer(mask), freq.get(mask) + 1);
}
else
{
freq.put(new Integer(mask), 1);
}
}
}
// Function return the number of valid pairs
public static int countPairs(int[] arr, int n)
{
calculateMaskFrequencies(arr, n);
int numberOfPairs = 0;
// Considering every possible pair of masks
// and calculate pairs according to their
// frequencies
for(int i = 0; i < 1024; i++)
{
int x = 0;
if(freq.containsKey(i))
{
x = freq.get(i);
}
numberOfPairs += ((x) * (x - 1)) / 2;
for(int j = i + 1; j < 1024; j++)
{
int y = 0;
// if it contains a common digit
if((i & j) != 0)
{
if(freq.containsKey(j))
{
y = freq.get(j);
}
numberOfPairs += x * y;
}
}
}
return numberOfPairs;
}
// Driver Code
public static void main (String[] args)
{
int[] arr = {10, 12, 24};
int n = arr.length;
System.out.println(countPairs(arr, n));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 Program to count pairs in an array # with some common digit # This function calculates the mask frequencies # for every present in the array def calculateMaskFrequencies(arr, n, freq): # Iterate over the array for i in range(n): num = arr[i] # Creating an empty mask mask = 0 # Extracting every digit of the number # and updating corresponding bit in the # mask while (num > 0): mask = mask | (1 << (num % 10)) num //= 10 # Update the frequency array freq[mask] = freq.get(mask, 0) + 1 # Function return the number of valid pairs def countPairs(arr, n): # Store the mask frequencies freq = dict() calculateMaskFrequencies(arr, n, freq) numberOfPairs = 0 # Considering every possible pair of masks # and calculate pairs according to their # frequencies for i in range(1024): x = 0 if i in freq.keys(): x = freq[i] numberOfPairs += (x * (x - 1)) // 2 for j in range(i + 1, 1024): y = 0 if j in freq.keys(): y = freq[j] # if it contains a common digit if (i & j): numberOfPairs += (x * y) return numberOfPairs # Driver Code arr = [10, 12, 24] n = len(arr) print(countPairs(arr, n)) # This code is contributed by mohit kumar
C#
// C# Program to count pairs in an array with
// some common digit
using System;
using System.Collections.Generic;
public class GFG
{
// Store the mask frequencies
static Dictionary<int, int> freq = new Dictionary<int, int>();
// This function calculates the mask frequencies
// for every present in the array
public static void calculateMaskFrequencies(int[] arr,int n)
{
// Iterate over the array
for(int i = 0; i < n; i++)
{
int num = arr[i];
// Creating an empty mask
int mask = 0;
// Extracting every digit of the number
// and updating corresponding bit in the
// mask
while(num > 0)
{
mask = mask | (1 << (num % 10));
num /= 10;
}
// Update the frequency array
if(freq.ContainsKey(mask))
{
freq[mask]++;
}
else
{
freq.Add(mask, 1);
}
}
}
public static int countPairs(int[] arr, int n)
{
calculateMaskFrequencies(arr, n);
int numberOfPairs = 0;
// Considering every possible pair of masks
// and calculate pairs according to their
// frequencies
for(int i = 0; i < 1024; i++)
{
int x = 0;
if(freq.ContainsKey(i))
{
x = freq[i];
}
numberOfPairs += ((x) * (x - 1)) / 2;
for(int j = i + 1; j < 1024; j++)
{
int y = 0;
// if it contains a common digit
if((i & j) != 0)
{
if(freq.ContainsKey(j))
{
y = freq[j];
}
numberOfPairs += x * y;
}
}
}
return numberOfPairs;
}
// Driver Code
static public void Main ()
{
int[] arr = {10, 12, 24};
int n = arr.Length;
Console.WriteLine(countPairs(arr, n));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript Program to count pairs in an array with
// some common digit
// Store the mask frequencies
let freq = new Map();
// This function calculates the mask frequencies
// for every present in the array
function calculateMaskFrequencies(arr,n)
{
// Iterate over the array
for(let i = 0; i < n; i++)
{
let num = arr[i];
// Creating an empty mask
let mask = 0;
// Extracting every digit of the number
// and updating corresponding bit in the
// mask
while(num > 0)
{
mask = mask | (1 << (num % 10));
num = Math.floor(num/10);
}
// Update the frequency array
if(freq.has(mask))
{
freq.set((mask), freq.get(mask) + 1);
}
else
{
freq.set((mask), 1);
}
}
}
// Function return the number of valid pairs
function countPairs(arr,n)
{
calculateMaskFrequencies(arr, n);
let numberOfPairs = 0;
// Considering every possible pair of masks
// and calculate pairs according to their
// frequencies
for(let i = 0; i < 1024; i++)
{
let x = 0;
if(freq.has(i))
{
x = freq.get(i);
}
numberOfPairs += Math.floor((x) * (x - 1)) / 2;
for(let j = i + 1; j < 1024; j++)
{
let y = 0;
// if it contains a common digit
if((i & j) != 0)
{
if(freq.has(j))
{
y = freq.get(j);
}
numberOfPairs += x * y;
}
}
}
return numberOfPairs;
}
// Driver Code
let arr=[10, 12, 24];
let n = arr.length;
document.write(countPairs(arr, n));
// This code is contributed by unknown2108
</script>
Producción
2
Complejidad de tiempo: O(N + 1024 * 1024), donde N es el tamaño de la array.
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA