[TLE fix] Pairs

This question is just as one would expect it. The first thought you get to solve it will probably be the right one.

For each element arr[i], we search for arr[i] + k in the array, and whenever it is found, we increment a counter variable.

But the twist here is that arr.index() is linear search, and is an O(n) function. Since we are putting this in a loop, the naive O(n²) solution gives a TLE.

Enter the bisect package. To use it we have to add this line at the top of our code:

from bisect import bisect_left

What does this do? Gives us binary search out of the box.
The bisect package contains 2 particularly useful functions:
bisect_left(array, element) returns the index of leftmost occurrence element in array.
bisect_right(array, element) returns the index of rightmost occurrence element in array.

Binary search is an O(logn) algorithm. Therefore our solution is O(nlogn) and it now passes all the testcases.

Note that the array must be sorted in order for binary search to work. So before calling bisect_left, we must sort the array.

[deceptively nasty] Palindrome Index

This problem is prima facie really easy looking. But its a snake waiting to bite!

What I did initially was to initialize two variables, i = 0 and j = len(s) - 1 (start and end of s).
On each iteration of a while loop (while i < floor(len(s) / 2)), compare values s[i] and s[j] and if they are equal, we are good.

But if they are not equal, one of the two things can occur. Either s[i] must be the odd letter, or s[j]. For this the natural approach is to check the next letter, and see if they match, that is:

1. compare s[i + 1] and s[j]
2. compare s[i] and s[j - 1]

If 1. is true, then s[i] must be removed, and if 2 is true, s[j] must be removed.

Easy, right?
WRONG!

Consider the following testcases:

cwwcw
wcwwc

The above logic will give the wrong output for these cases.

It turns out, conditions 1. and 2. are NOT sufficient for determining which letter is the odd one out. We must also check the next pair of elements as well. The correct conditions are:

1. if s[i] == s[j - 1] and s[i + 1] == s[j - 2]
2. if s[i + 1] == s[j] and s[i + 2] == s[j - 1]

These correctly determine which out of s[i] and s[j] is the odd one out. Deceptively nasty indeed!

[a little intuition] Max Min

Sometimes, one must trust one's intuition. In coding problems, intuition is a really useful thing to build.

When I opened this problem, I had no idea whatsoever how to approach this problem.

Suddenly a random thought popped into my head:
What if I sorted the array, and took the first k elements?
Immediately I could think of counterexamples to disprove this notion.

1, 10, 11, 12, 13 and k  = 3

But all was not lost. We could still improve upon this. What if we looked at k length contiguous subsets of this?

1, 10, 11 | 10
10, 11, 12 | 2
11, 12, 13 | 2

And eureka! We could find the minimum difference this way.

Eureka indeed. Why does this work? If you remove all the contest pressure I had, it is plain that if the array is sorted, the difference between consecutive elements is the smallest possible, while still being non-negative. For a valid contiguous subset, we are finding the sum of the differences between consecutive elements (a bit of a mouthful there).

If the consecutive differences are minimum, then the cumulative difference between the first and last elements (min and max) is minimum, and that, solves the problem.

[incremental progress :)] The Full Counting Sort

The first medium level question in my HackerRank journey! And yes, it was pretty hard for me. But the logic was easy to think of. Just hard to implement.

This was a higher level version of Jim and the Orders (whose solution is available here: https://teamresurgence.blogspot.com/2020/05/new-concept-jim-and-orders.html).

Here too, the Hashmap came in handy. Ultimately we have to sort the strings by their keys. But here we have to set it up to make the sorting "stable" (read the question). So here is what I came up with:

1. Accept the string, and it's key. Search for the key in an array called "takenKeys", which stores all the unique keys so far. If the key is found (meaning it is a duplicate), we will modify it to ensure stable sorting. Here they have put loophole of replacing the first half of strings by '-'. While accepting the strings itself, check if the the index of the loop which is accepting the strings is smaller than floor(n / 2) and simply append '-' instead of the accepted string in that case. A literal loophole!

2. This "modification" is simple. For each unique key, I have a "factor" (all these factors for each key are stored in a different array)  The factor for each key is initialized to 0.1. Whenever a duplicate key is detected, say 4, I add the factor to it. (4 -> 4.1) and then factor = factor + factor/10000. Why 10000? I actually tried, 2, 10, 100, 1000, 10000. 10000 managed to pass all the testcases. This happens because lower values can "overflow". Meaning the sums of factors can add up to a value larger than 1. If 4 becomes 5 or more, instead of 4 < x < 5, then our sorting will mess up.
So if our keys were originally like this:
1, 3, 0, 1, 0, 1
they now become (if factor = factor + factor / 10, for simplicity):
1, 3, 0, 1.1, 0.1, 1.11
After sorting:
0, 0.1, 1, 1.1, 1.11, 3
Now it should be clear why the sorting is stable.

3. Now send this dictionary, with keys being the modified keys and the values being associated strings. Sort the dictionary by keys (unlike Jim, where we sorted by values). And now, print the values!

[playing with combinations] Smart Number

A very interesting problem, leading to a result that seems counter intuitive till you prove it. The difficulty is that intuition doesn't encourage one to try and prove it.

Consider any number n.
It has prime factors having varying powers, and those powers may be odd or even
After squaring, all the powers will become even. Let the power be p, therefore there are p + 1 ways to put that prime
in our factor prime^(0, 1, 2, ... p). Therefore the number of factors of any number are:
(p1 + 1)(p2 + 1)... so on
But since p is always even, p + 1 is guaranteed to be odd.
Since a product of odd numbers is always odd, the number of factors is odd.

Therefore, a perfect square will always have odd number of factors.

[new concept] Jim and the Orders

This problem becomes really easy if we use a hashmap.

The Hashmap:
A data structure very much like an array, but the "index" of this array can be any data type. This "index" is called "key". The data associated with each key is called its "value".
For example:
"Key1" : 1023
"Key2" : "Hello"
12.13 : True

An advantage of hashmap is that the time required to extract a value given it's key is constant (O(1)).

In python, hashmaps are called "dictionaries".

For this problem, I created a dictionary with the keys being natural numbers, representing the position of each customer in the line (1, 2, 3, ...) and the value being the time for serving the order.

Then I sorted the dictionary by value. The keys should now be in correct order!
One way to do it in python is this:

sorted_keys = sorted(dict.items(), key = lambda kv:(kv[1], kv[0]))

This returns an array of tuples (key, value) of the dictionary sorted by value.

Just extract the keys part in a separate array, and return it.

[a delightful little problem] Fair Rations

This is a complex sounding problem that is actually very simple, and yet requires some creativity to solve.
Let's consider an array, with elements being boolean (True if the number of loaves with the person in that index in the line is even, else False). A typical starting array may look like this:

TTTTF

Now this case is interesting. We observe that in order to eliminate F entirely, we must have a situation with two nieghboring F's. Then we can give one loaf to both, and convert them to T. Hence, the total number of F's must be even, otherwise a solution is not possible, in which case we return "NO".

Now let's look at some examples cases where it is possible:

1. TFTFT

2. TTFFT

3. FTTTF

I tried some experimentation, and came up with this algorithm to distribute the loaves:

1. Loop through every element. If that element is T, move on.
2. If that element is F, then invert that element and the element to its right. Increment a "breadCount" variable by 2 everytime we do this.
3. Continue doing this. By the end of this, we must end up with all T's.
4. Return the "breadCount"

Also: Solution accepted on first try :))