13 hours ago

admin 1.9k

Sehore

Question: Repeating Integer Pairs

Problem Statement:

You are given a list of integers. Write a program which prints all the integer pairs in the list that repeat. If the list has more than one such pair, print all the pairs in consecutive lines in a sorted order. Sorting should be performed on the first integer of the pair.

Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings while reading the input or while printing, as these contribute to the standard output and test cases will fail.

Input Format:

• First Line has an integer, N.
• Second Line has N integers separated by single white spaces.

Output Format:

• The integer pairs which repeat are printed one in each line, sorted in ascending order.

Constraints:

• The list has at least one such integer pair.
• The occurrences of the repetitions must always be distinct.

Sample Input 1:

5

1 2 3 1 2

Sample Output 1:

1 2

Explanation 1:

Since 1 2 is repeating in the list, it forms a couple. Hence the output is 1 2.

13 hours ago

admin 1.9k

Sehore

Problem Solution

Repeating Integer Pairs Solution

Topics Involved / Prerequisites

• Array Traversal
• Tree Maps / Hash Maps (std::map)
• Pair Data Structures

Overview

The problem requires us to find all contiguous sub-arrays of length 2 (integer pairs) that appear more than once in the given list. We also need to print them sorted by their first integer.

Using a highly structured associative container like std::map in C++ is perfect for this. It allows us to use a std::pair as a key to count frequencies, and because std::map is implemented as a balanced binary search tree, it automatically keeps our pairs sorted lexicographically (first by the first element, then by the second).

Approach

1. Pair Extraction and Counting

We iterate through the input array from the first element up to the second-to-last element. At each step i, we extract the adjacent pair (arr[i], arr[i+1]). We use this pair as a key in our std::map and increment its frequency counter.

2. Automatic Sorting

Because we are inserting into a std::map<pair<int, int>, int>, the C++ standard library automatically sorts the keys. If two pairs have different first elements, they are sorted by the first element. If they have the same first element, they are sorted by the second.

3. Output Filtering

Once we have processed the entire array, we iterate through the map. If a pair's frequency is strictly greater than 1, it means it is a repeating pair, and we print it.

Code Implementation (C++)

#include <vector>
#include <map>
using namespace std;

vector<pair<int, int>> findFrequentPairs(const vector<int>& arr) {
    int n = arr.size();
    map<pair<int, int>, int> pair_counts;

    // Count adjacent pairs
    for (int i = 0; i < n - 1; i++) {
        pair_counts[{arr[i], arr[i + 1]}]++;
    }

    // Store result
    vector<pair<int, int>> result;
    for (const auto &item : pair_counts) {
        if (item.second > 1) {
            result.push_back(item.first);
        }
    }

    return result;
}

Time and Space Complexity

• Time Complexity: O(N log N) — We iterate through the array of N elements. Inserting a pair into a std::map takes logarithmic time, resulting in N log N overall operations.

Space Complexity: O(N) — In the worst-case scenario (all pairs are entirely unique), we will store N-1 pairs in the map, requiring linear extra memory.