Dada una array arr[] y un entero K , la tarea es contar el par de índices (i, j) tal que i !=j y la concatenación de a[i] y a[j] es divisible por K .
Ejemplo:
Entrada: arr[] = [4, 5, 2], K = 2
Salida: 4
Explicación:
Todas las concatenaciones posibles son {45, 42, 54, 52, 24, 25}.
De estos, los números divisibles por 2 son {42, 52, 24, 54}.
Por lo tanto, la cuenta es 4.Entrada: arr[] =[45, 1, 10, 12, 11, 7], K = 11
Salida: 7
Enfoque ingenuo:
el enfoque más simple para resolver el problema es el siguiente:
- Itere sobre la array utilizando bucles anidados con las variables i y j .
- Concatenar arr[i] y arr[j] , para cada i != j , por la ecuación:
Concatenación de arr[i] y arr[j] = (arr[i] * 10 lenj ) + arr[j] , donde lenj es el número de dígitos en arr[j]
- Comprueba la divisibilidad del número concatenado por K .
Número concatenado es divisible por k si y solo si la suma de (arr[j] % k) y ((arr[i] * 10 lenj ) % k) es 0 mod k .
- Para todos esos pares de (arr[i], arr[j]) , aumente count .
- Imprime el valor final de count .
Complejidad de tiempo: O(N 2 *len(maxm), donde maxm denota el elemento máximo en la array y len(maxm) denota el conteo de dígitos de maxm.
Espacio Auxiliar: O(1)
Enfoque Eficiente:
Para optimizar el enfoque anterior, siga los pasos a continuación:
- Para aplicar la fórmula anterior, mantenga un Mapa para cada longitud de 1 a 10 .
- Guarda { len[a[i]] , a[i] % k } en el mapa.
- Para contar los pares, para cada j en [1, 10] , aumente el conteo por la frecuencia de (k – ((arr[i] * 10^j) % k)) almacenado en el Mapa como {j, k – ((arr[i] * 10^j) % k)} mapeo.
- Si se cuenta el par (arr[i], arr[i]) , disminuya el conteo en 1 .
- Después de completar el recorrido de la array, imprima el conteo final .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to count pairs
// of array elements which are
// divisible by K when concatenated
#include <bits/stdc++.h>
using namespace std;
map<int, int> rem[11];
// Function to calculate and return the
// count of pairs
int countPairs(vector<int> a, int n, int k)
{
vector<int> len(n);
// Compute power of 10 modulo k
vector<int> p(11);
p[0] = 1;
for (int i = 1; i <= 10; i++) {
p[i] = (p[i - 1] * 10) % k;
}
for (int i = 0; i < n; i++) {
int x = a[i];
// Calculate length of a[i]
while (x > 0) {
len[i]++;
x /= 10;
}
// Increase count of remainder
rem[len[i]][a[i] % k]++;
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= 10; j++) {
// Calculate (a[i]* 10^lenj) % k
int r = (a[i] * p[j]) % k;
// Calculate (k - (a[i]* 10^lenj)% k) % k
int xr = (k - r) % k;
// Increase answer by count
ans += rem[j][xr];
// If a pair (a[i], a[i]) is counted
if (len[i] == j
&& (r + a[i] % k) % k == 0)
ans--;
}
}
// Return the count of pairs
return ans;
}
// Driver Code
int main()
{
vector<int> a = { 4, 5, 2 };
int n = a.size(), k = 2;
cout << countPairs(a, n, k);
}
Java
// Java program to count pairs
// of array elements which are
// divisible by K when concatenated
import java.util.*;
import java.lang.*;
class GFG{
static int[][] rem = new int[11][11];
// Function to calculate and return the
// count of pairs
static int countPairs(int[] a, int n, int k)
{
int[] len = new int[n];
// Compute power of 10 modulo k
int[] p = new int[11];
p[0] = 1;
for(int i = 1; i <= 10; i++)
{
p[i] = (p[i - 1] * 10) % k;
}
for(int i = 0; i < n; i++)
{
int x = a[i];
// Calculate length of a[i]
while (x > 0)
{
len[i]++;
x /= 10;
}
// Increase count of remainder
rem[len[i]][a[i] % k]++;
}
int ans = 0;
for(int i = 0; i < n; i++)
{
for(int j = 1; j <= 10; j++)
{
// Calculate (a[i]* 10^lenj) % k
int r = (a[i] * p[j]) % k;
// Calculate (k - (a[i]* 10^lenj)% k) % k
int xr = (k - r) % k;
// Increase answer by count
ans += rem[j][xr];
// If a pair (a[i], a[i]) is counted
if (len[i] == j &&
(r + a[i] % k) % k == 0)
ans--;
}
}
// Return the count of pairs
return ans;
}
// Driver code
public static void main (String[] args)
{
int[] a = { 4, 5, 2 };
int n = a.length, k = 2;
System.out.println(countPairs(a, n, k));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to count pairs # of array elements which are # divisible by K when concatenated rem = [ [ 0 for x in range(11) ] for y in range(11) ] # Function to calculate and return the # count of pairs def countPairs(a, n, k): l = [0] * n # Compute power of 10 modulo k p = [0] * (11) p[0] = 1 for i in range(1, 11): p[i] = (p[i - 1] * 10) % k for i in range(n): x = a[i] # Calculate length of a[i] while (x > 0): l[i] += 1 x //= 10 # Increase count of remainder rem[l[i]][a[i] % k] += 1 ans = 0 for i in range(n): for j in range(1, 11): # Calculate (a[i]* 10^lenj) % k r = (a[i] * p[j]) % k # Calculate (k - (a[i]* 10^lenj)% k) % k xr = (k - r) % k # Increase answer by count ans += rem[j][xr] # If a pair (a[i], a[i]) is counted if (l[i] == j and (r + a[i] % k) % k == 0): ans -= 1 # Return the count of pairs return ans # Driver Code a = [ 4, 5, 2 ] n = len(a) k = 2 print(countPairs(a, n, k)) # This code is contributed by chitranayal
C#
// C# program to count pairs
// of array elements which are
// divisible by K when concatenated
using System;
class GFG{
static int [,]rem = new int[11, 11];
// Function to calculate and
// return the count of pairs
static int countPairs(int[] a,
int n, int k)
{
int[] len = new int[n];
// Compute power of 10 modulo k
int[] p = new int[11];
p[0] = 1;
for(int i = 1; i <= 10; i++)
{
p[i] = (p[i - 1] * 10) % k;
}
for(int i = 0; i < n; i++)
{
int x = a[i];
// Calculate length of a[i]
while (x > 0)
{
len[i]++;
x /= 10;
}
// Increase count of remainder
rem[len[i], a[i] % k]++;
}
int ans = 0;
for(int i = 0; i < n; i++)
{
for(int j = 1; j <= 10; j++)
{
// Calculate (a[i]* 10^lenj) % k
int r = (a[i] * p[j]) % k;
// Calculate (k - (a[i]* 10^lenj)% k) % k
int xr = (k - r) % k;
// Increase answer by count
ans += rem[j, xr];
// If a pair (a[i], a[i]) is counted
if (len[i] == j &&
(r + a[i] % k) % k == 0)
ans--;
}
}
// Return the count of pairs
return ans;
}
// Driver code
public static void Main(string[] args)
{
int[] a = {4, 5, 2};
int n = a.Length, k = 2;
Console.Write(countPairs(a, n, k));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program to count pairs
// of array elements which are
// divisible by K when concatenated
let rem = new Array(11);
// Loop to create 2D array using 1D array
for (var i = 0; i < rem.length; i++) {
rem[i] = new Array(2);
}
for (var i = 0; i < rem.length; i++) {
for (var j = 0; j < rem.length; j++) {
rem[i][j] = 0;
}
}
// Function to calculate and return the
// count of pairs
function countPairs(a, n, k)
{
let len = Array.from({length: n}, (_, i) => 0);
// Compute power of 10 modulo k
let p = Array.from({length: 11}, (_, i) => 0);
p[0] = 1;
for(let i = 1; i <= 10; i++)
{
p[i] = (p[i - 1] * 10) % k;
}
for(let i = 0; i < n; i++)
{
let x = a[i];
// Calculate length of a[i]
while (x > 0)
{
len[i]++;
x = Math.floor(x / 10);
}
// Increase count of remainder
rem[len[i]][a[i] % k]++;
}
let ans = 0;
for(let i = 0; i < n; i++)
{
for(let j = 1; j <= 10; j++)
{
// Calculate (a[i]* 10^lenj) % k
let r = (a[i] * p[j]) % k;
// Calculate (k - (a[i]* 10^lenj)% k) % k
let xr = (k - r) % k;
// Increase answer by count
ans += rem[j][xr];
// If a pair (a[i], a[i]) is counted
if (len[i] == j &&
(r + a[i] % k) % k == 0)
ans--;
}
}
// Return the count of pairs
return ans;
}
// Driver Code
let a = [ 4, 5, 2 ];
let n = a.length, k = 2;
document.write(countPairs(a, n, k));
</script>
Producción
4
Complejidad de tiempo: O(N * len(maxm))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA