We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Down to Zero II
  5. Discussions

Down to Zero II

Sort by

recency

|

231 Discussions

|

  • ambuj_yadav_che1
     + 0 comments

    how is editorial code working q =10^5 n =10^6

    for each query we are doing memset so q*n then how is it working or is there anything that i am missing here

  • axmadjonovulugb1
     + 2 comments

    TESTCASES ARE WRONG. DONT BE SURPRISED. e.g: for 86 expected output is 7. but my output was 8: 86->43->42->7->6->3->2->1->0.!

  • vishnubabu94in
     + 0 comments

    js

    const map = { 0: 0, 1: 1 };
function downToZero(n) {
    for (let i = 2; i <= n; i++) {
        if (map[i]) continue;

        let a = 2;
        let min = map[i - 1];
        let b;
        while (a <= (b = i / a)) {
            if (Math.floor(b) === b) {
                min = Math.min(min, map[b]);
            }
            a++;
        }
        map[i] = min + 1;
    }
    return map[n];
}

  • Dmitry_Strakhov
     + 0 comments

    Here is my DP solution (C# code). Take a look:

    public static int DownToZero(int n) {
    return new DownToZeroSolution().Solve(n);
}
    
class DownToZeroSolution {
    static int calculated_N;
    static readonly int[] solutions;

    static DownToZeroSolution() {
        calculated_N = 1;
        solutions = new int[1_000_001];
        solutions[1] = 1;
    }
    public int Solve(int n) {
        if(n <= calculated_N) return solutions[n];

        for(int i = calculated_N + 1; i <= n; i++) {
            solutions[i] = CalculateItem(i);
        }
        calculated_N = n;
        return solutions[n];
    }
    static int CalculateItem(int n) {
        int min = solutions[n - 1];
        int d_start;
        int d_step;

        if((n & 1) == 1) {
            d_start = 3;
            d_step = 2;
        }
        else {
            d_start = 2;
            d_step = 1;
        }
        
        int topN = (int)(Math.Sqrt(n) + 0.1);

        // n = d1*d2
        for(int d1 = d_start; d1 <= topN; d1 += d_step) {
            if(n % d1 == 0)
                min = Math.Min(min, solutions[Math.Max(d1, n / d1)]);
        }
        return 1 + min;
    }
}

  • shridhar_thorat1
     + 1 comment

    I can't figure out how to fix this code. It only works for 2 tests. For the ones it fails it's usually just one more move than expected

    def downToZero(n):
    moves = 0
    while n != 0:
        a = 1
        b = 1
        if n == 1:
            n -= 1
            moves += 1
            break
        # calculate factors until a < b
        for num in range(n-1, 1, -1):
            if n % num == 0:
                a = num
                b = n // num
                if a < b:
                    break

        if (a == 1) or (a == n):
            n -= 1
        else:
            n = max(a, b)
        moves += 1

    return moves