Рубрики

Количество пар в массиве, сумма которых является идеальным квадратом

Учитывая массив Задача состоит в том, чтобы найти общее количество двух пар элементов из массива, сумма которого является идеальным квадратом .

Примеры:

Input: arr[] = {2, 3, 6, 9, 10, 20}
Output: 2
Only possible pairs are (3, 6) and (6, 10)

Input: arr[] = {9, 2, 5, 1}
Output: 0

Наивный подход: используйте вложенные циклы и проверяйте каждую возможную пару на предмет того, является ли их сумма идеальным квадратом или нет. Этот метод не эффективен, когда длина массива очень велика.

Эффективный подход:

  • Сохраните все элементы массива в HashSet с именем nums и сохраните сумму максимум двух элементов в переменной с именем max .
  • Понятно, что сумма любых двух элементов из массива не будет превышать макс . Итак, найдите все идеальные квадраты, которые ≤ max, и сохраните их в ArrayList с именем perfectSquares .
  • Теперь для каждого элемента в массиве, скажем, arr [i], и для каждого идеального квадрата, сохраненного в perfectSquares , проверьте, существует ли perfectSquares.get (i) — arr [i] в числах или нет, т. Е. Есть ли какой- либо элемент в исходном массиве, который при добавлении с выбранным в данный момент элементом дает любой идеальный квадрат из списка.
  • Если вышеуказанное условие выполнено, увеличьте переменную count .
  • Выведите значение count в конце.

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

C ++

// CPP реализация подхода

  
#include <bits/stdc++.h>

using namespace std;

  

  
// Функция для возврата ArrayList, содержащего
// все идеальные квадраты до п

vector<int> getPerfectSquares(int n)

{

    vector<int> perfectSquares;

    int current = 1, i = 1;

  

    // в то время как текущий идеальный квадрат меньше или равен n

    while (current <= n)

    {

        perfectSquares.push_back(current);

        current = static_cast<int>(pow(++i, 2));

    }

    return perfectSquares;

}

  
// Функция для вывода суммы максимума
// два элемента из массива

int maxPairSum(vector<int> &arr)

{

    int n = arr.size();

    int max, secondMax;

    if (arr[0] > arr[1])

    {

        max = arr[0];

        secondMax = arr[1];

    }

    else

    {

        max = arr[1];

        secondMax = arr[0];

    }

  

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

    {

        if (arr[i] > max)

        {

            secondMax = max;

            max = arr[i];

        }

        else if (arr[i] > secondMax)

        {

            secondMax = arr[i];

        }

    }

    return (max + secondMax);

}

  
// Функция для возврата количества чисел, которые
// при добавлении с n дают идеальный квадрат

int countPairsWith(int n, vector<int> &perfectSquares, unordered_set<int> &nums)

{

    int count = 0;

    for (int i = 0; i < perfectSquares.size(); i++)

    {

        int temp = perfectSquares[i] - n;

  

        // temp> n проверяется, чтобы пары

        // (x, y) и (y, x) не учитываются дважды

        if (temp > n && find(nums.begin(), nums.end(), temp) != nums.end())

        {

            count++;

        }

    }

    return count;

}

  
// Функция для подсчета пар, сумма которых является идеальным квадратом

int countPairs(vector<int> &arr)

{

    int i, n = arr.size();

  

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

    int max = maxPairSum(arr);

  

    // Список идеальных квадратов до максимума

    vector<int> perfectSquares = getPerfectSquares(max);

  

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

    unordered_set<int> nums;

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

    {

        nums.insert(arr[i]);

    }

  

    int count = 0;

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

    {

  

        // Добавить количество элементов, которые при

        // добавлено с помощью arr [i], чтобы получить идеальный квадрат

        count += countPairsWith(arr[i], perfectSquares, nums);

    }

    return count;

}

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

int main()

