Rodrigo Burgos Dominguez
BAN USERYour welcome, try with this input
A= {2, 3, 4}
sum = 5
I think is necessary use a dynamic programming or best first search to find all possibilities.
Good look!
public String compareTwoReleaseVersion( String version1, String version2){
String splitV1[] = version1.split("\\.");
String splitV2[] = version2.split("\\.");
for( int pos = 0; pos < splitV1.length && pos < splitV2.length ; pos++){
if( splitV1[ pos ].compareTo( splitV2[ pos ] ) > 0 ) return version1;
if( splitV1[ pos ].compareTo( splitV2[ pos ] ) < 0 ) return version2;
}
return ( splitV1.length > splitV2.length ) ? version1 : version2;
}
Hi punnet.sochi, I think your idea is great but if we have this input
A = {2 , 4}
and the sum = 5
you find 4 , and then 5 - 4 = 1 , but you don't have any 1.
Your idea work well if they use as a input the first kth fibonacci number , or something like that.
Best regards.
another way to ge it:
import java.util.*;
class Main{
public static void main(String arg[]){
Scanner scan = new Scanner(System.in);
int size;
while( (size = scan.nextInt()) != 0 ) {
int sum = scan.nextInt();
int []input = new int[ size ];
for( int x = 0; x < size; x++) input[ x ] = scan.nextInt();
System.out.println( "" + ( (new Main()).solve( input , sum ) ) ) ;
}
}
class SumInformation{
private Integer sum;
private Integer distance;
private Integer operation;
public SumInformation( int sum, int distance, int operation){
this.sum = sum;
this.distance = distance;
this.operation = operation;
}
public int getDistance(){
return this.distance;
}
public int getSum(){
return this.sum;
}
public int getOperation(){
return this.operation;
}
}
public int solve( int A[], int S){
Queue<Integer> queue = new LinkedList<Integer>();
HashMap<Integer, SumInformation> hashInformation = new HashMap<Integer, SumInformation>();
queue.add( S );
hashInformation.put( S, new SumInformation( S, 0, 0 ));
while( !queue.isEmpty() ) {
Integer sum = queue.poll();
Integer distance = hashInformation.get( sum).getDistance();
if( sum == 0 ) {
while( sum != S ) {
Integer operation = hashInformation.get( sum).getOperation();
System.out.println(" " + sum + " previous operation " + (-operation));
sum += -operation;
}
return distance;
}
for( int position = 0; position < A.length; position++){
int sign = -1;
Integer sumtmp = sum + sign * A[ position ];
SumInformation inf = hashInformation.get( sumtmp );
if( sumtmp < 0 ) continue;
if( inf != null ) continue;
hashInformation.put( sumtmp , new SumInformation( sumtmp, distance + 1, sign * A[ position ] ) );
queue.add( sumtmp);
}
}
return -1;
}
}
boolean vis[][];
int din[][];
final static int INF = 1000000000;
int getMin( int position, int A[], int sum){
if( position == A.length || sum < 0 ) return INF;
if( sum == 0) return 0;
if( vis[position][ sum ] == true) return din[ position ][ sum ];
vis[ position ][ sum ] = true;
din[position][ sum ] = INF;
if( A[ position ] > 0 ){
din[position][ sum ] = Math.min( din[ position][sum], getMin( position , sum - A[ position ]) + 1);
}
din[ position ][ sum ] = Math.min( din[position][sum], getMin( position + 1, sum ) );
return din[ position ][ sum ];
}
int solve( int []A, int S){
vis = new boolean[ A.length ][ S + 1];
din = new int[A.length][ S +1];
int res = getMin( 0, A, S);
return ( res >= INF ) ? -1 : res;
}
I think the correct answer is 3 + 2 = 5.
- Rodrigo Burgos Dominguez April 02, 2014May be exist another way to find a correct solution.
Good look!