Sign In Sign Up Ask an AI advisor
TYUqnn2077
TYUqnn2077
13.04.2021 • 
Mathematics

Right now you are doing a complete search over the prefix sums. However, this is not necessary. We know that the only way to get a multiple of $7$ is if both prefix sums have the same remainder $\pmod{ 7}$. Then, what happens if there are a lot of these prefix sums with the same remainder. If they're located at indexes $a_1,a_2,a_3,... ,a_n$, your $O(n^2)$ solution is finding the maximum of all of the differences. But we don't need to check $a_2-a_1$, for example, since we know $a_n-a_1$ is divisible by $7$, and it must be larger. Thus, we only have to find $a_1$ and $a_n$, because all the other differences must be smaller. This means that for each remainder from $0$ to $6$, we can calculate $a_1$ and $a_n$, and find the maximum of their difference, which will be an $O(n)$ solution.

Solved
Show answers

Ask an AI advisor a question

I want advice