Is better than O(n^2) possible for getting pairs that sum to a multiple of 10? Is it possible to solve a problem with a worse case less than $O(n^2)$, when the input is an an array of numbers and the output is all pairs that sum to a number divisible by 10?  for example

int [] a = {1, 2, 15, 25, 28};
// would produce [2, 28], [15, 25]


I don't think so because when all sums are divisible by 10 then the total number of pairs is $n(n-1)/2$ which is $O(n^2)$.

int [] a = {5, 15, 25, 35, 45};
// n(n-1)/2 = 5(4)/2 = 10
// pairs [5, 15], [5, 25], [5, 35], [5, 45], [15, 25], [15, 35], [15, 45], [25, 35], [25, 45], [35, 45]
It is not possible to have an algorithm that is faster than $O(n^2)$ as the output can be $O(n^2)$ — all pairs. This can happen when all numbers are divisible by 10, or all are returning 5 when taken modulo 10.