0
\$\begingroup\$

The problem statement was pretty easy and I was able to run half of the test cases, but some of the test cases in the end gave me the error of memory limit reached. What can I do here to improve the memory efficiency of my code?

Question: Find the min number of "usable" integers required to reach the N. The "usable integers" are those that contain only 4 or 5 in their decimal representation, e.g. 4,5,455,545454.

So to reach 9, answer would be 2 (4+5) My approach: Creating a vector consisting of all usable numbers up to N and using dynamic programming solution on that vector to find the minimum number of elements required to reach N.

My code:

int getCount(int N) {
    vector<int> vec;vec.push_back(4);vec.push_back(5);
    int i = 0;int temp = 0; 
    while(true) {
        temp = vec[i] * 10 + 4;
        if(temp > N)
            break;
        vec.push_back(temp);
        temp = vec[i] * 10 + 5;
        if(temp > N)
            break;
        vec.push_back(temp);
        i++;
    }
    
    return getCountDP(vec,vec.size(),N);
}

int getCountDP(vector<int> vec,int size, int N){  

    int dp[size+1][N+1];

    for(int i = 0 ; i <= N; i++) {
        dp[0][i] = INT_MAX - 1;
    }
    
    for(int i = 0 ; i < size+1; i++) {
        dp[i][0] = 0;
    }

    for (int i = 1; i <= size; i++) { 
        for (int j = 1; j <= N; j++) { 
            if (vec[i - 1] > j) { 
                dp[i][j]= dp[i-1][j]; 
            } 
            else { 
                dp[i][j]= min(dp[i-1][j],dp[i][j-vec[i-1]]+1); 
            } 
        } 
    } 
    return dp[size][N]; 
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ This would benefit from having a complete program and also some clarification of the intent of the code. Is addition the only operation supported? \$\endgroup\$
    – Edward
    Jan 21, 2021 at 15:52
  • \$\begingroup\$ Yes addition is the only operation supported. The intent of the code is just to find the minimum no. of "usable" integers which sum up to N. The main() of the code just consisted of scanning N and sending it to the function getCount(int) so I felt like there was no real need for it. @Edward \$\endgroup\$
    – Martin
    Jan 22, 2021 at 8:35
  • \$\begingroup\$ Is there a limit on N? \$\endgroup\$
    – AJNeufeld
    Jan 22, 2021 at 15:12
  • \$\begingroup\$ yes, 0 < N < 10^6 @AJNeufeld \$\endgroup\$
    – Martin
    Jan 23, 2021 at 13:45
  • \$\begingroup\$ What dous dp[i][j] mean? What does i here for? Could you just make it dp[j]? \$\endgroup\$
    – tsh
    Jan 24, 2021 at 4:18

1 Answer 1

1
\$\begingroup\$

Since your question is about Memory Limit Exceed. And the most memory consumed item is dp. You are going to make your dp matrix smaller. Your current memory usage is \$O(2^{log_{10}n}\cdot n) = O(n^2)\$. And you need to reduce it to \$O(n)\$.

Let's write down your current dp function:

$$ dp_{i,j} = \min \{ dp_{i-1,j}, dp_{i, j-usable_i}+1 \} $$

First, consider you only need dp[i] and dp[i-1] during iteration. All previous rows are not necessarily any more. You may only declare two rows as dp1[N + 1] and dp2[N + 1]. (To make the logic for even and odd rows consistent, use two pointers point to these array.) By using this approach, memory usage may reduced into \$O(2n) = O(n)\$.

Another approach may be just reduce your dp function into 1 dimension:

$$ dp_{j} = \min_{n \in usable} \{dp_{j-n}\} + 1 $$

So, you may only maintain dp[N + 1] instead. This also cost \$O(n)\$ memory. The second approach also make the array reusable when this function is invoked later. If you are going to handle multiple testcases in one run. You may simply declare it as global variable dp[MAX_N + 1] to reduce its time consume.

#include <stdio.h>

const int MAX_N = 1000000;
const int MAX_VAL = 128; // 2 ^ (log10(MAX_N) + 1)

int getCount(int n) {
  static int filled = 0;
  // values hold all numbers only contais 4 or 5 in 0 ~ 1e6
  static int values[MAX_VAL] = {4, 5};
  // steps is the array for dp
  // steps[i] = min(steps[i - values[j]] + 1 for every j)
  static int steps[MAX_N];
  int i, j, step, min_step;
  if (n > MAX_N) return -1; // We do not support input > 1e6
  // When first time run, we fill all values
  if (filled == 0) {
    for (i = 2, j = 0; i < MAX_VAL; j++) {
      values[i++] = values[j] * 10 + 4;
      values[i++] = values[j] * 10 + 5;
    }
    steps[0] = 0;
    filled = 1;
  }
  for (i = filled > 1 ? filled : 1; i <= n; i++) {
    // We use MAX_N+1 for values cannot be reached
    min_step = MAX_N + 1;
    for (j = 0; values[j] <= i; j++) {
      step = steps[i - values[j]] + 1;
      if (step < min_step) min_step = step;
    }
    steps[i] = min_step;
  }
  filled = n;
  if (steps[n] > n) return -1;
  return steps[n];
}

int main() {
  int n;
  for (n = 0; n < MAX_N; n++) {
    printf("%d\n", getCount(n));
  }
}

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.