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