Dada una array de enteros arr[], encuentre el número de pares reciclados en la array. Un par reciclado de dos números {a, b} tiene las siguientes propiedades:
- A debe ser más pequeño que B.
- El número de dígitos debe ser el mismo.
- Al rotar A cualquier número de veces en una dirección, deberíamos obtener B.
Ejemplos:
Input : arr[] = {32, 42, 13, 23, 9, 5, 31}
Output : 2
Explanation : Since there are two pairs {13, 31} and {23, 32}.
By rotating 13 for first time, output is 31 and by rotating 23 once output is 32.
Both of these pairs satisfy our criteria.
Input : arr[] = {1212, 2121}
Output : 1
Explanation : Since there are two pairs {1212, 2121}. By rotating 1212
for first time, output is 2121. This pair satisfies our criteria.
Note that if rotation id done further, rotating 1212 again output is 1212
which is given number and 2121 which has been already counted.
So discard both of these results.
A continuación se muestra el algoritmo paso a paso para resolver el problema anterior:
- Ordenar la array.
- Cree una nueva array ‘temp’ de tamaño n donde n es la longitud de la array original.
- Elimine los duplicados de la array copiando valores únicos en la nueva array ‘temp’.
- Encuentre la cantidad de elementos copiados de la array original y deje que este número sea el tamaño de la array.
- Cree un HashSet para almacenar solo rotaciones únicas del número actual.
- Inicializar un contador con valor = 0.
- Atraviese ‘temp’ y para cada número siga los siguientes pasos:
- Encuentra el número de dígitos. Sea ‘d1’.
- Gire el número d-1 veces y almacene cada número formado por cada rotación en un HashSet.
- Si se encuentra un número formado en HashSet, ignórelo.
- Para cada número rotado, realice una búsqueda binaria de su presencia en el resto de la array.
- Si está presente, incrementa el contador.
C++
// C++ code for Recycled Pairs in array.
#include<bits/stdc++.h>
using namespace std;
// Function to find recycled pairs
int recycledPairs(int a[], int n)
{
int count = 0;
// Sorting array
sort(a, a + n);
// Removing duplicates by creating new array temp.
int temp[n];
memset(temp, -1, n);
int j = 0;
for (int i = 0; i < n - 1; i++)
if (a[i] != a[i + 1])
temp[j++] = a[i];
temp[j++] = a[n - 1];
int size = n;
// Finding number of locations in temp
// which are occupied from copying.
for (int i = n - 1; i >= 0; i--)
if (temp[i] != -1)
{
size = i;
break;
}
// Hashset to store new Rotations
set<int>hs;
for (int i = 0; i < size + 1; i++)
{
// Clearing hashset for each number in temp.
hs.clear();
int x = temp[i];
// Finding number of digits of taken number
int d1 = (int)log10(temp[i]) + 1;
int f = (int)pow(10, d1 - 1);
for (j = 1; j <= d1 - 1; j++)
{
// Remainder
int r = x % 10;
// Quotient
int q = x / 10;
// Forming new number by rotating.
x = r * f + q;
// Number of digits of newly formed rotated number
// to avoid duplicate numbers.
int d2 = (int)log10(x) + 1;
set<int>::iterator it = hs.find(x);
// Inserting formed rotated number to set s
if (it == hs.end())
{
hs.insert(x);
// Checking for number of digits of new number.
if ((d1 == d2))
{
// Searching for the formed element in rest of array.
int position = lower_bound(temp + i,
temp + size + 1 , x)-(temp + i + 1);
// If position found
if(position >= 0)
{
// Increment counter.
count++;
}
}
}
}
}
// Return counter
return count;
}
// Driver function
int main()
{
int a[] = { 32, 42, 13, 23, 9, 5, 31 };
int n = sizeof(a)/sizeof(a[0]);
int result = recycledPairs(a,n);
cout << (result);
return 0;
}
// This code is contributed by Rajput-Ji
Java
// Java code for Recycled Pairs in array.
import java.util.*;
class GFG {
// Function to find recycled pairs
static int recycledPairs(int[] a)
{
int count = 0;
// Sorting array
Arrays.sort(a);
int n = a.length;
// Removing duplicates by creating new array temp.
int[] temp = new int[n];
Arrays.fill(temp, -1);
int j = 0;
for (int i = 0; i < n - 1; i++)
if (a[i] != a[i + 1])
temp[j++] = a[i];
temp[j++] = a[n - 1];
int size = n;
// Finding number of locations in temp which are occupied from copying.
for (int i = n - 1; i >= 0; i--)
if (temp[i] != -1) {
size = i;
break;
}
// Hashset to store new Rotations
HashSet<Integer> hs = new HashSet<Integer>();
for (int i = 0; i < size + 1; i++) {
// Clearing hashset for each number in temp.
hs.clear();
int x = temp[i];
// Finding number of digits of taken number
int d1 = (int)Math.log10(temp[i]) + 1;
int f = (int)Math.pow(10, d1 - 1);
for (j = 1; j <= d1 - 1; j++) {
// Remainder
int r = x % 10;
// Quotient
int q = x / 10;
// Forming new number by rotating.
x = r * f + q;
// Number of digits of newly formed rotated number
// to avoid duplicate numbers.
int d2 = (int)Math.log10(x) + 1;
// Inserting formed rotated number to set s
if (!hs.contains(x)) {
hs.add(x);
// Checking for number of digits of new number.
if ((d1 == d2))
{
// Searching for the formed element in rest of array.
int position = Arrays.binarySearch(temp, i + 1, size + 1, x);
// If position found
if(position >= 0)
{
// Increment counter.
count++;
}
}
}
}
}
// Return counter
return count;
}
// Driver function
public static void main(String[] args)
{
int a[] = { 32, 42, 13, 23, 9, 5, 31 };
int result = recycledPairs(a);
System.out.println(result);
}
}
C#
// C# code for Recycled Pairs in array.
using System;
using System.Collections.Generic;
class GFG
{
// Function to find recycled pairs
static int recycledPairs(int[] a)
{
int count = 0;
// Sorting array
Array.Sort(a);
int n = a.Length;
// Removing duplicates by
// creating new array temp.
int[] temp = new int[n];
for (int i = 0; i < n; i++)
temp[i] = -1;
int j = 0;
for (int i = 0; i < n - 1; i++)
if (a[i] != a[i + 1])
temp[j++] = a[i];
temp[j++] = a[n - 1];
int size = n;
// Finding number of locations in temp
// which are occupied from copying.
for (int i = n - 1; i >= 0; i--)
if (temp[i] != -1)
{
size = i;
break;
}
// Hashset to store new Rotations
HashSet<int> hs = new HashSet<int>();
for (int i = 0; i < size + 1; i++)
{
// Clearing hashset for each number in temp.
hs.Clear();
int x = temp[i];
// Finding number of digits of taken number
int d1 = (int)Math.Log10(temp[i]) + 1;
int f = (int)Math.Pow(10, d1 - 1);
for (j = 1; j <= d1 - 1; j++)
{
// Remainder
int r = x % 10;
// Quotient
int q = x / 10;
// Forming new number by rotating.
x = r * f + q;
// Number of digits of newly formed rotated number
// to avoid duplicate numbers.
int d2 = (int)Math.Log10(x) + 1;
// Inserting formed rotated number to set s
if (!hs.Contains(x))
{
hs.Add(x);
// Checking for number of digits of new number.
if ((d1 == d2))
{
// Searching for the formed element in rest of array.
int position = Array.BinarySearch(temp, i + 1,
size - i, x);
// If position found
if(position >= 0)
{
// Increment counter.
count++;
}
}
}
}
}
// Return counter
return count;
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 32, 42, 13, 23, 9, 5, 31 };
int result = recycledPairs(a);
Console.WriteLine(result);
}
}
// This code is contributed by 29AjayKumar
Producción:
2
Complejidad del tiempo : O(n*log(n)).
Nota : para cualquier número entero, el número máximo de rotaciones para formar nuevos números es fijo, es decir (no_of_digits-1). Por lo tanto, esta operación es un tiempo constante que es O(1).
Publicación traducida automáticamente
Artículo escrito por akisonlyforu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA