Abhiroop Sarkar - 1 year ago 85
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.

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);
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);
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);
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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download