Рубрики

Найти пару с наибольшим продуктом в массиве

Для данного массива из n элементов задача состоит в том, чтобы найти наибольшее число, такое, чтобы оно было произведением двух элементов данного массива. Если такого элемента не существует, выведите -1. Элементы находятся в диапазоне от 1 до 10 ^ 5.

Примеры :

Input :  arr[] = {10, 3, 5, 30, 35}
Output:  30
Explanation: 30 is the product of 10 and 3.

Input :  arr[] = {2, 5, 7, 8}
Output:  -1
Explanation: Since, no such element exists.

Input :  arr[] = {10, 2, 4, 30, 35}
Output:  -1

Input :  arr[] = {10, 2, 2, 4, 30, 35}
Output:  4

Input  : arr[] = {17, 2, 1, 35, 30}
Output : 35

Наивный подход состоит в том, чтобы выбрать элемент, а затем проверить для каждого продукта пары, если он равен этому числу, и обновить максимум, если число максимальное, повторять до тех пор, пока весь массив не будет пройден за O (n ^ 3) времени.

C ++

// C ++ программа для поиска пары с товаром
// в данном массиве.
#include<bits/stdc++.h>

using namespace std;

  
// Функция, чтобы найти наибольшее число, которое мы

int findGreatest( int arr[] , int n)

{

    int result = -1;

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

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

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

                if (arr[j] * arr[k] == arr[i])

                    result = max(result, arr[i]);

    return result;

}

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

int main()

{

    // Ваш код C ++

    int arr[] = {30, 10, 9, 3, 35};

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

  

    cout << findGreatest(arr, n);

  

    return 0;

}

Джава

// Java программа для поиска пары
// с продуктом в указанном массиве.

import java.io.*;

  

class GFG{

  

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

{

    int result = -1;

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

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

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

                if (arr[j] * arr[k] == arr[i])

                    result = Math.max(result, arr[i]);

    return result;

}

  

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

    static public void main (String[] args)

    {

        int []arr = {30, 10, 9, 3, 35};

        int n = arr.length;

  

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

    }

}

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

Python 3

# Python 3 программа для поиска пары
# с продуктом в указанном массиве.

  
# Функция для поиска наибольшего числа

def findGreatest( arr , n):

  

    result = -1

    for i in range(n):

        for j in range(n - 1):

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

                if (arr[j] * arr[k] == arr[i]):

                    result = max(result, arr[i])

    return result

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

if __name__ == "__main__":

      

    arr = [ 30, 10, 9, 3, 35]

    n = len(arr)

  

    print(findGreatest(arr, n))

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

C #

// C # программа для поиска пары с товаром
// в данном массиве.

using System;

  

class GFG{

  

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

{

    int result = -1;

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

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

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

                if (arr[j] * arr[k] == arr[i])

                    result = Math.Max(result, arr[i]);

    return result;

}

  

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

    static public void Main ()

    {

       int []arr = {30, 10, 9, 3, 35};

       int n = arr.Length;

  

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

    }

}

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

PHP

<?php
// PHP программа для поиска пары
// с продуктом в указанном массиве.

  
// Функция для поиска
// наибольшее число

function findGreatest($arr , $n)

{

    $result = -1;

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

        for ($j = 0; $j < $n - 1; $j++)

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

                if ($arr[$j] * $arr[$k] == $arr[$i])

                    $result = max($result, $arr[$i]);

    return $result;

}

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

$arr = array(30, 10, 9, 3, 35);

$n = count($arr);

  

echo findGreatest($arr, $n);

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

Выход :

30

Эффективный метод следует ниже реализации:

  1. Создайте пустую хеш-таблицу и сохраните в ней все элементы массива.
  2. Сортировать массив в порядке возрастания.
  3. Выберите элементы один за другим от конца массива.
  4. И проверьте, существует ли пара, произведение которой равно этому числу. При этом эффективности можно добиться. Идея состоит в том, чтобы достичь до этого числа. Если мы не получим пару до sqrt, это означает, что такой пары не существует. Мы используем хеш-таблицу, чтобы убедиться, что мы можем найти другой элемент пары за время O (1).
  5. Повторяйте шаги с 2 по 3, пока не получите элемент или весь массив.

Ниже приведена реализация.

C ++

// C ++ программа для поиска наибольшего номера продукта
#include<bits/stdc++.h>

using namespace std;

  
// Функция для поиска наибольшего числа

int findGreatest(int arr[], int n)

{

    // Сохраняем вхождения всех элементов в хеш

    // массив

    unordered_map<int, int> m;

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

        m[arr[i]]++;

  

    // Сортировка массива и прохождение всех элементов из

    // конец.

    sort(arr, arr+n);

  

    for (int i=n-1; i>1; i--)

    {

        // для каждого элемента проверяем, есть ли другой

        // элемент, который разделяет его.

        for (int j=0; j<i && arr[j]<=sqrt(arr[i]); j++)

        {

            if (arr[i] % arr[j] == 0)

            {

                int result = arr[i]/arr[j];

  

                // Проверяем, существует ли значение результата в массиве

                // или нет, если да, возврат arr [i]

                if (result != arr[j] && m[result] > 0)

                    return arr[i];

  

                // Для обработки случая, как arr [i] = 4 и

                // arr [j] = 2

                else if (result == arr[j] && m[result] > 1)

                    return arr[i];

            }

        }

    }

    return -1;

}

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

int main()

{

    int arr[] = {17, 2, 1, 15, 30};

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

    cout << findGreatest(arr, n);

    return 0;

}

Джава

// Java-программа для поиска наибольшего номера продукта

import java.util.*;

  

class GFG 

{

  

    // Функция для поиска наибольшего числа

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

    {

        // Сохраняем вхождения всех

        // элементы в хеш-массиве

        Map<Integer, Integer> m = new HashMap<>();

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

        {

            if (m.containsKey(arr[i])) 

            {

                m.put(arr[i], m.get(arr[i]) + 1);

            

            else 

            {

                m.put(arr[i], m.get(arr[i]));

            }

        }

  

        // m [arr [i]] ++;

        // Сортировать массив и пройти

        // все элементы от конца.

        Arrays.sort(arr);

  

        for (int i = n - 1; i > 1; i--) 

        {

            // для каждого элемента проверяем, есть ли другой

            // элемент, который разделяет его.

            for (int j = 0; j < i && 

                arr[j] <= Math.sqrt(arr[i]); j++) 

            {

                if (arr[i] % arr[j] == 0

                {

                    int result = arr[i] / arr[j];

  

                    // Проверяем, существует ли значение результата в массиве

                    // или нет, если да, возврат arr [i]

                    if (result != arr[j] && 

                        m.get(result) == null|| m.get(result) > 0)

                    {

                        return arr[i];

                    

                      

                    // Чтобы обработать случай как arr [i] = 4

                    // и arr [j] = 2

                    else if (result == arr[j] && m.get(result) > 1

                    {

                        return arr[i];

                    }

                }

            }

        }

        return -1;

    }

  

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

    public static void main(String[] args) 

    {

        int arr[] = {17, 2, 1, 15, 30};

        int n = arr.length;

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

    }

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

питон

# Python3 программа для поиска наибольшего номера продукта

from math import sqrt

  
# Функция для поиска наибольшего числа

def findGreatest(arr, n):

  

    # Хранить вхождения всех элементов в хеш

    # массив

    m = dict()

  

    for i in arr:

        m[i] = m.get(i, 0) + 1

  

    # Сортировать массив и пройти все элементы из

    # конец.

    arr=sorted(arr)

  

    for i in range(n - 1, 0, -1):

          

        # Для каждого элемента проверьте, есть ли другой

        # элемент, который разделяет его.

        j = 0

        while(j < i and arr[j] <= sqrt(arr[i])):

  

            if (arr[i] % arr[j] == 0):

  

                result = arr[i]//arr[j]

  

                # Проверьте, существует ли значение результата в массиве

                # или нет, если да, возврат arr [i]

                if (result != arr[j] and (result in m.keys() )and m[result] > 0):

                    return arr[i]

  

                # Для обработки случая, как arr [i] = 4 и

                # arr [j] = 2

                elif (result == arr[j] and (result in m.keys()) and m[result] > 1):

                    return arr[i]

  

            j += 1

  

  

    return -1

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

arr= [17, 2, 1, 15, 30]

n = len(arr)

print(findGreatest(arr, n))

  
# Этот код предоставлен Мохит Кумар

C #

// C # программа для поиска наибольшего номера продукта

using System;

using System.Collections.Generic;

  

class GFG 

{

  

    // Функция для поиска наибольшего числа

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

    {

        // Сохраняем вхождения всех

        // элементы в хеш-массиве

        Dictionary<int,int> m = new Dictionary<int,int> ();

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

        {

            if (m.ContainsKey(arr[i])) 

            {

                var a = m[arr[i]] + 1;

                  

                // m.Remove (arr [i]);

                m.Add(arr[i], a);

            

            else

            {

                m.Add(arr[i], arr[i]);

            }

        }

  

        // m [arr [i]] ++;

        // Сортировать массив и пройти

        // все элементы от конца.

        Array.Sort(arr);

  

        for (int i = n - 1; i > 1; i--) 

        {

            // для каждого элемента проверяем, есть ли другой

            // элемент, который разделяет его.

            for (int j = 0; j < i && 

                arr[j] <= Math.Sqrt(arr[i]); j++) 

            {

                if (arr[i] % arr[j] == 0) 

                {

                    int result = arr[i] / arr[j];

  

                    // Проверяем, существует ли значение результата в массиве

                    // или нет, если да, возврат arr [i]

                    if (result != arr[j] && 

                        m[result] == null|| m[result] > 0)

                    {

                        return arr[i];

                    

                      

                    // Чтобы обработать случай как arr [i] = 4

                    // и arr [j] = 2

                    else if (result == arr[j] && m[result] > 1) 

                    {

                        return arr[i];

                    }

                }

            }

        }

        return -1;

    }

  

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

    public static void Main(String[] args) 

    {

        int []arr = {17, 2, 1, 15, 30};

        int n = arr.Length;

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

    }

  
// Этот код предоставлен Rajput-Ji

Выход :

30

Сложность времени: O (nlogn)

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

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

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

Найти пару с наибольшим продуктом в массиве

0.00 (0%) 0 votes