Рубрики

Подсчитать пары, чьи продукты существуют в массиве

Учитывая массив, подсчитайте те пары, чье значение продукта присутствует в массиве.

Примеры:

Input : arr[] = {6, 2, 4, 12, 5, 3}
Output : 3
       All pairs whose product exist in array 
       (6 , 2) (2, 3) (4, 3)   

Input :  arr[] = {3, 5, 2, 4, 15, 8}
Output : 2 

Простое решение состоит в том, чтобы сгенерировать все пары данного массива и проверить, существует ли продукт в массиве. Если существует, то увеличить счетчик. Наконец вернуть счет.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для подсчета пар, чей продукт существует в массиве
#include<iostream>

using namespace std;

  
// Возвращает количество пар, произведение которых существует в arr []

int countPairs( int arr[] ,int n)

{

    int result = 0;

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

    {

        for (int j = i+1 ; j < n ; j++)

        {

            int product = arr[i] * arr[j] ;

  

            // найти товар в массиве

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

            {

                // если продукт нашел счетчик приращений

                if (arr[k] == product)

                {

                    result++;

                    break;

                }

            }

        }

    }

  

    // возвращаем количество всех пар, чей продукт существует в массиве

    return result;

}

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

int main()

{

    int arr[] = {6 ,2 ,4 ,12 ,5 ,3} ;

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

    cout << countPairs(arr, n);

    return 0;

}

Джава

// Java-программа для подсчета пар
// чей продукт существует в массиве

import java.io.*;

  

class GFG 

{

      
// Возвращает количество пар
// чей продукт существует в arr []

static int countPairs(int arr[],

                      int n)

{

    int result = 0;

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

    {

        for (int j = i + 1 ; j < n ; j++)

        {

            int product = arr[i] * arr[j] ;

  

            // найти товар

            // в массиве

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

            {

                // если продукт найден

                // счетчик приращений

                if (arr[k] == product)

                {

                    result++;

                    break;

                }

            }

        }

    }

  

    // возвращаем количество всех пар

    // чей продукт существует в массиве

    return result;

}

  
// Код драйвера

public static void main (String[] args) 

{

int arr[] = {6, 2, 4, 12, 5, 3} ;

int n = arr.length;

System.out.println(countPairs(arr, n));
}
}

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

Python 3

# Программа Python для подсчета пар, чьи
# продукт существует в массиве

  
# Возвращает количество пар, чьи
# продукт существует в arr []

def countPairs(arr, n):

  

    result = 0;

    for i in range (0, n):

  

        for j in range(i + 1, n):

              

            product = arr[i] * arr[j] ;

  

            # найти товар в массиве

            for k in range (0, n):

          

                # если продукт нашел счетчик приращений

                if (arr[k] == product):

                    result = result + 1;

                    break;

  

    # возвращает счетчик всей пары, чья

    # продукт существует в массиве

    return result;

  
# Драйверная программа

arr = [6, 2, 4, 12, 5, 3] ;

n = len(arr);

print(countPairs(arr, n));

      
# Этот код добавлен
# by Shivi_Aggarwal

C #

// C # программа для подсчета пар
// чей продукт существует в массиве

using System;

  

class GFG

{

  
// Возвращает количество пар
// чей продукт существует в arr []

public static int countPairs(int[] arr, 

                             int n)

{

    int result = 0;

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

    {

        for (int j = i + 1 ; j < n ; j++)

        {

            int product = arr[i] * arr[j];

  

            // найти товар в массиве

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

            {

                // если продукт найден

                // счетчик приращений

                if (arr[k] == product)

                {

                    result++;

                    break;

                }

            }

        }

    }

  

    // возвращаем количество всех пар

    // чей продукт существует в массиве

    return result;

}

  
// Код драйвера

public static void Main(string[] args)

{

    int[] arr = new int[] {6, 2, 4, 12, 5, 3};

    int n = arr.Length;

    Console.WriteLine(countPairs(arr, n));

}
}

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

PHP

<?php
// PHP программа для подсчета пар
// чей продукт существует в массиве

  
// Возвращает количество пар, чьи
// продукт существует в arr []

function countPairs($arr, $n)

{

    $result = 0;

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

    {

        for ($j = $i + 1 ; $j < $n ; $j++)

        {

            $product = $arr[$i] * $arr[$j] ;

  

            // найти товар в массиве

            for ($k = 0; $k < $n; $k++)

            {

                // если продукт нашел счетчик приращений

                if ($arr[$k] == $product)

                {

                    $result++;

                    break;

                }

            }

        }

    }

  

    // возвращаем количество всех пар, чьи

    // продукт существует в массиве

    return $result;

}

  
// Код драйвера

$arr = array(6, 2, 4, 12, 5, 3);

$n = sizeof($arr);

echo countPairs($arr, $n);

  
// Этот код добавлен
// Аканкша Рай

