PWC 056: Task #1, Diff-K & Task #2, Path Sum
After posting two separate blogs for PWC 055 and seeing how awkward the explanations were, I'll try a new tack: Both submissions will be elaborated in one blog post. The elaborations will not be explanations. I'll focus more on the "idea" part and let any programming details come out in the comments, if at all.
InputFor input I decided that all the numbers in the array would be command line arguments. That meant that 'k' would have to be a command line option. There was some validation that the stated requirements were met.
One input requirement "given an array @N of positive integers (sorted)" seemed to say that the input array should be sorted. The algorithm I chose worked without any sorting requirement on input, so this was not checked.
Case 1: k > 0Basically, take your input values and then create another array that is the input array with an element-wise subtraction by k. Take the intersection of these two arrays. Any elements in the intersection are the A[j] in the desired relation, A[i] - A[j] = k. By construction, we also know we have A[i] in the input array as well. Some bookkeeping is needed to track the indices, but it's not too bad.
Case 2: k = 0This is where the i != j requirement comes into play. This case basically lists off all the groups of non-unique elements in pair-wise fashion.
This is about the nicest binary tree exercise for people, like myself, who never had a formal comp sci class which forced them to write one from scratch. The tree doesn't have to be balanced, nor does it have to be sorted.