{

    vector<int> arr = {2, 3, 6, 9, 10, 20};

  

    cout << countPairs(arr) << endl;

    return 0;

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

Джава

// Java реализация подхода

import java.util.*;

  

public class GFG {

  

    // Функция для возврата ArrayList, содержащего

    // все идеальные квадраты до п

    public static ArrayList<Integer> getPerfectSquares(int n)

    {

        ArrayList<Integer> perfectSquares = new ArrayList<>();

        int current = 1, i = 1;

  

        // в то время как текущий идеальный квадрат меньше или равен n

        while (current <= n) {

            perfectSquares.add(current);

            current = (int)Math.pow(++i, 2);

        }

        return perfectSquares;

    }

  

    // Функция для вывода суммы максимума

    // два элемента из массива

    public static int maxPairSum(int arr[])

    {

        int n = arr.length;

        int max, secondMax;

        if (arr[0] > arr[1]) {

            max = arr[0];

            secondMax = arr[1];

        }

        else {

            max = arr[1];

            secondMax = arr[0];

        }

  

        for (int i = 2; i < n; i++) {

            if (arr[i] > max) {

                secondMax = max;

                max = arr[i];

            }

            else if (arr[i] > secondMax) {

                secondMax = arr[i];

            }

        }

        return (max + secondMax);

    }

  

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

    // при добавлении с n дают идеальный квадрат

    public static int countPairsWith(

        int n, ArrayList<Integer> perfectSquares, 

                            HashSet<Integer> nums)

    {

        int count = 0;

        for (int i = 0; i < perfectSquares.size(); i++) {

            int temp = perfectSquares.get(i) - n;

  

            // temp> n проверяется, чтобы пары

            // (x, y) и (y, x) не учитываются дважды

            if (temp > n && nums.contains(temp))

                count++;

        }

        return count;

    }

  

    // Функция для подсчета пар, сумма которых является идеальным квадратом

    public static int countPairs(int arr[])

    {

        int i, n = arr.length;

  

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

        int max = maxPairSum(arr);

  

        // Список идеальных квадратов до максимума

        ArrayList<Integer> perfectSquares = 

                                    getPerfectSquares(max);

  

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

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

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

            nums.add(arr[i]);

  

        int count = 0;

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

  

            // Добавить количество элементов, которые при

            // добавлено с помощью arr [i], чтобы получить идеальный квадрат

            count += countPairsWith(arr[i], perfectSquares, nums);

        }

        return count;

    }

  

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

    public static void main(String[] args)

    {

        int arr[] = { 2, 3, 6, 9, 10, 20 };

  

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

    }

}

python3

# Python3 реализация подхода

  
# Функция для возврата ArrayList, содержащего
# все идеальные квадраты до п

def getPerfectSquares(n): 

  

    perfectSquares = [];

    current = 1;

    i = 1

  

    # в то время как текущий идеальный квадрат

    # меньше или равно n

    while (current <= n): 

        perfectSquares.append(current);

        i += 1;

        current = int(pow(i, 2)); 

  

    return perfectSquares; 

  
# Функция для вывода суммы максимума
# два элемента из массива

def maxPairSum(arr): 

  

    n = len(arr); 

    max = 0;

    secondMax = 0

    if (arr[0] > arr[1]): 

        max = arr[0]; 

        secondMax = arr[1]; 

    else

        max = arr[1]; 

        secondMax = arr[0]; 

  

    for i in range(2, n): 

        if (arr[i] > max): 

            secondMax = max

            max = arr[i]; 

        elif (arr[i] > secondMax): 

            secondMax = arr[i]; 

  

    return (max + secondMax); 

  
# Функция для возврата количества чисел, которые
# при добавлении с n дают идеальный квадрат

def countPairsWith(n, perfectSquares, nums): 

  

    count = 0

    for i in range(len(perfectSquares)): 

        temp = perfectSquares[i] - n; 

  

        # temp> n проверяется, чтобы пары

        # (x, y) и (y, x) не учитываются дважды

        if (temp > n and (temp in nums)): 

            count += 1

  

    return count; 

  
# Функция для подсчета пар, чьи
# сумма - идеальный квадрат

def countPairs(arr):

  

    n = len(arr); 

  

    # Сумма максимум двух элементов

    # из массива

    max = maxPairSum(arr); 

  

    # Список идеальных квадратов до максимума

    perfectSquares = getPerfectSquares(max); 

  

    # Содержит все элементы массива

    nums = []; 

    for i in range(n): 

        nums.append(arr[i]); 

  

    count = 0

    for i in range(n): 

  

        # Добавить количество элементов, которые при

        # добавлено с arr [i], чтобы получить идеальный квадрат

        count += countPairsWith(arr[i], 

                 perfectSquares, nums); 

    return count; 

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

arr = [ 2, 3, 6, 9, 10, 20 ]; 

print(countPairs(arr));

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

C #

// C # реализация подхода

using System;

using System.Collections; 

using System.Collections.Generic;

  

public class GFG { 

  

    // Функция для возврата ArrayList, содержащего

    // все идеальные квадраты до п

    public static ArrayList getPerfectSquares(int n) 

    

        ArrayList perfectSquares = new ArrayList();

        int current = 1, i = 1; 

  

        // в то время как текущий идеальный квадрат меньше или равен n

