CtCI - Sum Pair Finder

With an array [7, 11, 15, 4, 2] find the indexes that sum up to 9.

In the first step of the solution we will check if the number at position zero, which in this case is the number seven, add up to the target nine when summed with the other numbers in the array. Below we can see the operations and notice that the solution is 7 + 2 which consists of the numbers in position zero and four.

[0, 0] 7 +  7 = 14
[0, 1] 7 + 11 = 18
[0, 2] 7 + 15 = 22
[0, 3] 7 +  4 = 11
[0, 4] 7 +  2 =  9

Since we need two different indexes we can remove the checks where the indexes are the same, in this case we will drop the check at positions [0, 0]. So if we have an iterator with x as the index of the array, we can assume that (x == x) is False.

We already found a solution for the problem, we have that indexes [0, 4] add up to the target nine, but lets check the other indexes and see if we can find a pattern to design our algorithm.

[1, 0] 11 +  7 = 18
[1, 1] 11 + 11 = 22 # Ignore
[1, 2] 11 + 15 = 26
[1, 3] 11 +  4 = 15
[1, 4] 11 +  2 = 13

We can see that indexes [0, 1] and [1, 0] are arithmetically the same. This becomes our second rule, we do not need to check the result of summing the numbers in positions that were checked in a previous step. In this case we only need to check the numbers in indexes greater than the current one. If x = 4 we can ignore the numbers in positions [0, 1, 2, 3].

[2, 0] 15 +  7 = 22 # Ignore
[2, 1] 15 + 11 = 26 # Ignore
[2, 2] 15 + 15 = 30 # Ignore
[2, 3] 15 +  4 = 19
[2, 4] 15 +  2 = 17
[3, 0] 4 +  7 = 11 # Ignore
[3, 1] 4 + 11 = 15 # Ignore
[3, 2] 4 + 15 = 19 # Ignore
[3, 3] 4 +  4 = 8  # Ignore
[3, 4] 4 +  2 = 6

Finally we find that the last index cannot be checked against any of the other ones because all the other indexes are in a position lower than the last one. Fortunately we already have the pattern for our algorithm, we found that for ever index x we are starting the comparison against every number in all the positions of the array starting at x+1. If array[x] + array[x+y] == 9 then we can return [x, y] where y is any index after position x.

func solution(numbers []int, target int) []int {
    var result = make([]int, 2)
    var total int = len(numbers)

    for i := 0; i < total; i++ {
        for j := (i + 1); j < total; j++ {
            if (numbers[i] + numbers[j]) == target {
                result[0] = i
                result[1] = j
                break
            }
        }
    }

    return result
}

However, this solution is quite expensive as we are executing an iteration inside another iteration which means that we are doing n * n where n is the number of elements in the list, which means we are doing O(n^2). We are executing the second iterator because we want to check the first index with all the numbers in the same list, but we are exiting the operation right after the first pair of numbers is found, so it is clear that we don't need to check all numbers.

Suppose that you have a list of friends and you ask them to come to your house one by one with a outfit of certain color. You want to know if two of your friends will wear the same colors. In our solution we are taking notes of the color of friend X and then inviting all the other friends for the color comparison, and doing this every time X changes. A real-life solution would be to track the color of each friend in a piece of paper, and every time a new friend comes you check if there is someone in the list (that have already signed) with the same color.

We can do the same here with our exercise. If we are on index zero we find the number 7 which differs from the target 9 by 2 points as (9 - 7) = 2. We want to check if the number two is in the tracking list, otherwise we add number seven to the list with its index and continue checking the other positions in the array.

Position two has number 11 which differs from 9 by -2 points as (9 - 11) = -2. We know by a fact that all numbers in the list are unsigned integers and we have to consider this inside the iterator, in his specific case as -2 is lower than zero we will multiply by -1 to remove the minus sign. Now we have 2 but unfortunately this number is not in the tracking list as we only have added the number 7 so we have to continue checking the other positions.

By the end of the first iteration we have a hash table {7:0, 11:1, 15:2, 4:3, 2:4}

The operations executed so far were like this:

Index - Operation - Diff - Abs - Hash Table
[0]     (9 -  7)  =  2     2     {7:0}
[1]     (9 - 11)  = -2     2     {7:0, 11:1}
[2]     (9 - 15)  = -6     6     {7:0, 11:1, 15:2}
[3]     (9 -  4)  =  5     5     {7:0, 11:1, 15:2, 4:3}
[4]     (9 -  2)  =  7     7     {...}

With this operation we want to check if the absolute (unsigned) difference of the subtraction of the number at index x from target is in the hash table (aka. the tracking list). At iteration zero we want to find the number two in the hash table but it doesn't exists so we add the number at position zero to the tracking list and continue with the other positions. At iteration four we get 7 as the absolute result of the subtraction, seven is in hash table so we have the solution there, we can pair the x index from the original iteration with the index attached to the number seven in the hash table, either [4, 0] or [0, 4]. With this approach we can do O(n).

func solution(numbers []int, target int) []int {
    var result = make([]int, 2)
    var total int = len(numbers)
    var hash = make(map[int]int)
    var diff int = 0

    for i := 0; i < total; i++ {
        diff = target - numbers[i]

        if diff < 0 {
            diff *= -1
        }

        if _, ok := hash[diff]; ok {
            return []int{hash[diff], i}
        }

        hash[numbers[i]] = i
    }

    return result
}
7 months ago
  • 8da57acFix minor bugs found by the code static ana…
7 months ago
  • caa417fAdd option to configure the malware scanner…
7 months ago
  • 9c86744Modify default value for some of the alert …
7 months ago
  • 84dd39dAdd option to stop sending the failed login…
7 months ago
  • eb05935Add pre-checks for every plugin page for si…
7 months ago
  • d21a062Modify mechanism to ignore files from integ…
7 months ago
  • b1a9169Add developer option to disable failed pass…
7 months ago
  • 4e3ef13Add support for other English and Spanish b…
7 months ago
  • 2d07b4eFix error interception for Firewall API err…
7 months ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
7 months ago
pushed to master at cixtor/slackapi
7 months ago
  • 6497e80Remove unnecessary automatic blacklisting o…
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
7 months ago
7 months ago
7 months ago
  • 38cc02aModify timing for the dashboard alerts afte…
7 months ago
  • 350c074Fix infinite loop with email alerts and SMT…
7 months ago
  • acff4aaFix detection of base URL with built-in fun…
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
7 months ago
7 months ago
  • 4c51445Fix static function call of non-static Site…
7 months ago
7 months ago
  • af47581Add changelog to release version 1.8.6
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
7 months ago
  • dc1a05aAdd changelog to release version 1.8.5
7 months ago
Do you have a project idea? Let's make it together!