0

I have to come up with an algorithm that adds elements of two big arrays(size of each array is 10⁹ of integers that can go up to 10⁹). When declaring two arrays in java with size of 10⁹ each, I get a memory exception! The problem statement: http://bit.ly/1XWbUca

Oussama Achech
  • 131
  • 1
  • 11
  • The Question being -? How much memory did you allow your JVM? – greybeard Sep 12 '15 at 08:49
  • I use an on line compiler , the one on hackerrank – Oussama Achech Sep 12 '15 at 08:50
  • 1
    Well, if you give us more background, we might show you you don't really need such big arrays (if it is the case) – amit Sep 12 '15 at 08:53
  • Then don't: execute the code on your own machine, with enough memory allocated to the JVM. You'll need something like 8 GB of memory to have two arrays of integers that large. If you want to store the result in another array, then add 4 more GB. What are you trying to achieve? – JB Nizet Sep 12 '15 at 08:53
  • 4
    `hackerrank`: if you are doing https://www.hackerrank.com/challenges/a-very-big-sum, read the problem statement again. Provide a link to the original problem statement _in the question itself (a sound practice, anyway). – greybeard Sep 12 '15 at 08:56
  • I am trying to calculate the result of (a1∗b1)+(a2∗b2)+...+(aN∗bN) in modulo 1000000007 where a and b are my two arrays (N can reach 10⁹ ) and I am using an online compiler – Oussama Achech Sep 12 '15 at 09:03
  • 1
    (1) How is the input given? You don't need to store at least one array, depending on how the input is given – amit Sep 12 '15 at 09:06
  • http://bit.ly/1XWbUca – Oussama Achech Sep 12 '15 at 09:12
  • _Do not comment comments asking for information missing. Put complementary information in the question proper._ – greybeard Sep 12 '15 at 09:20
  • So, differentiate between `Ikbal` (having arrays) and solving the problem (200000 operations). And, by all means, mention _modular arithmetic_ in the question proper, if not in the title. – greybeard Sep 12 '15 at 09:26
  • are you saying that the problem is in the modulus operator not the memory allocation ? – Oussama Achech Sep 12 '15 at 09:38
  • can you provide hackerrank link of the problem instead of PDF link? – YoungHobbit Sep 12 '15 at 10:27
  • https://www.hackerrank.com/contests/worldcup/challenges/two-arrays-1 competition's name is World cup problem ikbal's arrays – Oussama Achech Sep 12 '15 at 10:54

1 Answers1

0

by analyzing the input constraints you can see that you can get 2*10^5 * 10^9 array accesses in the worst case if you implement the solution using two arrays of ints. So that approach will not do. If you somehow solve your MLE error, you will almost certainly get TLE.

There is another way... there is another option :)

you only have 200k operations, that means, you only have to pay attention to 2*200k points (for each operation you have start and end index). If you keep your operations in the sorted array of pairs , where ind is starting or ending index of operation and value is positive for starting index and negative for ending index.

Answering the query can be done by looping through that array and keeping a sum variable to which you add a value for each ind,value pair you encounter.

While that approach is marginally better, because it can add a value to the segment of an array in O(1) it still requires O(n) for queries in the worst case.

So, I imagine the custom segment tree implementation is the way to solve this one.

I don't know much about it, but you can look it up.

Basically, segment tree will store all your segments in a tree-like data structure, that means the access and deletion of elements/segments takes O(log n) time... which is good. Segments in this case would be the range of particular operation (start index, end index). Each node of the tree would also keep a value that you should add to that segment.

And you would have one segment tree for both arrays.

Since I don't know what I'm talking about, you can check someone who does.

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
Tawcharowsky
  • 615
  • 4
  • 18