Tuesday, December 11, 2012

TopCoder SRM 562 Div 2 250 pt

I haven't done TopCoder in quite some time. In fact, I haven't done much real coding in awhile. Most coding I've been doing is high level easy stuff. I want to get back to thinking algorithmically, so I'm going to start making myself do TopCoder practice problems every day. So here's the question link and my approach and code. 


My approach and solution

import java.util.Arrays;

public class CucumberMarket
public String check(int[] price, int budget, int k)
If any combination of k elements in price > budget then return NO, else YES

So need to build all possible combos of size k, check if the value is greater than budget.

This calls for a recursive solution.

Wait, we just need the k largest elements in price[] and then see if the sum > budget. So I can just sort the array

Arrays.sort(price); //sorts in ascending order
int sum = 0;
for(int i = price.length - 1; i >= price.length - k; i--)
sum += price[i];
if(sum > budget)
return "NO";
return "YES";

Code references
1. Java array sort - http://viralpatel.net/blogs/java-tip-how-to-sort-array-in-java-java-util-arrays/

No comments:

Post a Comment