To solve this problem, we need to count the number of pairs (i, j) in an array such that i < j and the sum of elements at positions i and j is divisible by 3.

Approach

The key insight here is to use the properties of remainders when divided by 3. For the sum of two numbers to be divisible by 3:

1. Either both numbers have a remainder of 0 when divided by 3 (since 0 + 0 = 0 mod 3).
2. Or one number has a remainder of 1 and the other has a remainder of 2 (since 1 + 2 = 3 mod 3 = 0).

We can break down the solution into the following steps:

1. Count Remainders: Categorize the elements of the array into three groups based on their remainder when divided by 3:
   • count0: Number of elements with remainder 0.
   • count1: Number of elements with remainder 1.
   • count2: Number of elements with remainder 2.
2. Calculate Valid Pairs:
   • Pairs from count0: Choose any two elements (combination of 2 elements from count0).
   • Pairs from count1 and count2: Multiply the count of elements in count1 with the count of elements in count2.

Solution Code

n = int(input())
a = list(map(int, input().split()))
count0 = count1 = count2 = 0

for num in a:
    rem = num % 3
    if rem == 0:
        count0 += 1
    elif rem == 1:
        count1 += 1
    else:
        count2 += 1

result = (count0 * (count0 - 1) // 2) + (count1 * count2)
print(result)

Explanation

1. Count Remainders: We iterate through the array and count how many elements fall into each remainder category (0, 1, or 2).
2. Valid Pairs Calculation:
   • Pairs from count0: The number of ways to choose 2 elements from count0 is given by the combination formula C(n, 2) = n*(n-1)/2.
   • Pairs from count1 and count2: Each element in count1 can pair with each element in count2, so the number of such pairs is count1 * count2.

This approach efficiently computes the result in O(n) time complexity, where n is the number of elements in the array, making it optimal for large inputs.

Example: For the array [1,2,3,4,5,6], the remainders are [1, 2, 0, 1, 2, 0]. The count0 is 2, count1 is 2, count2 is 2. The result is (21//2) + (22) = 1 +4 =5, which is correct.

This solution is both time and space efficient, ensuring it handles the problem constraints effectively.

作者声明:本文包含人工智能生成内容。