Scribd
Upload
10 views4 pages

DAA Lab Assignment3

The document describes three methods to count pairs in an array that sum to a given integer k. The brute-force solution has a time complexity of O(n²), the optimized solution using sorting and two pointers has a complexity of O(n log n), and the most efficient solution using a hash map operates in O(n) time. Each method has its own limitations regarding performance and space usage.

Uploaded by

prathmeshkarale2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views4 pages

DAA Lab Assignment3

The document describes three methods to count pairs in an array that sum to a given integer k. The brute-force solution has a time complexity of O(n²), the optimized solution using sorting and two pointers has a complexity of O(n log n), and the most efficient solution using a hash map operates in O(n) time. Each method has its own limitations regarding performance and space usage.

Uploaded by

prathmeshkarale2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Lab Assignment 3: Count Pairs with

Given Sum:
**Problem Statement**:
Given an array and an integer k, count the number of pairs (i, j) such that arr[i] + arr[j] == k.

1. Brute-force Solution
This approach uses two nested loops to check every possible pair.

### Code:

```cpp
#include<iostream>
using namespace std;

int countPairsBrute(int arr[], int n, int k) {


int count = 0;
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
if(arr[i] + arr[j] == k) {
count++;
}
}
}
return count;
}
```

**Time Complexity:** O(n²) – because it uses two nested loops.


**Limitation:** Very slow for large arrays.

2. Optimized Solution (O(n log n)) using Sorting + Two Pointers


This approach sorts the array and uses the two-pointer technique to find valid pairs.

### Code:
```cpp
#include<iostream>
#include<algorithm>
using namespace std;

int countPairsTwoPointers(int arr[], int n, int k) {


sort(arr, arr + n);
int count = 0;
int left = 0, right = n - 1;

while (left < right) {


int sum = arr[left] + arr[right];
if (sum == k) {
count++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return count;
}
```

**Time Complexity:** O(n log n) – due to sorting.


**Limitation:** Only works when all elements are unique, or needs modification if
duplicates are present.

3. Most Efficient Solution (O(n)) using Hash Map


This approach uses a hash map to store occurrences and check for (k - current) in O(1).

### Code:
```cpp
#include<iostream>
#include<unordered_map>
using namespace std;

int countPairsHashMap(int arr[], int n, int k) {


unordered_map<int, int> freq;
int count = 0;

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


int complement = k - arr[i];
if(freq[complement]) {
count += freq[complement];
}
freq[arr[i]]++;
}

return count;
}
```

**Time Complexity:** O(n) – single pass with constant-time lookups.


**Limitation:** Uses extra space O(n) for hash map.

You might also like