Pair Sum with Python O(n)

Given a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k. If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn’t, even if they include the same values.

Signature

int numberOfWays(int[] arr, int k)

Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000,000,000]. k is in the range [1, 1,000,000,000].

Output

Return the number of different pairs of elements which sum to k.

Example 1

n = 5 k = 6 arr = [1, 2, 3, 4, 3] output = 2The valid pairs are 2+4 and 3+3.

Example 2

n = 5 k = 6 arr = [1, 5, 3, 3, 3] output = 4There’s one valid pair 1+5, and three different valid pairs 3+3 (the 3rd and 4th elements, 3rd and 5th elements, and 4th and 5th elements).

Solution using Python:

Complexity:

• Time: O(n)
• Space: Array of n and Hash of n (Who cares about space?? really ??)

Execution:

Case 1:

[1, 2, 3, 4, 3]
{1: 1, 2: 1, 3: 2, 4: 1}
Total Pairs is: 2.0

If you are looking for an all-in-one solution to help you prepare for the AWS Cloud Practitioner Certification Exam, look no further than this AWS Cloud Practitioner CCP CLFC01 book below.

Achieve AWS Solutions Architect Associate Certification with Confidence: Master SAA Exam with the Latest Practice Tests and Quizzes illustrated

Case 2:

[1, 5, 3, 3, 3]
{1: 1, 5: 1, 3: 3}
Total Pairs is: 4.0

"Become a Canada Expert: Ace the Citizenship Test and Impress Everyone with Your Knowledge of Canadian History, Geography, Government, Culture, People, Languages, Travel, Wildlife, Hockey, Tourism, Sceneries, Arts, and Data Visualization. Get the Top 1000 Canada Quiz Now!"

Complexity:

• Time: O(n)
• Space: Array of n and Hash of n (Who cares about space?? really ??)

Execution:

Case 1:

[1, 2, 3, 4, 3]
{1: 1, 2: 1, 3: 2, 4: 1}
Total Pairs is: 2.0

Case 2:

Invest in your future today by enrolling in this Azure Fundamentals - Pass the Azure Fundamentals Exam with Ease: Master the AZ-900 Certification with the Comprehensive Exam Preparation Guide!

[1, 5, 3, 3, 3]
{1: 1, 5: 1, 3: 3}
Total Pairs is: 4.0

Complexity:

• Time: O(n)
• Space: Array of n and Hash of n (Who cares about space?? really ??)

Execution:

Case 1:

[1, 2, 3, 4, 3]
{1: 1, 2: 1, 3: 2, 4: 1}
Total Pairs is: 2.0

Case 2:

[1, 5, 3, 3, 3]
{1: 1, 5: 1, 3: 3}
Total Pairs is: 4.0

 

What are the Greenest or Least Environmentally Friendly Programming Languages?