        while (current <= n) { 

            perfectSquares.Add(current); 

            current = (int)Math.Pow(++i, 2); 

        

        return perfectSquares; 

    

  

    // Функция для вывода суммы максимума

    // два элемента из массива

    public static int maxPairSum(int[] arr) 

    

        int n = arr.Length; 

        int max, secondMax; 

        if (arr[0] > arr[1]) { 

            max = arr[0]; 

            secondMax = arr[1]; 

        

        else

            max = arr[1]; 

            secondMax = arr[0]; 

        

  

        for (int i = 2; i < n; i++) { 

            if (arr[i] > max) { 

                secondMax = max; 

                max = arr[i]; 

            

            else if (arr[i] > secondMax) { 

                secondMax = arr[i]; 

            

        

        return (max + secondMax); 

    

  

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

    // при добавлении с n дают идеальный квадрат

    public static int countPairsWith( 

        int n, ArrayList perfectSquares, ArrayList nums) 

    

        int count = 0; 

        for (int i = 0; i < perfectSquares.Count; i++) { 

            int temp = (int)perfectSquares[i] - n; 

  

            // temp> n проверяется, чтобы пары

            // (x, y) и (y, x) не учитываются дважды

            if (temp > n && nums.Contains(temp)) 

                count++; 

        

        return count; 

    

  

    // Функция для подсчета пар, сумма которых является идеальным квадратом

    public static int countPairs(int[] arr) 

    

        int i, n = arr.Length; 

  

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

        int max = maxPairSum(arr); 

  

        // Список идеальных квадратов до максимума

        ArrayList perfectSquares = getPerfectSquares(max); 

  

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

        ArrayList nums = new ArrayList(); 

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

            nums.Add(arr[i]); 

  

        int count = 0; 

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

  

            // Добавить количество элементов, которые при

            // добавлено с помощью arr [i], чтобы получить идеальный квадрат

            count += countPairsWith(arr[i], perfectSquares, nums); 

        

        return count; 

    

  

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

    public static void Main() 

    

        int[] arr = { 2, 3, 6, 9, 10, 20 }; 

  

        Console.WriteLine(countPairs(arr)); 

    


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

PHP

<?php
// PHP реализация подхода

  
// Функция для возврата ArrayList, содержащего
// все идеальные квадраты до п

function getPerfectSquares($n

    $perfectSquares = array();

    $current = 1;

    $i = 1; 

  

    // пока текущий идеальный квадрат

    // меньше или равно n

    while ($current <= $n)

    

        array_push($perfectSquares, $current); 

        $current = (int)pow(++$i, 2); 

    

    return $perfectSquares

  
// Функция для вывода суммы максимума
// два элемента из массива

function maxPairSum($arr

    $n = count($arr); 

    $max;

    $secondMax

    if ($arr[0] > $arr[1]) 

    

        $max = $arr[0]; 

        $secondMax = $arr[1]; 

    

    else 

    

        $max = $arr[1]; 

        $secondMax = $arr[0]; 

    

  

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

    

        if ($arr[$i] > $max)

        

            $secondMax = $max

            $max = $arr[$i]; 

        

        else if ($arr[$i] > $secondMax)

        

            $secondMax = $arr[$i]; 

        

    

    return ($max + $secondMax); 

  
// Функция для возврата количества чисел, которые
// при добавлении с n дают идеальный квадрат

function countPairsWith($n, $perfectSquares, $nums

    $count = 0; 

    for ($i = 0; $i < count($perfectSquares); $i++) 

    

        $temp = $perfectSquares[$i] - $n

  

        // temp> n проверяется, чтобы пары

        // (x, y) и (y, x) не учитываются дважды

        if ($temp > $n && in_array($temp, $nums)) 

            $count++; 

    

    return $count

  
// Функция для подсчета пар, чьи
// сумма - идеальный квадрат

function countPairs($arr

    $n = count($arr); 

  

    // Сумма максимум двух элементов

    // из массива

    $max = maxPairSum($arr); 

  

    // Список идеальных квадратов до максимума

    $perfectSquares = getPerfectSquares($max); 

  

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

    $nums = array(); 

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

        array_push($nums, $arr[$i]); 

  

    $count = 0; 

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

    

  

        // Добавить количество элементов, которые при

        // добавлено с помощью arr [i], чтобы получить идеальный квадрат

        $count += countPairsWith($arr[$i], 

                                 $perfectSquares, $nums); 

    

    return $count

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

$arr = array( 2, 3, 6, 9, 10, 20 ); 

  

echo countPairs($arr);

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

Выход:

2

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

Количество пар в массиве, сумма которых является идеальным квадратом

0.00 (0%) 0 votes