contestada

You are given an array of integers. Your task is to create pairs of them, such that every created pair has the same sum. This sum is not specified, but the number of created pairs should be the maximum possible. Each array element may belong to one pair only.

Write a function

class Solution public int
solution (int[] A); }

that, given an array A consisting of N integers, returns the maximum possible number of pairs with the same sum.

Examples:
1. Given A = [1, 9, 8, 100, 2], the function should return 2. The pairs are (A[0]. A[1]) and (A[2], A[4]); the sum of each pair is 10.
2. Given A = [2, 2, 2, 3], the function should return 1. Although, for instance, A[0]+A[1] = A[0]+A[2], the pairs (A[0], A[1]) and (A[0], A[2]) cannot exist at the same time, because they both contain a common element, A[0].

Respuesta :

Talanat
Complete PYTHON code with explanation:

def solution(nums):

# form a dictionary which will store

# the possible pair's sum as key and the indexs used for the sum

sumAndpair = {}

# for every element in list nums

for i in range(len(nums)):

# iterate on all the element to the right of current element

for j in range(i+1,len(nums)):

# calculate the sum of current 2 elements

sum = nums[i] + nums[j]

# if the sum is already in the dictionay

if sum in sumAndpair:

# check if the current index have already been used

# if yes, then continue to next iteration

# this will make sure that same number have not been used more than once

if i in sumAndpair[sum] or j in sumAndpair[sum]:

continue

# if no, then append the current i and j to the value of current sum

else:

sumAndpair[sum].append(i)

sumAndpair[sum].append(j)

# if the current sum is not in the dictionary

# add the sum as key with a list of index used

else:

sumAndpair[sum] = [i, j]

# copmpute the maximum possible number of pairs with the same sum

# which will be the maximum length value out of all the possible sum

# this maximum length will be divided by 2, since a pair of i, j contrinute to one sum

maxLength = 0

for key, value in sumAndpair.items():

if maxLength

Otras preguntas