Anzahl der recycelten Paare in einem Array
Ermitteln Sie bei einem gegebenen Array von Ganzzahlen arr[] die Anzahl der wiederverwendeten Paare im Array. Ein recyceltes Paar aus zwei Zahlen {a, b} hat die folgenden Eigenschaften:
- A sollte kleiner sein als B.
- Die Anzahl der Ziffern sollte gleich sein.
- Indem wir A beliebig oft in eine Richtung drehen, sollten wir B erhalten.
Beispiele:
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.
Unten ist der Schritt-für-Schritt-Algorithmus zur Lösung des obigen Problems:
- Sortieren Sie das Array.
- Erstellen Sie ein neues Array „temp“ der Größe n, wobei n die Länge des ursprünglichen Arrays ist.
- Entfernen Sie Duplikate aus dem Array, indem Sie eindeutige Werte in das neue Array „temp“ kopieren.
- Finden Sie die Anzahl der Elemente, die aus dem ursprünglichen Array kopiert wurden, und lassen Sie diese Zahl die Größe des Arrays sein.
- Erstellen Sie ein HashSet, um nur eindeutige Rotationen der aktuellen Zahl zu speichern.
- Initialisieren Sie einen Zähler mit Wert = 0.
- Durchqueren Sie „temp“ und führen Sie für jede Zahl die folgenden Schritte aus –
- Finden Sie die Anzahl der Ziffern. Lassen Sie es 'd1' sein.
- Rotiere die Zahl d-1 Mal und speichere jede Zahl, die durch jede Rotation gebildet wird, in einem HashSet.
- Wenn eine gebildete Zahl in HashSet gefunden wird, ignorieren Sie sie.
- Führen Sie für jede rotierte Zahl eine binäre Suche nach ihrem Vorhandensein im Rest des Arrays durch.
- Falls vorhanden, Zähler inkrementieren.
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
Ausgabe:
2
Zeitkomplexität : O(n*log(n)).
Hinweis : Für jede gegebene Ganzzahl ist die maximale Anzahl von Rotationen zum Bilden neuer Zahlen festgelegt, dh (no_of_digits-1). Daher ist diese Operation eine konstante Zeit, die O (1) ist.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .