[Java] [BFS]


  • 0
    T

    Was not able to figure out that DP could be used. Came up with a BFS straightforward way.

    Created new wrapper class called node. From every node either the previously copied number of 'A' could be used for to generate next set of 'A's or the whole of current 'A' could be used. This leads to the formation of a binary tree kind of structure.

    To eliminate checking unnecessary conditions, few checks have been used inside the loop.

    PS: comments appreciated.

    public class Solution {
        public int minSteps(int n) {
            Queue<node> l = new LinkedList<node>();
            if(n==1) return 0;
            l.offer(new node(2,1,2));
            while(!l.isEmpty()){
                node b  = l.poll();
                if(b.x == n) return b.cur;
                if(b.x+b.prev <= n)
                    l.offer(new node(b.x+b.prev,b.prev,b.cur+1));
                if(b.x*2 <= n)
                l.offer(new node(b.x*2,b.x,b.cur+2));
            }
            return -1;
            
        }
    }
    class node{
        int x;
        int prev;
        int cur;
        public node(int a, int b, int c){
            x = a;
            prev = b;
            cur = c;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.