Count Pairs with given sum in c#

Programming C#
1

The problem of counting pairs with a given sum involves finding all pairs of elements in an array that add up to a specified target sum. This can be efficiently solved using a hash table (or dictionary) to track occurrences of numbers.

Problem Statement

Given an array of integers and a target sum, count the number of unique pairs (a, b) such that a + b = target. Each pair should only be counted once, regardless of the order of elements.

Approach

  1. Use a Dictionary: We can use a dictionary to store the counts of each number in the array as we iterate through it.
  2. Check for Complements: For each number, calculate its complement (i.e., target - number). If this complement exists in the dictionary, we can count how many times it can form a pair with the current number.
  3. Avoid Double Counting: We need to ensure we do not count the same pair twice. This can be managed by either:
    • Using a set to store pairs.
    • Adjusting the counting logic to prevent counting pairs in reverse.

C# Implementation

Here’s how you can implement this in C#:

using System;
using System.Collections.Generic;

public class Solution
{
    public int CountPairsWithSum(int[] nums, int target)
    {
        var count = 0;
        var numCount = new Dictionary<int, int>();

        foreach (var num in nums)
        {
            // Calculate the complement
            int complement = target - num;

            // Check if the complement exists in the dictionary
            if (numCount.ContainsKey(complement))
            {
                count += numCount[complement]; // Add the count of the complement
            }

            // Add/update the current number in the dictionary
            if (numCount.ContainsKey(num))
            {
                numCount[num]++;
            }
            else
            {
                numCount[num] = 1;
            }
        }

        return count;
    }
}

Explanation of the Code

  1. Initialization:

    • count: This variable tracks the number of pairs found.
    • numCount: A dictionary to count occurrences of each number.

  2. Loop through Numbers:

    • For each number in the input array, calculate its complement with respect to the target.
    • Check if the complement exists in numCount. If it does, increment the count by the number of times the complement has appeared before.
    • Update numCount with the current number. If it exists, increment its count; if not, add it with a count of 1.

  3. Return the Count: Finally, return the total count of pairs.

Complexity

  • Time Complexity: O(n), where n is the number of elements in the array. Each element is processed once.
  • Space Complexity: O(n) in the worst case for the dictionary that stores the counts of each number.

Example

For the input nums = [1, 5, 7, -1, 5] and target = 6, the output will be 3 because the pairs that sum up to 6 are:

  • (1, 5)
  • (5, 1)
  • (7, -1)

This approach efficiently counts pairs by leveraging a dictionary to track number occurrences, allowing for quick lookups of complements.