Abhiroop Sarkar Abhiroop Sarkar - 12 days ago 5
Java Question

Finding least number of moves

I have the following problem statement:


Given a number n (1 < n < 10^9), what is the least number of
mathematical operations from the set (divide n by 2, divide n by 3,
subtract 1 from n) that can be used to transform the number n to 1?


I have written the following code so far in an attempt to solve the problem:

while(n!=1){

if(n%3==0 || n%2==0){
if(n%3==0){
n=n/3;
c=c+1;
}
if(n%2==0){
n=n/2;
c=c+1;
}
}
else{
n=n-1;
c=c+1;
}
}
System.out.println(c);


But I dont get the desired output. Can someone help me with it.

Answer

The simplest solution might be to explore all possibilities.

public static ArrayList<Integer> solve(int n, 
  ArrayList<Integer> moves, int bestMove,HashMap<Integer,Integer> memory) {

        if (moves.size() >= bestMove) return null;
        if (n == 1) return moves;
        Integer sizeOfPathN= memory.get(n);

        if (sizeOfPathN!=null && sizeOfPathN<=moves.size())return null;
        memory.put(n,moves.size());

        int size_1=Integer.MAX_VALUE, size_2 = Integer.MAX_VALUE, size_3 = Integer.MAX_VALUE;
        ArrayList<Integer> moves3 = null, moves2 = null, moves1;

        if (n % 3 == 0) {
            ArrayList<Integer> c = new ArrayList<Integer>(moves);
            c.add(3);
            moves3 = solve(n / 3, c,bestMove,memory);
            if (moves3!=null)
            size_3 = moves3.size();
        }

        bestMove = Math.min(bestMove, size_3);

        if (n % 2 == 0) {
            ArrayList<Integer> c = new ArrayList<Integer>(moves);
            c.add(2);
            moves2 = solve(n / 2, c,bestMove,memory);
            if (moves2!=null)
            size_2 = moves2.size();
        }

        bestMove = Math.min(bestMove, size_2);


        ArrayList<Integer> c = new ArrayList<Integer>(moves);
        c.add(1);
        moves1 = solve(n - 1, c,bestMove,memory);
        if (moves1!=null)
        size_1 = moves1.size();

        int r = Math.min(Math.min(size_1, size_2),size_3);
        if (r==size_1) return moves1;
        if (r==size_2) return moves2;

        return moves3;

    }

Explanation:

n : n

moves : An ArrayList containing the movements. (for printing pourposes)

bestMove : value containing size of the minimal solution found.

memory : a HashMap containing the "state" explored previously and the length of the path.

If we call public static void main(String[] args) {

    long a = System.currentTimeMillis();
    Object[] sol=solve(10, new ArrayList<Integer>(),Integer.MAX_VALUE,new HashMap<Integer,Integer>()).toArray();
    System.out.println(sol.length);
    System.out.println(Arrays.toString(sol));
    System.out.println((System.currentTimeMillis()-a));
}

The output would be:

3
[1, 3, 3]
1

Equivalent to n-1, n/3,n/3 (@Tristan's best solution)

if we call it with 1000 000 000 as n:

30
[1, 3, 3, 3, 3, 1, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 1, 3, 2, 2]
55

If we call it with 11:

4
[1, 1, 3, 3]
1

EDIT: If only the number of moves it's needed:

public static int solve(int n,int moves,int bestMove,HashMap<Integer,Integer> memory) {

        if (moves >= bestMove) return Integer.MAX_VALUE;
        if (n == 1) return moves;
        Integer sizeOfPathN= memory.get(n);

        if (sizeOfPathN!=null && sizeOfPathN<=moves)return Integer.MAX_VALUE;
        memory.put(n,moves);

        int size_1=Integer.MAX_VALUE;
        int size_2 = Integer.MAX_VALUE;
        int size_3 = Integer.MAX_VALUE;

        moves=moves+1;
        if (n % 3 == 0) size_3 = solve(n / 3, moves,bestMove,memory);
        bestMove = Math.min(bestMove, size_3);      
        if (n % 2 == 0) size_2=solve(n >> 1, moves,bestMove,memory);

        bestMove = Math.min(bestMove, size_2);

        size_1 = solve(n - 1, moves,bestMove,memory);


        return  Math.min(Math.min(size_1, size_2),size_3);


    }

Calling this method with

long a = System.currentTimeMillis();
System.out.println(
     solve(1000 *1000*1000, 0,Integer.MAX_VALUE,new HashMap<Integer,Integer>()));

    System.out.println((System.currentTimeMillis()-a));

Output:

30
24

Fast enough

Comments