Рубрики

Найти количество пар (x, y) в массиве, такое что x ^ y> y ^ x

Для двух массивов натуральных чисел X [] и Y [] найдите количество пар, для которых x ^ y> y ^ x, где x — элемент из X [], а y — элемент из Y [].

Примеры:

Input: X[] = {2, 1, 6}, Y = {1, 5}
Output: 3
Explanation: There are total 3 pairs where pow(x, y) is greater
than pow(y, x) Pairs are (2, 1), (2, 5) and (6, 1)

Input: X[] = {10, 19, 18}, Y[] = {11, 15, 9}
Output: 2
Explanation: There are total 2 pairs where pow(x, y) is greater
than pow(y, x) Pairs are (10, 11) and (10, 15)

Решение грубой силы состоит в том, чтобы рассмотреть каждый элемент из X [] и Y [] и проверить, удовлетворяет ли данное условие или нет.

Ниже приведен код C ++, основанный на грубой силе.

int countPairsBruteForce(int X[], int Y[], int m, int n)

{

    int ans = 0;

    for (int i = 0; i < m; i++)

       for (int j = 0; j < n; j++)

          if (pow(X[i], Y[j]) > pow(Y[j], X[i]))

              ans++;

    return ans;

}

Сложность времени : O (M * N), где M и N — размеры заданных массивов.

Эффективное решение:
Проблема может быть решена за O (nLogn + mLogn) время. Хитрость в том, что если y> x, то x ^ y> y ^ x с некоторыми исключениями.

Ниже приведены простые шаги, основанные на этом трюке.

  • Сортировать массив Y [].
  • Для каждого x в X [] найдите индекс idx наименьшего числа больше x (также называемого ceil of x) в Y [] с помощью бинарного поиска, или мы можем использовать встроенную функцию upper_bound () в библиотеке алгоритмов.
  • Все числа после idx удовлетворяют соотношению, поэтому просто добавьте (n-idx) к числу.

Базовые случаи и исключения:
Ниже приведены исключения для x из X [] и y из Y []

  • Если x = 0, то количество пар для этого x равно 0.
  • Если x = 1, то количество пар для этого x равно нулю в Y [].
  • х меньше, чем у означает, что х ^ у больше, чем у ^ х.
    1. х = 2, у = 3 или 4
    2. х = 3, у = 2

Обратите внимание, что случай, когда x = 4 и y = 2, отсутствует

Следующая диаграмма показывает все исключения в табличной форме. Значение 1 указывает, что соответствующие (x, y) образуют правильную пару.

В следующей реализации мы предварительно обрабатываем массив Y и считаем в нем 0, 1, 2, 3 и 4, чтобы мы могли обрабатывать все исключения в постоянное время. Массив NoOfY [] используется для хранения счетчиков.

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

C ++

// C ++ программа для определения количества пар (x, y)
// в массиве такой, что x ^ y> y ^ x

  
#include<iostream>
#include<algorithm>

using namespace std;

  
// Функция для возврата количества пар с х в качестве одного элемента
// пары. В основном он ищет все значения в Y [], где
// x ^ Y [i]> Y [i] ^ x

int count(int x, int Y[], int n, int NoOfY[])

{

    // Если x равен 0, то в Y не может быть никакого значения, такого, что

    // x ^ Y [i]> Y [i] ^ x

    if (x == 0) return 0;

  

    // Если x равен 1, то число pais равно числу

    // нули в Y []

    if (x == 1) return NoOfY[0];

  

    // Находим количество элементов в Y [] со значениями больше чем x

    // upper_bound () получает адрес первого большего элемента в Y [0..n-1]

    int* idx = upper_bound(Y, Y + n, x);

    int ans = (Y + n) - idx;

  

    // Если мы достигли здесь, то х должен быть больше 1,

    // увеличиваем количество пар для y = 0 и y = 1

    ans += (NoOfY[0] + NoOfY[1]);

  

    // Уменьшаем количество пар для x = 2 и (y = 4 или y = 3)

    if (x == 2)  ans -= (NoOfY[3] + NoOfY[4]);

  

    // Увеличить количество пар для х = 3 и у = 2

    if (x == 3)  ans += NoOfY[2];

  

    return ans;

}

  
// Функция для возврата количества пар (x, y), таких, что
// x принадлежит X [], y принадлежит Y [] и x ^ y> y ^ x

int countPairs(int X[], int Y[], int m, int n)

{

    // Сохранять счетчики 0, 1, 2, 3 и 4 в массиве Y

    int NoOfY[5] = {0};

    for (int i = 0; i < n; i++)

        if (Y[i] < 5)

            NoOfY[Y[i]]++;

  

    // Сортировка Y [], чтобы мы могли выполнять в ней бинарный поиск

    sort(Y, Y + n);

  

    int total_pairs = 0; // Инициализировать результат

  

    // Взять каждый элемент X и посчитать пары с ним

    for (int i=0; i<m; i++)

        total_pairs += count(X[i], Y, n, NoOfY);

  

    return total_pairs;

}

  
// Драйвер программы

int main()

{

    int X[] = {2, 1, 6};

    int Y[] = {1, 5};

  

    int m = sizeof(X)/sizeof(X[0]);

    int n = sizeof(Y)/sizeof(Y[0]);

  

    cout << "Total pairs = " << countPairs(X, Y, m, n);

  

    return 0;

}

Джава

// Java программа для поиска количества пар (x, y)
// в массиве такой, что x ^ y> y ^ x

  

import java.util.Arrays;

  

class Test

{

    // Функция для возврата количества пар с х в качестве одного элемента

    // пары. В основном он ищет все значения в Y [], где

    // x ^ Y [i]> Y [i] ^ x

    static int count(int x, int Y[], int n, int NoOfY[])

    {

        // Если x равен 0, то в Y не может быть никакого значения, такого, что

        // x ^ Y [i]> Y [i] ^ x

        if (x == 0) return 0;

       

        // Если x равен 1, то число pais равно числу

        // нули в Y []

        if (x == 1) return NoOfY[0];

       

        // Находим количество элементов в Y [] со значениями больше чем x

        // получение верхней границы x с помощью бинарного поиска

        int idx = Arrays.binarySearch(Y, x);

        int ans;

        if(idx < 0){

            idx = Math.abs(idx+1);

            ans = Y.length - idx;

        }

        else{

            while (idx<n && Y[idx]==x) {

                idx++;

            }

            ans = Y.length - idx;

        }

       

        // Если мы достигли здесь, то х должен быть больше 1,

        // увеличиваем количество пар для y = 0 и y = 1

        ans += (NoOfY[0] + NoOfY[1]);

       

        // Уменьшаем количество пар для x = 2 и (y = 4 или y = 3)

        if (x == 2)  ans -= (NoOfY[3] + NoOfY[4]);

       

        // Увеличить количество пар для х = 3 и у = 2

        if (x == 3)  ans += NoOfY[2];

       

        return ans;

    }

       

    // Функция, возвращающая количество пар (x, y), такое, что

    // x принадлежит X [], y принадлежит Y [] и x ^ y> y ^ x

    static int countPairs(int X[], int Y[], int m, int n)

    {

        // Сохранять счетчики 0, 1, 2, 3 и 4 в массиве Y

        int NoOfY[] = new int[5];

        for (int i = 0; i < n; i++)

            if (Y[i] < 5)

                NoOfY[Y[i]]++;

       

        // Сортировка Y [], чтобы мы могли выполнять в ней бинарный поиск

        Arrays.sort(Y);

       

        int total_pairs = 0; // Инициализировать результат

       

        // Взять каждый элемент X и посчитать пары с ним

        for (int i=0; i<m; i++)

            total_pairs += count(X[i], Y, n, NoOfY);

       

        return total_pairs;

    }

      

    // Метод драйвера

    public static void main(String args[])

    {

        int X[] = {2, 1, 6};

        int Y[] = {1, 5};

       

        System.out.println("Total pairs = " + countPairs(X, Y, X.length, Y.length));

    }

}

python3

# Python3 программа для поиска номера
количество пар (x, y) в массиве
# такой, что x ^ y> y ^ x

import bisect

  
# Функция для возврата количества пар
# с х в качестве одного элемента пары.
# В основном ищет все значения в Y
# где x ^ Y [i]> Y [i] ^ x

def count(x, Y, n, NoOfY):

      

    # Если х равен 0, то не может быть

    # любое значение в Y такое, что

    # x ^ Y [i]> Y [i] ^ x

    if x == 0:

        return 0

  

    # Если х равен 1, то количество пар

    # равно количеству нулей в Y

    if x == 1:

        return NoOfY[0]

  

    # Найти количество элементов в Y [] с помощью

    # значения больше x, bisect.bisect_right

    # получает адрес первого большего элемента

    # в Y [0..n-1]

    idx = bisect.bisect_right(Y, x)

    ans = n - idx

  

    # Если мы достигли здесь, то х должно быть больше 1,

    # увеличить количество пар для y = 0 и y = 1

    ans += NoOfY[0] + NoOfY[1]

  

    # Уменьшить количество пар

    # для х = 2 и (у = 4 или у = 3)

    if x == 2:

        ans -= NoOfY[3] + NoOfY[4]

  

    # Увеличить количество пар

    # для х = 3 и у = 2

    if x == 3:

        ans += NoOfY[2]

  

    return ans

  