Выход:

3

Временная сложность: O (n 3 )

Эффективным решением является использование хэша, в котором хранятся все элементы массива. Сгенерируйте все возможные пары из данного массива 'arr' и проверьте, что произведение каждой пары находится в 'hash'. Если существует, то увеличить счетчик. Окончательно верните счет.

Ниже приведена реализация вышеуказанной идеи.

C ++

// основанная на хешировании программа C ++ для подсчета пар, произведение которых
// существует в arr []
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество пар, произведение которых существует в arr []

int countPairs(int arr[] , int n)

{

    int result = 0;

  

    // Создать пустой хеш-набор, в котором хранятся все элементы массива

    set< int > Hash;

  

    // Вставляем все элементы массива в набор

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

        Hash.insert(arr[i]);

  

    // Генерируем все пары и проверяем, есть ли в 'Hash' или нет

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

    {

        for (int j = i + 1; j<n ; j++)

        {

            int product = arr[i]*arr[j];

  

            // если продукт существует в наборе, то мы увеличиваем

            // считать на 1

            if (Hash.find(product) != Hash.end())

                result++;

        }

    }

  

    // возвращаем количество пар, чей продукт существует в массиве

    return result;

}

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

int main()

{

    int arr[] = {6 ,2 ,4 ,12 ,5 ,3};

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

    cout << countPairs(arr, n) ;

    return 0;

}

Джава

// Java-программа на основе хеширования для подсчета пар, чей продукт
// существует в arr []

import java.util.*;

  

class GFG

{

  

    // Возвращает количество пар, произведение которых существует в arr []

    static int countPairs(int arr[], int n) {

        int result = 0;

  

        // Создать пустой хеш-набор, в котором хранятся все элементы массива

        HashSet< Integer> Hash = new HashSet<>();

  

        // Вставляем все элементы массива в набор

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

        {

            Hash.add(arr[i]);

        }

  

        // Генерируем все пары и проверяем, есть ли в 'Hash' или нет

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

        {

            for (int j = i + 1; j < n; j++)

            {

                int product = arr[i] * arr[j];

  

                // если продукт существует в наборе, то мы увеличиваем

                // считать на 1

                if (Hash.contains(product))

                {

                    result++;

                }

            }

        }

  

        // возвращаем количество пар, чей продукт существует в массиве

        return result;

    }

  

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

    public static void main(String[] args) 

    {

        int arr[] = {6, 2, 4, 12, 5, 3};

        int n = arr.length;

        System.out.println(countPairs(arr, n));

    }

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

python3

# Программа C ++ для хеширования
# пары, произведение которых существует в arr []

  
# Возвращает количество пар, произведение которых
# существует в arr []

def countPairs(arr, n):

    result = 0

  

    # Создать пустой хэш-набор, который

    # хранить все элементы массива

    Hash = set()

  

    # Вставить все элементы массива в набор

    for i in range(n):

        Hash.add(arr[i])

  

    # Генерация всех пар и проверка

    # существует в 'Hash' или нет

    for i in range(n):

        for j in range(i + 1, n):

            product = arr[i] * arr[j]

  

            # если товар существует в наборе, то

            # увеличиваем количество на 1

            if product in(Hash):

                result += 1

      

    # возвращает количество пар, чьи

    # продукт существует в массиве

    return result

  
Код водителя

if __name__ == '__main__':

    arr = [6, 2, 4, 12, 5, 3]

    n = len(arr)

    print(countPairs(arr, n))

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

C #

// Программа C # на основе хеширования для подсчета пар, произведение которых
// существует в arr []

using System;

using System.Collections.Generic;

  

class GFG

{

  

    // Возвращает количество пар, произведение которых существует в arr []

    static int countPairs(int []arr, int n) 

    {

        int result = 0;

  

        // Создать пустой хеш-набор, в котором хранятся все элементы массива

        HashSet<int> Hash = new HashSet<int>();

  

        // Вставляем все элементы массива в набор

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

        {

            Hash.Add(arr[i]);

        }

  

        // Генерируем все пары и проверяем, есть ли в 'Hash' или нет

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

        {

            for (int j = i + 1; j < n; j++)

            {

                int product = arr[i] * arr[j];

  

                // если продукт существует в наборе, то мы увеличиваем

                // считать на 1

                if (Hash.Contains(product))

                {

                    result++;

                }

            }

        }

  

        // возвращаем количество пар, чей продукт существует в массиве

        return result;

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        int []arr = {6, 2, 4, 12, 5, 3};

        int n = arr.Length;

        Console.WriteLine(countPairs(arr, n));

    }

}

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

Выход:

3

Сложность по времени: O (n 2 ) «Под вставкой предположения найдите операцию take O (1) Time»

Эта статья предоставлена Nishant_Singh (Pintu) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Подсчитать пары, чьи продукты существуют в массиве

0.00 (0%) 0 votes