algoadvance

Leetcode 2748. Number of Beautiful Pairs

Problem Statement

Given a positive integer array nums, return the number of pairs (i, j) (where i < j) such that the combination of the first digit of nums[i] and the last digit of nums[j] form a beautiful pair.

A pair (num1, num2) is considered beautiful if the sum of the two digits is a prime number.

Example

  1. Input: nums = [12, 34, 56, 78] Output: 4 Explanation: Pairs are (12, 34), (12, 56), (34, 56), (34, 78). The valid pairs are those with prime sums.

  2. Input: nums = [11, 42, 33, 90] Output: 2 Explanation: Pairs are (11, 42), (11, 33), (11, 90), (42, 33), (42, 90), (33, 90). The valid pairs are those with prime sums.

Clarifying Questions

  1. Definition of beautiful pair: Are beautiful pairs specifically defined as the sum of their first and last digits being a prime number?
  2. Number constraints: What is the possible range for the numbers, and how large can the array be?
  3. Prime number check: Do we need to precompute primes up to a certain number or can we assume we are allowed to compute primes during execution?

Strategy

  1. Extract Digits:
    • Extract the first digit of nums[i] and the last digit of nums[j].
  2. Prime Check:
    • Determine if the sum of these digits is a prime number. Precompute prime numbers up to a reasonable limit.
  3. Count Valid Pairs:
    • Use nested loops to generate pairs (i, j) where i < j and check if they form a beautiful pair.
  4. Optimization:
    • Primes are limited in the sum range (since we are dealing with single digits, the range is 2 to 18).
    • Use a boolean array to mark which sums are prime for quick lookup during the loop.

Code

Here’s a sample implementation in Java:

import java.util.ArrayList;
import java.util.List;

public class BeautifulPairs {
    private static boolean[] primes;

    public static int numberOfBeautifulPairs(int[] nums) {
        primes = new boolean[19];
        sieveOfEratosthenes(18);
        
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int firstDigit = getFirstDigit(nums[i]);
            for (int j = i + 1; j < nums.length; j++) {
                int lastDigit = getLastDigit(nums[j]);
                if (primes[firstDigit + lastDigit]) {
                    count++;
                }
            }
        }
        return count;
    }

    private static int getFirstDigit(int num) {
        while (num >= 10) num /= 10;
        return num;
    }

    private static int getLastDigit(int num) {
        return num % 10;
    }

    private static void sieveOfEratosthenes(int max) {
        primes[2] = true; // Only set 2 directly, as all other indexes default to false
        for (int i = 3; i <= max; i++) {
            primes[i] = isPrime(i);
        }
    }

    private static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false; 
        }
        return true;
    }

    public static void main(String[] args) {
        int[] nums1 = {12, 34, 56, 78};
        System.out.println(numberOfBeautifulPairs(nums1)); // Output: 4

        int[] nums2 = {11, 42, 33, 90};
        System.out.println(numberOfBeautifulPairs(nums2)); // Output: 2
    }
}

Time Complexity

Overall, this results in a time complexity of O(n^2) for this problem with efficient constant-time operations inside the nested loop.

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