November 30, 2021 Rookie SRM 7 Editorial
CheckbookRegister
This problem, like many easy problems in rookie SRMs, is really just a warm-up to get into the flow. In a single line, one can write out the code doing exactly what the problem statement requests:
public int updateBalance(int startingBalance, int debits, int checks) {
return startingBalance - debits - checks;
}
SumUnique
Here we need to be careful to count each number, but ignore if we’ve seen it before. We can do this in several different ways, either by keeping a list of numbers we have seen, perhaps by making a set, or even by sorting the list and looking for differences.
The solution below uses the sorting approach:
public int getSum(int[] values) {
Arrays.sort(values);
int ret = values[0];
for (int i = 1; i < values.length; i++)
if (values[i] != values[i - 1]) ret += values[i];
return ret;
}
PackageSizes
This is a classic dynamic programming type of problem. For any given total, we can imagine choosing if our “last” package purchased was of size1, size2, etc. If we already know the best answer for each of the smaller totals, we can then pick whichever option is most optimal. In this way, we can start at 0 and work our way up to total. We need to keep in mind returning -1 in cases that aren’t possible, and we do this with a large sentinel value:
public int getMinimum(int[] sizes, int total) {
if (total == 0) return 0;
int[] min = new int[1001];
for (int i = 1; i <= 1000; i++) {
min[i] = 9999;
for (int j = 0; j < sizes.length; j++)
if (sizes[j] <= i)
min[i] = Math.min(min[i], min[i - sizes[j]] + 1);
}
return min[total] < 9999 ? min[total] : -1;
}
KassanErinn
Guest Blogger