Problem Link - Modular Pitfalls in Number theory
Problem Statement:
You are given an array arr consisting of N integers. Your task is to compute the sum of the squares of the elements in the array, and then return the result modulo 10^9+7.
Approach:
- Modular Arithmetic: Since the numbers can be very large (up to 10^{18}, and squaring them could result in even larger numbers, we must handle computations with modulo 10^9+7 to avoid overflow.
- For each number in the array compute their modulo so that you can compute their squares efficiently.
- Iterate through the array, compute the square of each element, and take the modulo at every step to avoid overflow and store it in
sum.
Complexity:
- Time Complexity:
O(N)Iterating through the array once to compute the sum of squares - Space Complexity:
O(1)No extra space required.