Given an integer
x an array of n elements
[a1,a2,a3 ... an] (both of which will be taken from input stream) , we wish to find out
(x % a1) + (x % a2) + (x % a3) ... + (x % an).
x will be given after the taking array as the input.
Since this is part of a bigger problem, I want to find it out preferably in
O(1) time (excluding
O(n) time for taking in the array).
When I will take the input array, I will simultaneously calculate the sum of the complete array, and wish to bring it into a format similar to
(x % (a1 + a2 + a3 ... an)). Is there any identity similar to this?
This is not my actual problem. I just wish to meet my time complexity requirements. Once the array is taken as input, after that,
multiple numbers will be given … and I have to calculate the answer for each of them in O(1) time.
Source: Windows Questions C++