Minimum steps to reach a target by adding a divisor at each step

So currently I'm stuck at a question. First I'll give the question below, then I'll give my own algorithm for solving it, but the problem is that it is too slow. Any help would be appreciated.

Question:

Assume numbers a and b such that a <= b, if we were to add the divisors of a number consecutively to itself, what is the minimum amount of steps required to get to number b.

a = 4, b = 24 => 4 -> 6 -> 9 -> 12 -> 18 -> 24

This is the code that I've written for the above question.

#include <iostream>  #define SIZE 100001  int main() {      int a, b;      std::cin >> a >> b;      int array[SIZE] = {0};      array[b] = 0;      for (int i = b - 1; i >= a; i--) {          int min = INT32_MAX;          for (int j = b; j > i; j--) {              int difference = j - i;              if (i % difference == 0 && min > array[j] && array[j] != -1 && difference != 1 && difference != i) {                  min = array[j];              }          }          if (min == INT32_MAX)              array[i] = -1;          else              array[i] = min + 1;      }        std::cout << array[a];  }    

As you can see I've used dynamic programming to solve the question, and the output is correct, but the code is too slow. Can you guys help me with improving its speed?

Constraints:

4 <= a <= b <= 100000

Memory limit = 256 mB

Time limit = 1 second

https://stackoverflow.com/questions/65876704/minimum-steps-to-reach-a-target-by-adding-a-divisor-at-each-step January 25, 2021 at 06:30AM