Discussion on Down to Zero II Challenge

2 years ago+ 0 comments

The challenging part of this problem is actually understanding the ask from the author. If the question writer was perhaps more clear in expressing his intent, this would not be such a challenging problem.

Here's my attempt at the simple explanation of the problem. Hopefully I am more clear than the author.

Problem Statement:

Given a number n, dermine if it is a prime number.
If it is a prime number, decrement the number by 1, and this is next.
OR if it is not a prime number, find the 2 factors (a,b) of the number such that gives a > b, and a will be next. There are many a,b factors for n, but you want to chose the smallest a,b to give the fastest converge to 0. The ideal a,b set is where a=sqrt(n). If you cannot find a natural sqrt, then take the factor of "a" closest above the sqrt(n).
Continue to next as n, repeating #2 and #3 above choices until 0 is reached.
count the number of iterations it takes to get to 0.

Analysis:

2 ways to solve it: a. recurse backwards OR b. precompute forward and look up.
Because there can be 1000 queries and N is limited to 10^6 and the answer is fixed for each n. precompute is best since it will only take 10^6 integers.
So if you precompute and solve the simple n=4 and n=3 case, you will solve all the cases.
The precompute just works opposite from the recurse logic.
You do not have to compute primes, since a prime number is a number where the forward sweep will not update by the factor method, but rather by n-1.

Here's a my solution in C++

Hopefully it's clearer to read, and the debug printfs help undersand the solution. To see the code work, uncomment the

#define DEBUG

... and test answers on a custom input where n < 25 or a small number to read so you can read the intent of the code.

//#define DEBUG

#ifdef DEBUG
#define MAX 25
#define _printf printf
#else
#define MAX 1000000
void _printf(...) {}
#endif

int find_max_multiple(int n) {
    int i = n-1;
    int a,b;
    set<int> multiples;
    while (i > 0) {
        a=i;
        b=n/a;
        if (n%i == 0) {
            multiples.insert(max(a,b));
        }
        i--;
    }
    // n has factors, return lowest factor to get largest drop
    i = *(multiples.begin());

    // n is prime, return itself
    if(multiples.size() == 0) {
        i=n;
    }
    return i;
}
void print_path(int* map, int n) {
    int i=n;
    int next=0;
    _printf("path for n %d [", n);
    while(i>0){
        if (i != n) {
            _printf(" %d ", i);
        }
        int a = find_max_multiple(i);
        if (map[i-1] < map[a]) {
            next = i-1;
        } else {
            next = a;
        }
        i=next;
    }
    _printf("0]\n");

}

void init_map(int* map) {
    int sqrt_max = sqrt(MAX);

    // init map with n=n-1 case, where no factor is considered
    for (int i=0; i <= MAX; i++) {
        map[i] = i;
    }

    // update for n= (a*b where a>b and a of n=a*b) is next decrement step
    for (int i=1; i < MAX; i++) {
        int score = map[i] + 1;
        _printf("eval i at map[%d] +1 = score %d\n",i,score);
        int limit;

        // i+1 is a prime with no factors, while i is not prime and has
        // lower score
        if (map[i+1] > score) {
            _printf("n-1 case map[%d+1]=%d>score=%d (i+1)=%d is a prime\n",i,map[i+1],score,i+1);
            map[i+1] = score;
        }

        // updating factors of i, updating those to the limit.
        if (i > sqrt_max) {
            _printf("limiting i %d > sqrt_max %d max %d\n", i, sqrt_max, MAX);
            limit = MAX;
        } else {
            limit = i*i;
            _printf("limit %d = %d^2\n", limit, i);
        }
        _printf("looping j %d to set to the limit %d inc by i %d\n", i*2, limit, i);
        for (int j = i+i; j <= limit; j += i) {
            if (map[j] > score) {
                _printf("a*b case map[%d] %d > score %d..saving smaller\n", j, map[j], score);
                map[j] = score;
            }
        }
    }

#ifdef DEBUG
    for(int i=0; i<MAX; i++) {
        _printf("map[%d] %d\n",i,map[i]);
    }
#endif    

}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int q;
    cin >> q;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    int map[MAX + 1];
    init_map(map);

    for (int q_itr = 0; q_itr < q; q_itr++) {
        int n;
        cin >> n;
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        int result = map[n];
        fout << result << "\n";
#if DEBUG        
        print_path(map,n);
#endif        
    }

    fout.close();

    return 0;
}