# Weekly Contest 415

## Q1: The Two Sneaky Numbers of Digitville

In the town of Digitville, there was a list of numbers called `nums` containing integers from `0` to `n - 1`. Each number was supposed to appear **exactly once** in the list, however, **two** mischievous numbers sneaked in an *additional time*, making the list longer than usual.

As the town detective, your task is to find these two sneaky numbers. Return an array of size **two** containing the two numbers (in *any order*), so peace can return to Digitville.

### Thoughts

* seems pretty simple, i think i’ll just use a hashset or something
    

### Solution

```java
class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        HashSet<Integer> hs = new HashSet();
        int[] ans = new int[2];
        int ansNum = 0;

        for (int i : nums) {
            if (!hs.add(i)) {
                ans[ansNum] = i;
                ansNum++;
                if (ansNum == 2) return ans;
            } 
        }
        return ans;
    }
}
```

**Time Complexity:** O(n)  
**Space Complexity:** O(n)

### Conclusion

ezpz hashset solution. I think there may be a better way though.

## Q2: Maximum Multiplication Score

You are given an integer array `a` of size 4 and another integer array `b` of size **at least** 4.

You need to choose 4 indices `i<sub>0</sub>`, `i<sub>1</sub>`, `i<sub>2</sub>`, and `i<sub>3</sub>` from the array `b` such that `i<sub>0</sub> < i<sub>1</sub> < i<sub>2</sub> < i<sub>3</sub>`. Your score will be equal to the value `a[0] * b[i<sub>0</sub>] + a[1] * b[i<sub>1</sub>] + a[2] * b[i<sub>2</sub>] + a[3] * b[i<sub>3</sub>]`.

Return the **maximum** score you can achieve.

### Thoughts

* best solution i could come up with was a brute force, I’m almost certain there is a way to do this with dynamic programming
    

### Solution

```java
class Solution {
    public long maxScore(int[] a, int[] b) {
        long ans = Long.MIN_VALUE;
        for (int i = 0; i < b.length - 3; i++) {
            for (int j = i + 1; j < b.length - 2; j++) {
                for (int k = j + 1; k < b.length - 1; k++) {
                    for (int l = k + 1; l < b.length; l++) {
                        long temp = a[0] * b[i] + a[1] * b[j] + a[2] * b[k] + a[3] * b[l];
                        if (Long.compare(temp,ans) > 0) ans = temp;
                    }
                }
            }
        }

        return ans;
    }
}
```

**Time Complexity:** O(n^4)  
**Space Complexity:** O(1)

### Conclusion

Definitely should learn some more dynamic programming because this is (I think) a dynamic programming problem and my brute force solution is too slow to complete all of the test cases.

# Overall Conclusion

Yea I really need to work on my DP knowledge, otherwise I am going to keep hitting performance walls like this.