Go Coding with Asparagos: Walnuts Take the IQ Test

#go #programming #humor #algorithms

Hi! I'm Asparagos — an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem: Walnuts Take the IQ Test 🌰.

Are walnuts the smartest?

Problem

Walnuts believe they are the smartest among all the plants (though not everyone agrees - especially spinach). Each walnut also believes that they are the smartest among all walnuts. Now, they want to convince everyone of their genius.

All walnuts have taken an IQ test. We have the IQ results for each of them. Now, they want to know if they are smarter than the average IQ of all the other walnuts - excluding themselves.

But that's not all. After gaining power, the fruits passed a new law: No negativity! Everyone should be happy and support the new King! So, subtraction is now banned in the kingdom. We must solve the problem without using the - operator.

Input 🥦

A slice of integers — each integer represents the result of one walnut's IQ test. There are at least two elements in the slice.

Output 🥕

A slice of integers — each integer represents the average IQ score of all the walnuts except the one at that index. The average should be calculated as the sum of the other results divided by their count, rounded down.

Examples 🥒:

Example 1

Input: [14, 75, 24, 86]

Output: [61, 41, 58, 37]

For index 0: average of [75, 24, 86] = (75 + 24 + 86) / 3 = 61.66... → 61
For index 1: average of [14, 24, 86] = 41.33... → 41
For index 2: average of [14, 75, 86] = 58.33... → 58
For index 3: average of [14, 75, 24] = 37.66... → 37
Example 2

Input: [15, 23, 48]

Output: [35, 31, 19]

For index 0: average of [23, 48] = (23 + 48) / 2 = 35.5 → 35
For index 1: average of [15, 48] = 31.5 → 31
For index 2: average of [15, 23] = 19
Example 3

Input: [15, 23]

Output: [23, 15]

Each index simply returns the other value.

Solution 💡

We create a result slice result. First, we calculate the prefix sum for each index and store it in result.
To calculate the average IQ of all nuts except the one at index ind, we need to sum all the elements to the left and right of that index.

We already have the prefix sum (i.e. the sum of all elements to the left) in result[ind - 1].

While iterating through the slice in reverse order, we calculate suffixSum, which holds the sum of all elements to the right of the current index.

The average is then calculated as (result[ind - 1] + suffixSum) / divNumber.

There's no subtraction in this algorithm, as required by the kingdom’s "No Negativity" law.

func checkWalnutGenius(iqs []int) []int {
    result := make([]int, len(iqs))
    result[0] = iqs[0]
    for ind := 1; ind < len(iqs); ind++ {
        result[ind] = result[ind-1] + iqs[ind]
    }

    suffixSum := 0
    divNumber := len(iqs) - 1
    for ind := len(iqs) - 1; ind > 0; ind-- {
        result[ind] = (result[ind-1] + suffixSum) / divNumber
        suffixSum += iqs[ind]
    }
    result[0] = suffixSum / divNumber
    return result
}