algoadvance

Leetcode 3184. Count Pairs That Form a Complete Day I

Problem Statement

Given an array of integers arr and an integer k, find the number of unique pairs (i, j) (where i < j) such that the sum of arr[i] and arr[j] forms a “complete day”. A “complete day” occurs when the sum of two elements is divisible by k.

Example

Clarifying Questions

  1. Can the array contain negative numbers or zero?
    • Yes, the array can contain any integer values including zero and negative numbers.
  2. Can the array contain duplicate values?
    • Yes, duplicate values are allowed.
  3. Are elements in the input array guaranteed to be finite?
    • Yes, for practical purposes the input array will contain a finite number of integers.
  4. Is there any constraint on the size of the array?
    • The array can be very large, so the solution needs to be efficient.

Strategy

  1. Brute Force Approach:
    • Iterate over all pairs of elements in the array.
    • Count pairs where the sum is divisible by k.
    • This approach has a time complexity of (O(n^2)), which can be inefficient for large arrays.
  2. Optimized Approach using Remainder Buckets:
    • Use an array or a HashMap to count the frequency of remainders when elements are divided by k.
    • Iterate through the array once to populate the remainder count.
    • For each pair of remainders r and k-r, compute the number of valid pairs.
    • Handle special cases where remainders are 0 or k/2 (if k is even).

Code

Here’s the Java implementation of the optimized approach:

import java.util.HashMap;
import java.util.Map;

public class CompleteDayPairs {
    public int countPairs(int[] arr, int k) {
        // Map to store remainder frequencies
        Map<Integer, Integer> remainderCount = new HashMap<>();

        // Populate the remainder count
        for (int num : arr) {
            int remainder = (num % k + k) % k; // Handle negative numbers
            remainderCount.put(remainder, remainderCount.getOrDefault(remainder, 0) + 1);
        }

        int count = 0;

        // Iterate through the remainder keys
        for (int rem : remainderCount.keySet()) {
            int complement = (k - rem) % k;

            // Special case: remainder 0 can only pair with itself
            if (rem == 0 || rem == complement) {
                int freq = remainderCount.get(rem);
                count += (freq * (freq - 1)) / 2; // Combination formula: nC2 = n*(n-1)/2
            } else if (rem > complement) {
                // Count pairs rem and complement
                count += remainderCount.get(rem) * remainderCount.getOrDefault(complement, 0);
            }
        }

        return count;
    }

    public static void main(String[] args) {
        CompleteDayPairs solution = new CompleteDayPairs();
        int[] arr = {1, 2, 3, 4, 5};
        int k = 3;
        int result = solution.countPairs(arr, k);
        System.out.println("Number of pairs: " + result);  // Output: 4
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI