Количество пар в массиве с разницей, равной разнице с перевернутыми цифрами

Опубликовано: 21 Сентября, 2022

Дан массив arr[] из N целых чисел. Задача состоит в том, чтобы найти количество пар элементов массива (arr[i], arr[j]) , таких, что разница между парами равна разнице, когда цифры обоих цифры обратные.

Примеры:

Input: arr[] = {42, 11, 1, 97}
Output: 2
Explanation:
The valid pairs of array elements are (42, 97), (11, 1) as:
1. 42 – 97 = 24 – 79 = (-55)
2. 11 – 1 = 11 – 1 = (10)
Input: arr[] = {1, 2, 3, 4}
Output: 6

Подход: Данную проблему можно решить с помощью хеширования, основанного на следующих наблюдениях:

A valid pair (i, j) will follow the equation as
=> arr[i] – arr[j] = rev(arr[i]) – rev(arr[j])
=> arr[i] – rev(arr[i]) = arr[j] – rev(arr[j])

Выполните следующие шаги, чтобы решить проблему:

Теперь создайте функцию reverseDigits , которая будет принимать целое число в качестве аргумента и переворачивать цифры этого целого числа.
Сохраните частоту значений arr[i] – rev(arr[i]) в неупорядоченной карте, скажем, mp .
Для каждого ключа (= разность) частоты X количество пар, которые могут быть образованы, определяется выражением .
Общее количество пар задается суммой значения приведенного выше выражения для каждой частоты, хранящейся в карте mp .

Ниже приведена реализация вышеуказанного подхода:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to reverse the digits
// of an integer
int reverseDigits(int n)
{
    // Convert the given number
    // to a string
    string s = to_string(n);
 
    // Reverse the string
    reverse(s.begin(), s.end());
 
    // Return the value of the string
    return stoi(s);
}
int countValidPairs(vector<int> arr)
{
    // Stores resultant count of pairs
    long long res = 0;
 
    // Stores the frequencies of
    // differences
    unordered_map<int, int> mp;
    for (int i = 0; i < arr.size(); i++) {
        mp[arr[i] - reverseDigits(arr[i])]++;
    }
 
    // Traverse the map and count pairs
    // formed for all frequency values
    for (auto i : mp) {
        long long int t = i.second;
        res += t * (t - 1) / 2;
    }
 
    // Return the resultant count
    return res;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 2, 3, 4 };
    cout << countValidPairs(arr);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.HashMap;
 
class GFG {
 
    // Function to reverse the digits
    // of an integer
    public static int reverseDigits(int n)
    {
       
        // Convert the given number
        // to a string
        String s = String.valueOf(n);
 
        // Reverse the string
        s = new StringBuffer(s).reverse().toString();
 
        // Return the value of the string
        return Integer.parseInt(s);
    }
 
    public static int countValidPairs(int[] arr)
    {
       
        // Stores resultant count of pairs
        int res = 0;
 
        // Stores the frequencies of
        // differences
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (mp.containsKey(arr[i] - reverseDigits(arr[i]))) {
                mp.put(arr[i] - reverseDigits(arr[i]), mp.get(arr[i] - reverseDigits(arr[i])) + 1);
            } else {
                mp.put(arr[i] - reverseDigits(arr[i]), 1);
            }
        }
 
        // Traverse the map and count pairs
        // formed for all frequency values
        for (int i : mp.keySet()) {
            int t = mp.get(i);
            res += t * (t - 1) / 2;
        }
 
        // Return the resultant count
        return res;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int[] arr = { 1, 2, 3, 4 };
        System.out.println(countValidPairs(arr));
    }
 
}
 
// This code is contributed by saurabh_jaiswal.

Python3

# python program for the above approach
 
# Function to reverse the digits
# of an integer
def reverseDigits(n):
 
    # Convert the given number
    # to a string
    s = str(n)
 
    # Reverse the string
    s = "".join(reversed(s))
 
    # Return the value of the string
    return int(s)
 
def countValidPairs(arr):
 
    # Stores resultant count of pairs
    res = 0
 
    # Stores the frequencies of
    # differences
    mp = {}
 
    for i in range(0, len(arr)):
        if not arr[i] - reverseDigits(arr[i]) in mp:
            mp[arr[i] - reverseDigits(arr[i])] = 1
        else:
            mp[arr[i] - reverseDigits(arr[i])] += 1
 
        # Traverse the map and count pairs
        # formed for all frequency values
    for i in mp:
        t = mp[i]
        res += (t * (t - 1)) // 2
 
        # Return the resultant count
    return res
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 2, 3, 4]
    print(countValidPairs(arr))
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to reverse the digits
    // of an integer
    public static int reverseDigits(int n)
    {
 
        // Convert the given number
        // to a string
        string s = n.ToString();
 
        // Reverse the string
        char[] arr = s.ToCharArray();
        Array.Reverse(arr);
        string st = new string(arr);
 
        // Return the value of the string
        return Int32.Parse(st);
    }
 
    public static int countValidPairs(int[] arr)
    {
 
        // Stores resultant count of pairs
        int res = 0;
 
        // Stores the frequencies of
        // differences
        Dictionary<int, int> mp
            = new Dictionary<int, int>();
        for (int i = 0; i < arr.Length; i++) {
            if (mp.ContainsKey(arr[i]
                               - reverseDigits(arr[i]))) {
                mp[arr[i] - reverseDigits(arr[i])]
                    = mp[arr[i] - reverseDigits(arr[i])]
                      + 1;
            }
            else {
                mp[arr[i] - reverseDigits(arr[i])] = 1;
            }
        }
 
        // Traverse the map and count pairs
        // formed for all frequency values
        foreach(int i in mp.Keys)
        {
            int t = mp[i];
            res += t * (t - 1) / 2;
        }
 
        // Return the resultant count
        return res;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4 };
        Console.WriteLine(countValidPairs(arr));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
// Javascript program for the above approach
 
// Function to reverse the digits
// of an integer
function reverseDigits(n)
{
 
  // Convert the given number
  // to a string
  let s = new String(n);
 
  // Reverse the string
  s = s.split("").reverse().join("");
 
  // Return the value of the string
  return parseInt(s);
}
function countValidPairs(arr)
{
 
  // Stores resultant count of pairs
  let res = 0;
 
  // Stores the frequencies of
  // differences
  let mp = new Map();
  for (let i = 0; i < arr.length; i++) {
    let temp = arr[i] - reverseDigits(arr[i]);
    if (mp.has(temp)) {
      mp.set(temp, mp.get(temp) + 1);
    } else {
      mp.set(temp, 1);
    }
  }
 
  // Traverse the map and count pairs
  // formed for all frequency values
  for (i of mp) {
    let t = i[1];
    res += (t * (t - 1)) / 2;
  }
 
  // Return the resultant count
  return res;
}
 
// Driver Code
let arr = [1, 2, 3, 4];
document.write(countValidPairs(arr));
 
// This code is contributed by gfgking.
</script>

Временная сложность: O(N)
Вспомогательное пространство: O(N)

Mathematical

Количество пар в массиве с разницей, равной разнице с перевернутыми цифрами

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