Dada una array arr de elementos distintos de tamaño N , la tarea es encontrar el número total de pares en la array cuya suma es un cubo perfecto .
Ejemplos:
Entrada: arr[] = {2, 3, 6, 9, 10, 20}
Salida: 1 El
único par posible es (2, 6)
Entrada: arr[] = {9, 2, 5, 1}
Salida: 0
Enfoque ingenuo: use bucles anidados y verifique cada par posible para ver si su suma es un cubo perfecto o no. Esta técnica no es efectiva cuando la longitud de la array es muy grande.
Enfoque eficiente:
- Almacene todos los elementos de la array en un HashSet y guarde la suma de los dos elementos máximos en una variable llamada max .
- Está claro que la suma de dos elementos cualquiera de la array no excederá max . Por lo tanto, encuentre todos los cubos perfectos que estén al máximo y guárdelos en una ArrayList llamada perfectcubes .
- Ahora, para cada elemento de la array, diga arr[i] y para cada cubo perfecto guardado en perfectcubes , verifique si perfectcubes.get(i) – arr[i] existe en números o no, es decir, si hay algún elemento en la array original que cuando se agrega con el elemento elegido actualmente da cualquier cubo perfecto de la lista.
- Si se cumple la condición anterior, incremente la variable de conteo .
- Imprime el valor de conteo al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
#include<vector>
using namespace std;
// Function to return an ArrayList containing
// all the perfect cubes upto n
vector<int> getPerfectcubes(int n)
{
vector<int>perfectcubes;
int current = 1;
int i = 1;
// while current perfect cube is
// less than or equal to n
while (current <= n)
{
perfectcubes.push_back(current);
i += 1;
current = int(pow(i, 3));
}
return perfectcubes;
}
// Function to print the sum of maximum
// two elements from the array
int maxPairSum(int arr[],int n)
{
int max = 0;
int secondMax = 0;
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);
}
// Function to return the count of numbers that
// when added with n give a perfect cube
int countPairsWith(int n, vector<int> perfectcubes, vector<int> nums)
{
int count = 0;
int len=perfectcubes.size();
for (int i = 0; i < len; i++)
{
int temp = perfectcubes[i] - n;
// temp > n is checked so that pairs
// (x, y) and (y, x) don't get counted twice
if (temp > n)
{
for(auto j=nums.begin();j!=nums.end();j++)
{
if((*j)==temp)
count += 1;
}
}
}
return count;
}
// Function to count the pairs whose
// sum is a perfect cube
int countPairs(int arr[],int n)
{
// Sum of the maximum two elements
// from the array
int max = maxPairSum(arr,n);
// List of perfect cubes upto max
vector<int>perfectcubes = getPerfectcubes(max);
// Contains all the array elements
vector<int>nums;
for (int i = 0 ; i < n; i++)
nums.push_back(arr[i]);
int count = 0;
for (int i = 0; i < n; i++)
{
// Add count of the elements that when
// added with arr[i] give a perfect cube
count += countPairsWith(arr[i], perfectcubes, nums);
}
return count;
}
// Driver code
int main()
{
int arr[] = { 2, 6, 18, 9, 999, 1 };
int n=sizeof(arr)/sizeof(arr[0]);
cout<<(countPairs(arr,n));
}
// This code is contributed by chitranayal
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return an ArrayList containing
// all the perfect cubes upto n
static List<Integer> getPerfectcubes(int n) {
List<Integer> perfectcubes = new ArrayList<Integer>();
int current = 1;
int i = 1;
// while current perfect cube is
// less than or equal to n
while (current <= n) {
perfectcubes.add(current);
i += 1;
current = (int) (Math.pow(i, 3));
}
return perfectcubes;
}
// Function to print the sum of maximum
// two elements from the array
static int maxPairSum(int[] arr) {
int n = arr.length;
int max = 0;
int secondMax = 0;
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);
}
// Function to return the count of numbers that
// when added with n give a perfect cube
static int countPairsWith(int n, List<Integer>
perfectcubes, List<Integer> nums) {
int count = 0;
for (int i = 0; i < perfectcubes.size(); i++) {
int temp = perfectcubes.get(i) - n;
// temp > n is checked so that pairs
// (x, y) and (y, x) don't get counted twice
if (temp > n && (nums.contains(temp)))
count += 1;
}
return count;
}
// Function to count the pairs whose
// sum is a perfect cube
static int countPairs(int[] arr) {
int n = arr.length;
// Sum of the maximum two elements
// from the array
int max = maxPairSum(arr);
// List of perfect cubes upto max
List<Integer> perfectcubes = getPerfectcubes(max);
// Contains all the array elements
List<Integer> nums = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
nums.add(arr[i]);
}
int count = 0;
for (int i = 0; i < n; i++) {
// Add count of the elements that when
// added with arr[i] give a perfect cube
count += countPairsWith(arr[i], perfectcubes, nums);
}
return count;
}
// Driver code
public static void main(String[] agrs) {
int[] arr = { 2, 6, 18, 9, 999, 1 };
System.out.print(countPairs(arr));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return an ArrayList containing # all the perfect cubes upto n def getPerfectcubes(n): perfectcubes = []; current = 1; i = 1; # while current perfect cube is # less than or equal to n while (current <= n): perfectcubes.append(current); i += 1; current = int(pow(i, 3)); return perfectcubes; # Function to print the sum of maximum # two elements from the array 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); # Function to return the count of numbers that # when added with n give a perfect cube def countPairsWith(n, perfectcubes, nums): count = 0; for i in range(len(perfectcubes)): temp = perfectcubes[i] - n; # temp > n is checked so that pairs # (x, y) and (y, x) don't get counted twice if (temp > n and (temp in nums)): count += 1; return count; # Function to count the pairs whose # sum is a perfect cube def countPairs(arr): n = len(arr); # Sum of the maximum two elements # from the array max = maxPairSum(arr); # List of perfect cubes upto max perfectcubes = getPerfectcubes(max); # Contains all the array elements nums = []; for i in range(n): nums.append(arr[i]); count = 0; for i in range(n): # Add count of the elements that when # added with arr[i] give a perfect cube count += countPairsWith(arr[i], perfectcubes, nums); return count; # Driver code arr = [ 2, 6, 18, 9, 999, 1 ]; print(countPairs(arr));
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return an List containing
// all the perfect cubes upto n
static List<int> getPerfectcubes(int n) {
List<int> perfectcubes = new List<int>();
int current = 1;
int i = 1;
// while current perfect cube is
// less than or equal to n
while (current <= n) {
perfectcubes.Add(current);
i += 1;
current = (int) (Math.Pow(i, 3));
}
return perfectcubes;
}
// Function to print the sum of maximum
// two elements from the array
static int maxPairSum(int[] arr) {
int n = arr.Length;
int max = 0;
int secondMax = 0;
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);
}
// Function to return the count of numbers that
// when added with n give a perfect cube
static int countPairsWith(int n, List<int>
perfectcubes, List<int> nums) {
int count = 0;
for (int i = 0; i < perfectcubes.Count; i++) {
int temp = perfectcubes[i] - n;
// temp > n is checked so that pairs
// (x, y) and (y, x) don't get counted twice
if (temp > n && (nums.Contains(temp)))
count += 1;
}
return count;
}
// Function to count the pairs whose
// sum is a perfect cube
static int countPairs(int[] arr) {
int n = arr.Length;
// Sum of the maximum two elements
// from the array
int max = maxPairSum(arr);
// List of perfect cubes upto max
List<int> perfectcubes = getPerfectcubes(max);
// Contains all the array elements
List<int> nums = new List<int>();
for (int i = 0; i < n; i++) {
nums.Add(arr[i]);
}
int count = 0;
for (int i = 0; i < n; i++) {
// Add count of the elements that when
// added with arr[i] give a perfect cube
count += countPairsWith(arr[i], perfectcubes, nums);
}
return count;
}
// Driver code
public static void Main(String[] agrs) {
int[] arr = { 2, 6, 18, 9, 999, 1 };
Console.Write(countPairs(arr));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to return an ArrayList containing
// all the perfect cubes upto n
function getPerfectcubes(n)
{
let perfectcubes = [];
let current = 1;
let i = 1;
// while current perfect cube is
// less than or equal to n
while (current <= n)
{
perfectcubes.push(current);
i += 1;
current = parseInt(Math.pow(i, 3));
}
return perfectcubes;
}
// Function to print the sum of maximum
// two elements from the array
function maxPairSum(arr,n)
{
let max = 0;
let secondMax = 0;
if (arr[0] > arr[1])
{
max = arr[0];
secondMax = arr[1];
}
else
{
max = arr[1];
secondMax = arr[0];
}
for (let 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);
}
// Function to return the count of numbers that
// when added with n give a perfect cube
function countPairsWith(n, perfectcubes, nums)
{
let count = 0;
let len=perfectcubes.length;
for (let i = 0; i < len; i++)
{
let temp = perfectcubes[i] - n;
// temp > n is checked so that pairs
// (x, y) and (y, x) don't get counted twice
if (temp > n)
{
for(let j = 0; j < nums.length; j++)
{
if(nums[j] == temp)
count += 1;
}
}
}
return count;
}
// Function to count the pairs whose
// sum is a perfect cube
function countPairs(arr,n)
{
// Sum of the maximum two elements
// from the array
let max = maxPairSum(arr,n);
// List of perfect cubes upto max
let perfectcubes = getPerfectcubes(max);
// Contains all the array elements
let nums = [];
for (let i = 0 ; i < n; i++)
nums.push(arr[i]);
let count = 0;
for (let i = 0; i < n; i++)
{
// Add count of the elements that when
// added with arr[i] give a perfect cube
count += countPairsWith(arr[i], perfectcubes, nums);
}
return count;
}
// Driver code
let arr = [ 2, 6, 18, 9, 999, 1 ];
let n = arr.length;
document.write(countPairs(arr,n));
</script>
Producción:
3
Complejidad temporal: O(n 3 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por SHUBHAMSINGH10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA