in COINS problem, i am getting java.lang.OutOfMemoryError

general
, , ,
1

problem COINS link

    /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package PracticeMedium;

import java.util.Scanner;

/**
 *
 * @author Hemant Dhanuka
 */
class COINS {

    long maximumvalue[] = new long[500000001];
    // maximumvalue=new long[1000000001];

    public static void main(String[] args) throws Exception {

        COINS c = new COINS();
        c.calculateMaxforEachNo();

        // calculateMaxforEachNo();
        Scanner s = new Scanner(System.in);
        while (s.hasNextInt()) {
            int numberWrittenOnCoin = s.nextInt();
            System.out.println(c.maximumvalue[numberWrittenOnCoin]);
        }
    }

    private void calculateMaxforEachNo() {
        for (int i = 0; i < maximumvalue.length; i++) {
            int n1 = i / 2;
            int n2 = i / 3;
            int n3 = i / 4;
            long checkingmax = maximumvalue[n1] + maximumvalue[n2] + maximumvalue[n3];
            if (checkingmax > i) {
                maximumvalue[i] = checkingmax;
            } else {
                maximumvalue[i] = i;
            }
            //  System.out.println(i);
        }
    }
}

i am getting error as as–
Exception in thread “main” java.lang.OutOfMemoryError: Java heap space
at COINS.(COINS.java:15)
at COINS.main(COINS.java:19)
C:\Users\Hemant Dhanuka\AppData\Local\NetBeans\Cache\8.1\executor-snippets\run.xml:53: Java returned: 1
BUILD FAILED (total time: 0 seconds)

is there anyother solution in which i will not encounter this heapMemoryFinishedError…
or Tell me what modification i do to run successufully my program and submit it on codechef accurately

2

Basically it means that you ran out of memory. The most common reason for this is if the size of array is too large (~10^8 - 10^9…tho it depends and varies from place to place)

I recommend that you try changing size of your array. Is the error occurring even after reducing array size to 10^6 or 10^7? Get back to me with that.

BTW- More info And Possible Fix

3

bro i know why problem occouring becose of heap memory is small as compared to my array size… but now problem is how to overcome this problem without changing size of array… means in problem i have to check upto 10^9… i can’t change limits…

4

If you’re running it on your system, then have you tried- (given in link)

“java -Xmx2048m [whatever you’d have written before]”

If online judge is throwing this error, then try switching to maps, tables.

5

For the solution, you don’t need to calculate for all the numbers. Instead use a recursive approach like

Max(n) = max(n/2)+max(n/3)+max(n/4)

With some suitable base case.
Then memoize with a HashMap.
This solution should work as in actuality, you don’t need to calculate for all the numbers.

Also, you can under no condition store more than approx 10^8 values.so if you ever find yourself an array or any data structure of that size,our solution is wrong.

2 Likes
6

@rajarshi_basu has given a nice answer, however just to show how much memory you are trying to allocate:
long maximumvalue[] = new long[500000001];
500000001 * 8 bytes
= 4000000008 bytes
= 3906250 KB
= 3814 MB
= 3.8 GB
So your program would required 3.8 GB for your maximumvalue array, which is way beyond the memory limit.

2 Likes
7

@rajarshi_basu @meooow while memorizing in hashmap it will also use upto 3.8 gb of memory as hashmap also use continious memory block as bucket hashing concept… so in hashmap also memory overflow