Dada una array arr[] de tamaño N , la tarea es contar los pares cuya concatenación de elementos es divisible por 3 y cada elemento de la array presente como máximo en un par.
Ejemplos:
Entrada: arr[] = { 5, 3, 2, 8, 7 }
Salida: 1
Explicación:
Los posibles pares cuya concatenación es divisible por 3 son { 27, 72, 78, 87 }, pero el elemento de array arr[4] estar presente en un par como máximo. Por lo tanto, la salida requerida es 1Entrada: arr[] = { 10, 6, 3, 7, 2 }
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y generar todos los pares posibles de la array dada . Para cada par comprobar si la concatenación de elementos del par es divisible por 3 o no. Si se determina que es verdadero, marque ambos elementos como falsos, de modo que ambos elementos del par no puedan estar presentes en más de un par.
A continuación se muestra la implementación del enfoque ingenuo:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count pairs whose concatenation
// is divisible by 3 and each element can be
// present in at most one pair
int countDivBy3InArray(int arr[], int N)
{
// Stores count pairs whose concatenation
// is divisible by 3 and each element can
// be present in at most one pair
int ans = 0;
// Check if an element present
// in any pair or not
bool taken[N];
memset(taken, false, sizeof(taken));
// Generate all possible pairs
for(int i = 0; i < N; i++)
{
// If the element already
// present in a pair
if (taken[i] == true)
{
continue;
}
for(int j = i + 1; j < N; j++)
{
// If the element already
// present in a pair
if (taken[j] == true)
{
continue;
}
// If concatenation of elements
// is divisible by 3
if (stoi(to_string(arr[i]) +
to_string(arr[j])) % 3 == 0 ||
stoi(to_string(arr[j]) +
to_string(arr[i])) % 3 == 0)
{
// Update ans
ans += 1;
// Mark i is True
taken[i] = true;
// Mark j is True
taken[j] = true;
}
}
}
return ans;
}
int main()
{
int arr[] = { 5, 3, 2, 8, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// To display the result
cout << countDivBy3InArray(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.Arrays;
class GFG{
// Function to count pairs whose concatenation
// is divisible by 3 and each element can be
// present in at most one pair
public static int countDivBy3InArray(int[] arr)
{
// Stores count pairs whose concatenation
// is divisible by 3 and each element can
// be present in at most one pair
int ans = 0;
// Check if an element present
// in any pair or not
boolean[] taken = new boolean[arr.length];
Arrays.fill(taken, false);
// Generate all possible pairs
for(int i = 0; i < arr.length; i++)
{
// If the element already
// present in a pair
if (taken[i] == true)
{
continue;
}
for(int j = i + 1; j < arr.length; j++)
{
// If the element already
// present in a pair
if (taken[j] == true)
{
continue;
}
// If concatenation of elements
// is divisible by 3
if (Integer.parseInt(
Integer.toString(arr[i]) +
Integer.toString(arr[j])) % 3 == 0 ||
Integer.parseInt(
Integer.toString(arr[j]) +
Integer.toString(arr[i])) % 3 == 0)
{
// Update ans
ans += 1;
// Mark i is True
taken[i] = true;
// Mark j is True
taken[j] = true;
}
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 5, 3, 2, 8, 7 };
// To display the result
System.out.println(countDivBy3InArray(arr));
}
}
// This code is contributed by aditya7409
Python3
# Python3 program to implement # the above approach # Function to count pairs whose concatenation is # divisible by 3 and each element can be present # in at most one pair def countDivBy3InArray(arr): # Stores count pairs whose concatenation is # divisible by 3 and each element can be present # in at most one pair ans = 0 # Check if an element present # in any pair or not taken = [False] * len(arr) # Generate all possible pairs for i in range(len(arr)): # If the element already # present in a pair if taken[i]: continue for j in range(i + 1, len(arr)): # If the element already # present in a pair if taken[j]: continue # If concatenation of elements # is divisible by 3 if (not int(str(arr[i])+str(arr[j])) % 3 or not int(str(arr[j])+str(arr[i])) % 3): # Update ans ans += 1 # Mark i is True taken[i] = True # Mark j is True taken[j] = True return ans # Driver Code arr = [5, 3, 2, 8, 7] # To display the result print(countDivBy3InArray(arr))
C#
// C# program to implement
// the above approach
using System;
public class GFG
{
// Function to count pairs whose concatenation
// is divisible by 3 and each element can be
// present in at most one pair
public static int countDivBy3InArray(int[] arr)
{
// Stores count pairs whose concatenation
// is divisible by 3 and each element can
// be present in at most one pair
int ans = 0;
// Check if an element present
// in any pair or not
bool[] taken = new bool[arr.Length];
// Generate all possible pairs
for(int i = 0; i < arr.Length; i++)
{
// If the element already
// present in a pair
if (taken[i] == true)
{
continue;
}
for(int j = i + 1; j < arr.Length; j++)
{
// If the element already
// present in a pair
if (taken[j] == true)
{
continue;
}
// If concatenation of elements
// is divisible by 3
if (Int32.Parse(
(arr[i]).ToString() +
(arr[j]).ToString()) % 3 == 0 ||
Int32.Parse(
(arr[j]).ToString() +
(arr[i]).ToString()) % 3 == 0)
{
// Update ans
ans += 1;
// Mark i is True
taken[i] = true;
// Mark j is True
taken[j] = true;
}
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 5, 3, 2, 8, 7 };
// To display the result
Console.WriteLine(countDivBy3InArray(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement the above approach
// Function to count pairs whose concatenation
// is divisible by 3 and each element can be
// present in at most one pair
function countDivBy3InArray(arr)
{
// Stores count pairs whose concatenation
// is divisible by 3 and each element can
// be present in at most one pair
let ans = 0;
// Check if an element present
// in any pair or not
let taken = new Array(arr.length);
taken.fill(false);
// Generate all possible pairs
for(let i = 0; i < arr.length; i++)
{
// If the element already
// present in a pair
if (taken[i] == true)
{
continue;
}
for(let j = i + 1; j < arr.length; j++)
{
// If the element already
// present in a pair
if (taken[j] == true)
{
continue;
}
// If concatenation of elements
// is divisible by 3
if (parseInt((arr[i]).toString() + (arr[j]).toString(), 10) % 3 == 0 ||
parseInt((arr[j]).toString() + (arr[i]).toString(), 10) % 3 == 0)
{
// Update ans
ans += 1;
// Mark i is True
taken[i] = true;
// Mark j is True
taken[j] = true;
}
}
}
return ans;
}
let arr = [ 5, 3, 2, 8, 7 ];
// To display the result
document.write(countDivBy3InArray(arr));
</script>
Producción:
1
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso del concepto de comprobar si un número es divisible por 3 o no . Siga los pasos a continuación para resolver el problema:
- Inicialice tres variables, digamos rem0 , rem1 y rem2 , para almacenar el recuento de elementos de array cuyo resto es 0 , 1 y 2 respectivamente cuando se divide por 3 .
- Atraviese la array y verifique las siguientes condiciones:
- Si arr[i] %3 == 0 , entonces actualice cnt0 += 1 .
- Si arr[i] %3 == 1 , actualice cnt1 += 1 .
- Si arr[i] %3 == 2 , actualice cnt2 += 1 .
- Finalmente, imprime el conteo de pares, es decir (rem0 / 2 + min(rem1, rem2)) .
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 count pairs whose concatenation is
// divisible by 3 and each element can be present
// in at most one pair
int countDiv(int arr[], int n)
{
// Stores count of array elements whose
// remainder is 0 by taking modulo by 3
int rem0 = 0;
// Stores count of array elements whose
// remainder is 1 by taking modulo by 3
int rem1 = 0;
// Stores count of array elements whose
// remainder is 2 by taking modulo by 3
int rem2 = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// Stores sum of digits
// of arr[i]
int digitSum = 0;
// Update digitSum
digitSum += arr[i];
// If remainder of digitSum by
// by taking modulo 3 is 0
if (digitSum % 3 == 0)
{
// Update rem0
rem0 += 1;
}
// If remainder of digitSum by
// by taking modulo 3 is 1
else if (digitSum % 3 == 1)
{
// Update rem1
rem1 += 1;
}
else
{
// Update rem2
rem2 += 1;
}
}
return (rem0 / 2 + min(rem1, rem2));
}
// Driver code
int main()
{
int arr[] = { 5, 3, 2, 8, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// To display the result
cout << (countDiv(arr, n));
}
// This code is contributed by ukasp
Java
// Java program to implement
// the above approach
public class GFG
{
// Function to count pairs whose concatenation is
// divisible by 3 and each element can be present
// in at most one pair
static int countDiv(int[] arr)
{
// Stores count of array elements whose
// remainder is 0 by taking modulo by 3
int rem0 = 0;
// Stores count of array elements whose
// remainder is 1 by taking modulo by 3
int rem1 = 0;
// Stores count of array elements whose
// remainder is 2 by taking modulo by 3
int rem2 = 0;
// Traverse the array
for(int i : arr)
{
// Stores sum of digits
// of arr[i]
int digitSum = 0;
// Update digitSum
digitSum += i;
// If remainder of digitSum by
// by taking modulo 3 is 0
if(digitSum % 3 == 0)
{
// Update rem0
rem0 += 1;
}
// If remainder of digitSum by
// by taking modulo 3 is 1
else if(digitSum % 3 == 1)
{
// Update rem1
rem1 += 1;
}
else
{
// Update rem2
rem2 += 1;
}
}
return (rem0 / 2 + Math.min(rem1, rem2));
}
// Driver code
public static void main(String[] args) {
int[] arr = {5, 3, 2, 8, 7};
// To display the result
System.out.println(countDiv(arr));
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 program to implement # the above approach # Function to count pairs whose concatenation is # divisible by 3 and each element can be present # in at most one pair def countDiv(arr): # Stores count of array elements whose # remainder is 0 by taking modulo by 3 rem0 = 0 # Stores count of array elements whose # remainder is 1 by taking modulo by 3 rem1 = 0 # Stores count of array elements whose # remainder is 2 by taking modulo by 3 rem2 = 0 # Traverse the array for i in arr: # Stores sum of digits # of arr[i] digitSum = 0 for digit in str(i): # Update digitSum digitSum += int(digit) # If remainder of digitSum by # by taking modulo 3 is 0 if digitSum % 3 == 0: # Update rem0 rem0 += 1 # If remainder of digitSum by # by taking modulo 3 is 1 elif digitSum % 3 == 1: # Update rem1 rem1 += 1 else: # Update rem2 rem2 += 1 return (rem0 // 2 + min(rem1, rem2)) # Driver Code arr = [5, 3, 2, 8, 7] # To display the result print(countDiv(arr))
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count pairs whose concatenation is
// divisible by 3 and each element can be present
// in at most one pair
static int countDiv(int[] arr)
{
// Stores count of array elements whose
// remainder is 0 by taking modulo by 3
int rem0 = 0;
// Stores count of array elements whose
// remainder is 1 by taking modulo by 3
int rem1 = 0;
// Stores count of array elements whose
// remainder is 2 by taking modulo by 3
int rem2 = 0;
// Traverse the array
foreach(int i in arr)
{
// Stores sum of digits
// of arr[i]
int digitSum = 0;
// Update digitSum
digitSum += i;
// If remainder of digitSum by
// by taking modulo 3 is 0
if(digitSum % 3 == 0)
{
// Update rem0
rem0 += 1;
}
// If remainder of digitSum by
// by taking modulo 3 is 1
else if(digitSum % 3 == 1)
{
// Update rem1
rem1 += 1;
}
else
{
// Update rem2
rem2 += 1;
}
}
return (rem0 / 2 + Math.Min(rem1, rem2));
}
// Driver code
static void Main() {
int[] arr = {5, 3, 2, 8, 7};
// To display the result
Console.Write(countDiv(arr));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count pairs
// whose concatenation is
// divisible by 3 and each
// element can be present
// in at most one pair
function countDiv(arr)
{
// Stores count of array elements whose
// remainder is 0 by taking modulo by 3
let rem0 = 0;
// Stores count of array elements whose
// remainder is 1 by taking modulo by 3
let rem1 = 0;
// Stores count of array elements whose
// remainder is 2 by taking modulo by 3
let rem2 = 0;
// Traverse the array
for(let i = 0; i < arr.length; i++)
{
// Stores sum of digits
// of arr[i]
let digitSum = 0;
// Update digitSum
digitSum += arr[i];
// If remainder of digitSum by
// by taking modulo 3 is 0
if(digitSum % 3 == 0)
{
// Update rem0
rem0 += 1;
}
// If remainder of digitSum by
// by taking modulo 3 is 1
else if(digitSum % 3 == 1)
{
// Update rem1
rem1 += 1;
}
else
{
// Update rem2
rem2 += 1;
}
}
return (parseInt(rem0 / 2, 10) +
Math.min(rem1, rem2));
}
let arr = [5, 3, 2, 8, 7];
// To display the result
document.write(countDiv(arr));
</script>
Producción:
1
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O()
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA