Number of recycled pairs in an array

0 0 8 minutes read

Given an array of integers arr[], find the number of recycled pairs in the array. A recycled pair of two numbers {a, b} has the following properties :

A should be smaller than B.
Number of digits should be same.
By rotating A any number of times in one direction, we should get B.

Examples:

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.

Below is the step by step algorithm to solve the above problem:

Sort the array.
Create a new array ‘temp’ of size n where n is the length of original array.
Remove duplicates from the array by copying unique values to new array ‘temp’.
Find the number of elements copied from original array and let this number be the size of array.
Create a HashSet to store only unique rotations of the current number.
Initialize a counter with value = 0.
Traverse ‘temp’ and for every number do the following steps –
- Find the number of digits. Let it be ‘d1’.
- Rotate the number for d-1 times and store every number formed by each rotation in a HashSet.
- If formed number is found in HashSet, ignore it.
- For every rotated number, do a binary search for its presence in rest of the array.
- If it is present, increment counter.

Implementation:

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

Javascript

    // Function to find recycled pairs
    function recycledPairs(a)
    {
        var count = 1;
         
        // Sorting array
        a.sort(function(a, b) {return a - b;});
        var n = a.length;
         
        // Removing duplicates by creating new array temp.
        var temp = Array(n).fill(0);
        temp.fill(-1);
        var j = 0;
        var i =0;
        for (i; i < n - 1; i++)
        {
            if (a[i] != a[i + 1])
            {
                temp[j++] = a[i];
            }
        }
        temp[j++] = a[n - 1];
        var size = n;
         
        // Finding number of locations in temp 
        // which are occupied from copying.
        for (i; i >= 0; i--)
        {
            if (temp[i] != -1)
            {
                size = i;
                break;
            }
        }
         
        function binarySearch(arr, start, end, x) {
   
    // Iterate while start not meets end
    while (start<=end){
  
        // Find the mid index
        let mid=Math.floor((start + end)/2);
   
        // If element is present at mid, return True
        if (arr[mid]===x) return mid;
  
        // Else look in left or right half accordingly
        else if (arr[mid] < x)
             start = mid + 1;
        else
             end = mid - 1;
    }
   
    return start;
}
        // Hashset to store new Rotations
        var hs = new Set();
        for (i; i < size + 1; i++)
        {
            // Clearing hashset for each number in temp.
            new Array();
            var x = temp[i];
            // Finding number of digits of taken number
            var d1 = parseInt(Math.log10(temp[i])) + 1;
            var f = parseInt(Math.pow(10,d1 - 1));
            for (j = 1; j <= d1 - 1; j++)
            {
                // Remainder
                var r = x % 10;
                // Quotient
                var q = parseInt(x / 10);
                // Forming new number by rotating.
                x = r * f + q;
                // Number of digits of newly formed rotated number
                // to avoid duplicate numbers.
                var d2 = parseInt(Math.log10(x)) + 1;
                // Inserting formed rotated number to set s
                if (!hs.has(x))
                {
                    hs.add(x);
                    // Checking for number of digits of new number.
                    if ((d1 == d2))
                    {
                        // Searching for the formed element in rest of array.
                        var position = binarySearch(temp,i + 1,size + 1,x);
                        // If position found
                        if (position >= 0)
                        {
                            // Increment counter.
                            count++;
                        }
                    }
                }
            }
        }
         
        // Return counter
        return count;
    }
     
    // Driver function
        var a = [32, 42, 13, 23, 9, 5, 31];
        var result = recycledPairs(a);
        console.log(result);
     
    // This code is contributed by sourabhdall0001.

Python3

import math
 
# Function to find recycled pairs
 
 
def recycled_pairs(a):
    count = 0
 
    # Sorting array
    a.sort()
 
    # Removing duplicates by creating new list temp.
    temp = []
    for i in range(len(a) - 1):
        if a[i] != a[i + 1]:
            temp.append(a[i])
    temp.append(a[-1])
    size = len(temp)
 
    # Hashset to store new Rotations
    hs = set()
 
    for i in range(size):
        # Clearing hashset for each number in temp.
        hs.clear()
        x = temp[i]
 
        # Finding number of digits of taken number
        d1 = int(math.log10(temp[i])) + 1
 
        f = pow(10, d1 - 1)
        for j in range(1, d1):
            # Remainder
            r = x % 10
 
            # Quotient
            q = x // 10
 
            # Forming new number by rotating.
            x = r * f + q
 
            # Number of digits of newly formed rotated number
            # to avoid duplicate numbers.
            d2 = int(math.log10(x)) + 1
 
            # Inserting formed rotated number to set s
            if x not in hs:
                hs.add(x)
 
                # Checking for number of digits of new number.
                if d1 == d2:
                    # Searching for the formed element in rest of array.
                    position = i + 1
                    while position < size and temp[position] < x:
                        position += 1
 
                    # If position found
                    if position < size and temp[position] == x:
                        # Increment counter.
                        count += 1
 
    # Return counter
    return count
 
 
# Driver function
if __name__ == '__main__':
    a = [32, 42, 13, 23, 9, 5, 31]
    result = recycled_pairs(a)
    print(result)
# Code is contributed by Siddharth Aher

Output

Time Complexity : O(n*log(n)).

Note: For any given integer, the maximum number of rotations to form new numbers are fixed that is (no_of_digits-1). Hence, this operation is constant time that is O(1).

Asked in Google.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!