# Функция для возврата количества пар (х, у)
# такое, что x принадлежит X,
# у принадлежит Y и х ^ у> у ^ х

def count_pairs(X, Y, m, n):

  

    # Для хранения счетчиков 0, 1, 2, 3,

    № и 4 в массиве Y

    NoOfY = [0] * 5

    for i in range(n):

        if Y[i] < 5:

            NoOfY[Y[i]] += 1

              

    # Сортировать Y, чтобы мы могли выполнять бинарный поиск в нем

    Y.sort()

    total_pairs = 0 # Инициализировать результат

  

    # Взять каждый элемент X и

    количество пар с ним

    for x in X:

        total_pairs += count(x, Y, n, NoOfY)

  

    return total_pairs

  
Код водителя

if __name__ == '__main__':

  

    X = [2, 1, 6]

    Y = [1, 5]

    print("Total pairs = "

           count_pairs(X, Y, len(X), len(Y)))

  
# Этот код предоставлен shaswatd673

C #

// C # программа для нахождения количества пар (x, y)
// в массиве такой, что x ^ y> y ^ x

using System;

  

class GFG {

      

    // Функция для возврата количества пар

    // с х в качестве одного элемента пары.

    // Он в основном ищет все значения в Y []

    // где x ^ Y [i]> Y [i] ^ x

    static int count(int x, int[] Y, int n, int[] NoOfY)

    {

        // Если х равен 0, то не может быть

        // значение в Y такое, что x ^ Y [i]> Y [i] ^ x

        if (x == 0)

            return 0;

  

        // Если х равен 1, то число Паис

        // равно количеству нулей в Y []

        if (x == 1)

            return NoOfY[0];

  

        // Находим количество элементов в Y [] с

        // значения больше чем x

        // верхняя граница x с бинарным поиском

        int idx = Array.BinarySearch(Y, x);

        int ans;

        if (idx < 0) {

            idx = Math.Abs(idx + 1);

            ans = Y.Length - idx;

        }

          

        else {

            while (idx<n && Y[idx] == x) {

                idx++;

            }

            ans = Y.Length - idx;

        }

  

        // Если мы достигли здесь, то х

        // должно быть больше 1, увеличить

        // количество пар для y = 0 и y = 1

        ans += (NoOfY[0] + NoOfY[1]);

  

        // Уменьшаем количество пар

        // для х = 2 и (у = 4 или у = 3)

        if (x == 2)

            ans -= (NoOfY[3] + NoOfY[4]);

  

        // Увеличить количество пар для х = 3 и у = 2

        if (x == 3)

            ans += NoOfY[2];

  

        return ans;

    }

  

    // Функция к которой возвращает count

    // пар (x, y) таких, что x принадлежит

    // к X [], y принадлежит Y [] и x ^ y> y ^ x

    static int countPairs(int[] X, int[] Y, int m, int n)

    {

        // Сохранять счетчики 0, 1, 2, 3 и 4 в массиве Y

        int[] NoOfY = new int[5];

        for (int i = 0; i < n; i++)

            if (Y[i] < 5)

                NoOfY[Y[i]]++;

  

        // Сортировка Y [], чтобы мы могли выполнять в ней бинарный поиск

        Array.Sort(Y);

  

        int total_pairs = 0; // Инициализировать результат

  

        // Взять каждый элемент X и посчитать пары с ним

        for (int i = 0; i < m; i++)

            total_pairs += count(X[i], Y, n, NoOfY);

  

        return total_pairs;

    }

  

    // Метод драйвера

    public static void Main()

    {

        int[] X = { 2, 1, 6 };

        int[] Y = { 1, 5 };

  

        Console.Write("Total pairs = "

                       countPairs(X, Y, X.Length, Y.Length));

    }

}

  
// Этот код предоставлен Sam007


Выход:

Total pairs = 3

Сложность времени: O (nLogn + mLogn), где m и n — размеры массивов X [] и Y [] соответственно. Шаг сортировки занимает O (nLogn) время. Затем каждый элемент из X [] ищется в Y [] с использованием бинарного поиска. Этот шаг занимает O (mLogn) время.

Эта статья предоставлена Shubham Mittal . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти количество пар (x, y) в массиве, такое что x ^ y> y ^ x

0.00 (0%) 0 votes