Gang of Misfits and Their Arithmetic Progressions

19 Mar, 2023

If you have been following this series, you know that the way I approach these problems is to solve them on paper first for a couple of reasons:

1. to find a general pattern
2. to reduce the complexity of the problem in my head

As a result, the patterns are as deterministic as the compiler that solves the problem. Of course, I sort of have developed an intuition by now, in which I can immediately pinpoint, which mathematical approach I want to use. And there's no secret to it, other than looking at the data structure, just as we do in algebra. For example, if the task passes as input, an array of integers, I intuitively know that a linear equation is on order.

To find the patterns, I ask myself: what is the relationship between the data and the desired result. After that, it is just a matter of pulling a stubby pencil, some paper, and solve this thing analogically, before committing to its digital brethren. Enough yapping, let's see the tasks:

Task 1: Minimum Index Sum

You are given two arrays of strings.

Write a script to find out all common strings in the given two arrays with
minimum index sum. If no common strings found returns an empty list.

Example 1
Input: @list1 = ("Perl", "Raku", "Love")
       @list2 = ("Raku", "Perl", "Hate")

Output: ("Perl", "Raku")

There are two common strings "Perl" and "Raku".
Index sum of "Perl": 0 + 1 = 1
Index sum of "Raku": 1 + 0 = 1
Example 2
Input: @list1 = ("A", "B", "C")
       @list2 = ("D", "E", "F")

Output: ()

No common string found, so no result.
Example 3
Input: @list1 = ("A", "B", "C")
       @list2 = ("C", "A", "B")

Output: ("A")

There are three common strings "A", "B" and "C".
Index sum of "A": 0 + 1 = 1
Index sum of "B": 1 + 2 = 3
Index sum of "C": 2 + 0 = 2

What is the relationship here?

When I read this problem, I intuitively knew this required set theory operations. Why, you may ask? Well, we can model the lists as sets, and wherever any of its members in the set intersect, we will have "commonality". Thus, in our case, the intersections between two sets. The solution is as identical as the way I initially solved it on paper. Matter of fact, it didn't require much scribbling, as the sample tests were easy to reason about in one's head. I just had to think out the algorithm out loud and write it down. Here's the code:

function solve(a, b) {
	const common = a.filter(e => b.includes(e));

	const minimum_sum = common.reduce((acc, e) => {
		const i = a.indexOf(e);
		const j = b.indexOf(e);
		const sum = i + j;

		if (sum < acc.min_sum) {
			return { elements: [e], min_sum: sum };
		} else if (sum == acc.min_sum) {
			return { elements: [...acc.elements, e], min_sum: sum };
		} else {
			return acc;
		}
	}, { elements: [], min_sum: Infinity });

	return minimum_sum.elements;
}

We first filter out the common values in each of the arrays passed in. In set operations, that's the intersection between the two. We can achieve this in JavaScript in multiple ways, the most straightforward I came up is the way I thought it through out loud, i.e:

• filter out all of the elements in a that are in b
• then reduce over all of the values that are in the common array by
• accumulating all of the elements in array a and array b
• starting from the empty array ([]) and some arbitrary number (Infinity)
• compute the sum by grabbing their indices
• if the actual sum < what we accumulated; give me the array with the element in it and the sum
• but if they are the same; i need everything you found, and the sum also
• otherwise, just give me back my accumulator which could be nothing

Since I now have an object that contains two fields {elements, min_sum}, I have my solution.

Task 2: Duplicate and Missing

You are given an array of integers in sequence with one missing and one duplicate.

Write a script to find the duplicate and missing integer in the given array. Return -1 if none found.

For the sake of this task, let us assume the array contains no more than one duplicate and missing.

Example 1:

Input: @nums = (1,2,2,4)
Output: (2,3)

Duplicate is 2 and Missing is 3.
Example 2:

Input: @nums = (1,2,3,4)
Output: -1

No duplicate and missing found.
Example 3:

Input: @nums = (1,2,3,3)
Output: (3,4)

Duplicate is 3 and Missing is 4.

This task was perhaps the "funnest" of the two. I originally solved this with set operations also, as it calls for uniqueness aka duplication and membership aka missing. However, a striking thing emerged. When I see integers, I always reach out for some type of relationship within them, as that normally produces better algorithms, since one can leverage the bits of information that they [the set of integers] give out. What do I mean?

Take a look at the examples given, see anything in particular ... I do! it is an arithmetic series, and these series are useful for modeling linear relationships. Which is exactly what we're after, as we are asked to find the relationship between the duplicate and missing number.

Duplication in an arithmetic series is a simply the sum_of_the squares since the answer lies in the name itself: square. The duplicate number is the one who repeats itself, as such, we'll grab the little tart.

For the one who's hiding, i.e the missing number, how do find him? Well, we know that he cannot be too far from his squarely friends, so he has to lurk closely to it within the data, he has to be within the elements. In other words, we need to find the difference between the sum of the elements and the sum of the squares. Let's given them names: Mr. Missing and Mrs. Duplicate (m and d respectively).

Let's use one of the examples and see if we can find them:

• Input: @nums = (1,2,2,4)
• Duplicate is 2 and Missing is 3.

The entire gang of misfits amount to 4, so n = 4 or better yet n = misfits.length. But if we accumulate them all up we find there are 9 of them, or better yet let's reduce them to their elements, and we can do the same thing to their squares:

elements = misfits.reduce((acc, val) => acc + val, 0) -> 9
squares = misfits.reduce((acc, val) => acc + val * val, 0) -> 25

Ok, if we now sum up what all of these elements and squares are up to, we can find their difference. In other words: the length of the gang (n) times what they originally started with (n + 1) and we divide them into two little neat groups, and we derive the same for the squares:

sum_of_elements = (n * (n + 1)) / 2 -> 10
sum_of_squares = (n * (n + 1) * (2 * n + 1)) / 6 -> 30

For element_diff = 4 * (4 + 1)) / 2 = 10 -> 1 (10 - 9)
For square_diff = 4 * (4 + 1)) * (2 * 4 + 1)) / 6 -> 5 (30 - 25)

So, now we have what we need to find Mr. Missing: just take difference of all the elements in this misfit gang (i.e. 1), lump them in with the difference of all the squares (i.e. 5) and we divide them by the two groups that we separate it them through (i.e. 2).

For Mrs. Duplicate: we simply remove Mr. Missing from the pack.

In the end, we have:

Mr. Missing    = (1 * 1 + 5) / (2 * 1) == 3  
Mrs. Duplicate = (3 - 1) == 2

Here's the code:

function solve(misfits) {
	const n = misfits.length;
	
	// elements
	const elements = misfits.reduce((acc, val) => acc + val, 0);
	const sum_of_elements = (n * (n + 1)) / 2;
	const element_diff = sum_of_elements - elements;

	// squares
	const squares = misfits.reduce((acc, val) => acc + val * val, 0);
	const sum_of_squares = (n * (n + 1) * (2 * n + 1)) / 6;
	const square_diff = sum_of_squares - squares;
	

	if (element_diff === 0 && square_diff === 0) {
		return -1;
	} else {
		const missing = (element_diff * element_diff + square_diff) / (2 * element_diff);
		const duplicate = missing - element_diff;
		return { duplicate, missing };
	}
}

Happy hacking!

#js #math #perl_weekly_challenge