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.
Not better than O(n), but you can still get more efficient. You can build and use a map in a single pass.
for(inti=0;i<trips;i++){intmoney=scan.nextInt();intflavors=scan.nextInt();int[]prices=newint[flavors];for(intj=0;j<flavors;j++){prices[j]=scan.nextInt();}HashMap<Integer,Integer>possibleSolutions=newHashMap<Integer,Integer>(flavors/2);// Key = price that will solve the problem, Value = the flavor id (base 0) having money-neededPricefor(intk=0;k<flavors;k++){if(prices[k]<money){if(possibleSolutions.containsKey(prices[k])){// solution foundSystem.out.println((possibleSolutions.get(prices[k])+1)+" "+(k+1));break;}else{// add as possible solutionpossibleSolutions.put(money-prices[k],k);}}}}
Ice Cream Parlor
You are viewing a single comment's thread. Return to all comments →
Not better than O(n), but you can still get more efficient. You can build and use a map in a single pass.