# CodeFights Problems

Stay tuned for more solution/explanations.

If you have a question you want to see the solution of, comment below so that I can help you!

Also, I figured out how to put actual code snippets with indentation and all, so, the newer ones will have the code as a text instead of an image.

# Anime Screenshot Series – Tsugumomo

Hello Everyone!

It’s been a while right?

The screenshots are from Tsugumomo. I couldn’t take HQ screenshots but I will update as soon as I get my hands on a higher quality video 🙂

This slideshow requires JavaScript.

And this one is from Renai Boukun

See you later ^_^

# How to solve ‘trapRooms’ in CodeFights

## The Problem:

A zoological museum can be represented as a matrix in which each cell is a room. The alarm system in the museum allows visitors to go from each room only in one direction, specific to that room.

One night the exhibits went mad and messed the alarm system up. Now there are traps in the museum. A room is considered to be a trap if it’s impossible to leave the museum starting from it. A person leaves the building once he leaves the rectangle that represents it.

Given the museum’s configuration, find the number of traps in it.

Example

For

``````museum = [['U', 'L'],
['R', 'L']]
``````

the output should be
`trapRooms(museum) = 2`.

There is no exit if you start from either of the bottom rooms.

Check out the image below for better understanding:

Input/Output

• [time limit] 4000ms (py)
• [input] array.array.char museum

A non-empty rectangular matrix. The possible values of `museum[i]` are:

• `'L'` if it’s possible to move to the left;
• `'R'` if it’s possible to move to the right;
• `'U'` if it’s possible to move up;
• `'D'` if it’s possible to move down.

Guaranteed constraints:
`1 ≤ museum.length ≤ 10`,
`1 ≤ museum[0].length ≤ 10`.

• [output] integer

The number of traps.

## The Solution:

```def trapRooms(museum):
x=[[0]*len(museum[0]) for x in range(len(museum))]
def rec(a,b,x):
if not(a<len(museum) and a>=0 and b<len(museum[0]) and b>=0):
return 0
if x[a][b]:
return 1
s=0
x[a][b]=1
if museum[a][b]=='U':
s+=rec(a-1,b,x)
if museum[a][b]=='D':
s+=rec(a+1,b,x)
if museum[a][b]=='L':
s+=rec(a,b-1,x)
if museum[a][b]=='R':
s+=rec(a,b+1,x)
x[a][b]=0
return s
p=0
for a in range(len(museum)):
for b in range(len(museum[0])):
p +=rec(a,b,x)
print p
return p
```

## The Explanation:

We need to traverse the maze starting from each o the rooms and see if we can go outside, or go back to one of the rooms we have already passed. If we see any rooms we have already passed, that means we are stuck in the maze because the same room will always cause us to go back to same route.

# How to solve ‘bijectiveBase10’ in CodeFights

## The Problem:

Consider a numeral system similar to base-10 numeral system with the only difference that it does not use a digit to represent zero; instead it has a digit to represent ten, such as `A`. It is called bijective base-10 system. For example, numbers that do not contain zeros in base-10 system remain the same when converted to bijective base-10 system.

Given a positive integer in base-10 system, return its representation in bijective base-10 system.

Example

• For `a = 12345`, the output should be
`bijectiveBase10(a) = "12345"`;
• For `a = 10`, the output should be
`bijectiveBase10(a) = "A"`;
• For `a = 100`, the output should be
`bijectiveBase10(a) = "9A"`.

`100 = 10 * 9 + 10` -> `"9A"`.

• For `a = 2010`, the output should be
`bijectiveBase10(a) = "19AA"`.

`2010 = 1 * 103 + 9 * 102 + 10 * 10 + 10` -> `"19AA"`.

Input/Output

• [time limit] 4000ms (py)
• [input] integer a

A positive integer.

Guaranteed constraints:
`10 ≤ a ≤ 6 · 108`.

• [output] string

The string representation of `a` in bijective base-10 system.

## The Solution:

```def bijectiveBase10(a):
if '0' not in `a`:
return `a`
r=""
while a>0:
if a%10==0:
a-=10
r+="A"
else:
r+=str(a%10)
a/=10
return r[::-1]

```

## The Explanation:

We need to understand the arithmetic behind this. For every 0 digit we see, we replace it with an ‘A’, which is 10. So, we decrease 10 from our number, because it is not zero anymore, but a ten. Then, we continue doing this just as if we are converting the number to another base. At the end, we have the reverse of the number, so, we return reverse.

The first if statement is actually unnecessary, it would work exactly the same without that if block.

# How to solve ‘studentsAge’ in CodeFights

## The Problem:

My friend Albi is a teacher. At the beginning of each lesson, her students form a line and enter the class one by one. As they enter, each student shakes her hand. Albi enters the students’ names in a list in the order in which they enter the classroom. After work, she analyzes the list to get a hint of the connections and relationships in the class.

Albi has a hunch that the ages of the students can tell her a lot. She has a list of the ages of her `students` in the order they entered the classroom, and she wants to calculate the number of pairs of students such that their age difference is exactly `1`, and the youngest student in the pair entered before the oldest. Please help my friend!

Example

• For `students = [2, 4, 3, 4, 6]`, the output should be
`studentsAge(students) = 2`.

There are two pairs of students Albi would be interested in: `(2, 3)` and `(3, 4)`.

• For `students = [5, 4, 9, 10]`, the output should be
`studentsAge(students) = 1`.

The only interesting pair of students in `(9, 10)`.

Input/Output

• [time limit] 4000ms (py)
• [input] array.integer students

The ages of the students in the order they entered the classroom.

Guaranteed constraints:
`1 ≤ students.length ≤ 105`,
`0 ≤ students[i] ≤ 105`.

• [output] integer

An integer with the answer for Albi.

## The Solution:

```def studentsAge(s):
m=[0]*5**9
c=0
for x in s:
c+=m[x-1]
m[x]+=1
return c

```

## The Explanation:

There are multiple ways to solve this problem. Smarter way is to use a dictionary and store how many times each element is seen. However, to achieve the shortest solution (62 character in Python), we need a less efficient approach. Instead of a dictionary, create an array of size 10^5 and use this array to count each element.

For each element x in array, we need how many times x-1 is seen before that. So, for each element, we sum up this number and return it. The reason the array is initialized with length 5^9 is to decrease 1 character from 10^6.

# How to Solve ‘Chemicals’ in CodeFights

## The Problem:

Abby is a researcher at a company that makes chemical solutions. Her boss left her with a difficult task late Friday afternoon, and waltzed off into the weekend.

Abby has a hazardous liquid that reacts with oxygen by exploding. Her task is to distribute the liquid between special containers. The company buys containers of specific sizes in bulk, so she has access to a lot of containers of each size.

Since the liquid is explosive, Abby needs to fill the containers full to the exact capacity. Preparing the containers is tricky, so Abby wants to use as few containers as possible. Given the `totalAmount` of liquid and the set of container sizes `containers`, find the total number of containers she will need.

If there’s no way to distribute the liquid as described above, return `-1` instead.

Example

• For `totalAmount = 18` and `containers = [1, 2, 5, 10]`,
the output should be
`Chemicals(totalAmount, containers) = 4`.Abby has access to containers with sizes `10`, `5`, `2`, and `1`, and will use one container of each size.
• For `totalAmount = 9` and `containers = [1, 4, 6]`,
the output should be
`Chemicals(totalAmount, containers) = 3`.Abby can use two containers of size `4` and one container of size `1`.

Input/Output

• [time limit] 4000ms (py)
• [input] integer totalAmountThe amount of chemicals.Guaranteed constraints:
`0 ≤ totalAmount < 5 · 104`.
• [input] array.integer containersA sorted array of distinct integers, denoting the container sizes.Guaranteed constraints:
`1 ≤ containers.length ≤ 15`,
`0 ≤ containers[i] ≤ 1000`.
• [output] integerThe minimum number of containers needed to distribute the liquid. Return `-1` if there’s no way to distribute the liquid.

## The Solution:

```def Chemicals(totalAmount, containers):
totalAmount+=1
d=[999999]*totalAmount
d[0]=0
for x in containers:
if x <totalAmount:
d[x]= 1
for x in range(totalAmount):
for y in containers:
if x-y>0:
d[x]= min(d[x],d[x-y]+1)
if d[-1]==999999:
return -1
return d[-1]
```

## The Explanation:

Knapsack Problem, you can search for this term and learn more about it. In essence, create an array d. Each element of d shows the best solution up to that index. The idea follows this:

If I can get maximum value of 90 at 10 weight, and I have an item with weight 2 and value 10, then, at the best case, I can have 100 value at 92.

Reversing this, we want to minimize our weight at a given value. And slightly modifying the problem, we want to minimize number of containers at a given value.

If I can use minimum 5 containers to store 90, and I have containers of size 5, then I can have minimum 6 containers for size 95.

# How to Solve ‘minSubstringWithAllChars’ in CodeFights

## The Problem:

You have two strings, `s` and `t`. The string `t` contains only unique elements. Find and return the minimum consecutive substring of `s` that contains all of the elements from `t`.

It’s guaranteed that the answer exists. If there are several answers, return the one which starts from the smallest index.

Example

For `s = "adobecodebanc"` and `t = "abc"`, the output should be
`minSubstringWithAllChars(s, t) = "banc"`.

Input/Output

• [time limit] 4000ms (py)
• [input] string sA string consisting only of lowercase English letters.Guaranteed constraints:
`0 ≤ s.length ≤ 100`.
• [input] string tA string consisting only of unique lowercase English letters.Guaranteed constraints:
`0 ≤ t.length ≤ min(26, s.length)`.
• [output] string

## The Solution:

```def minSubstringWithAllChars(s, t):
for x in range(len(s)+1):
for p in range(len(s)-x+1):
c = filter(lambda x: x in t,s[p:p+x])
if len(set(c))==len(t):
return s[p:p+x]
return ""
```

# How to Solve ‘isCryptSolution’ in CodeFights

## The Problem:

A cryptarithm is a mathematical puzzle for which the goal is to find the correspondence between letters and digits, such that the given arithmetic equation consisting of letters holds true when the letters are converted to digits.

You have an array of strings `crypt`, the cryptarithm, and an an array containing the mapping of letters and digits, `solution`. The array `crypt` will contain three non-empty strings that follow the structure: `[word1, word2, word3]`, which should be interpreted as the `word1 + word2 = word3` cryptarithm.

If `crypt`, when it is decoded by replacing all of the letters in the cryptarithm with digits using the mapping in `solution`, becomes a valid arithmetic equation containing no numbers with leading zeroes, the answer is `true`. If it does not become a valid arithmetic solution, the answer is `false`.

Example

For `crypt = ["SEND", "MORE", "MONEY"]` and

``````solution = [['O', '0'],
['M', '1'],
['Y', '2'],
['E', '5'],
['N', '6'],
['D', '7'],
['R', '8'],
['S', '9']]
``````

the output should be
`isCryptSolution(crypt, solution) = true`

When you decrypt `"SEND"`, `"MORE"`, and `"MONEY"` using the mapping given in `crypt`, you get `9567 + 1085 = 10652` which is correct and a valid arithmetic equation.

For `crypt = ["TEN", "TWO", "ONE"]` and

``````solution = [['O', '1'],
['T', '0'],
['W', '9'],
['E', '5'],
['N', '4']]
``````

the output should be
`isCryptSolution(crypt, solution) = false`

Even though `054 + 091 = 145`, `054` and `091` both contain leading zeroes, meaning that this is not a valid solution.

Input/Output

• [time limit] 4000ms (py)
• [input] array.string crypt

An array of three non-empty strings containing only uppercase English letters.

Constraints:
`crypt.length = 3`,
`1 ≤ crypt[i].length ≤ 14`.

• [input] array.array.char solution

An array consisting of pairs of characters that represent the correspondence between letters and numbers in the cryptarithm. The first character in the pair is an uppercase English letter, and the second one is a digit in the range from `0`to `9`.

Constraints:
`solution[i].length = 2`,
`'A' ≤ solution[i][0] ≤ 'Z'`,
`'0' ≤ solution[i][1] ≤ '9'`,
`solution[i][0] ≠ solution[j][0], i ≠ j`,
`solution[i][1] ≠ solution[j][1], i ≠ j`.

It is guaranteed that `solution` only contains entries for the letters present in `crypt` and that different letters have different values.

• [output] boolean

Return `true` if the `solution` represents the correct solution to the cryptarithm `crypt`, otherwise return `false`.

## The Explanation:

Map the letters to the given numbers.

Generate corresponding numbers,

if first + second = third, check if they have leading zeros by comparing the length of numbers and the words, if not, return 1

f they have leading zeros or the sum is not equal, return 0

# How to Solve ‘containsCloseNums’ in CodeFights

## The Problem:

Given an array of integers `nums` and an integer `k`, determine whether there are two distinct indices `i` and `j` in the array where`nums[i] = nums[j]` and the absolute difference between `i` and `j` is less than or equal to `k`.

Example

• For `nums = [0, 1, 2, 3, 5, 2]` and `k = 3`, the output should be
`containsCloseNums(nums, k) = true`.

There are two `2`s in `nums`, and the absolute difference between their positions is exactly `3`.

• For `nums = [0, 1, 2, 3, 5, 2]` and `k = 2`, the output should be

`containsCloseNums(nums, k) = false`.

The absolute difference between the positions of the two `2`s is `3`, which is more than `k`.

Input/Output

• [time limit] 4000ms (py)
• [input] array.integer nums

Constraints:
`0 ≤ nums.length ≤ 55000`,
`-231 - 1 ≤ nums[i] ≤ 231 - 1`.

• [input] integer k

Constraints:
`0 ≤ k ≤ 35000`.

• [output] boolean

## The Explanation:

First of all, we can solve this by running two loops, one is i from 1 to k and the other j from 0 to len(nums)-i and compare nums[j] and nums[i+j]. If we find an equality, return 1. If none found, return 0.

However, we would receive Time Limit Exceeded Error. So, we need a better solution. We know that when we sort numbers, the same numbers will be consecutive in sorted order. So, if we store the original locations of all elements, we will have the same elements together and also know their original location. All we have to do now is to check if any consecutive equal numbers have a smaller distance than k+1.

This reduces our complexity from, let’s say len(nums) = n. Then, O(n*k) to O( n*log(n) )

limit of n is 55000 so, logn is approximately 16. Where k could be 35000. So, our worst case scenario becomes 55000*35000 to 55000*16.

How we do this is simple. First,generate a new array with numbers and their original addressses. Then, sort them using their values. Then, for each element, check if the previous element has the same value, if so, check their original location distances. If smaller than k+1, return 1

Otherwise, return 0

# How to Solve ‘SimplifyPath’ in CodeFights

## The Problem:

Given an absolute file path (Unix-style), shorten it to the format `/<dir1>/<dir2>/<dir3>/...`.

Here is some info on Unix file system paths:

• `/` is the root directory; the path should always start with it even if it isn’t there in the given `path`;
• `/` is also used as a directory separator; for example, `/code/fights` denotes a `fights` subfolder in the `code` folder in the root directory;
• this also means that `//` stands for “change the current directory to the current directory”
• `.` is used to mark the current directory;
• `..` is used to mark the parent directory; if the current directory is root already, `..` does nothing.

Example

For `path = "/home/a/./x/../b//c/"`, the output should be
`simplifyPath(path) = "/home/a/b/c"`.

Here is how this path was simplified:
* `/./` means “move to the current directory” and can be replaced with a single `/`;
* `/x/../` means “move into directory `x` and then return back to the parent directory”, so it can replaced with a single `/`;
* `//` means “move to the current directory” and can be replaced with a single `/`.

Input/Output

• [time limit] 4000ms (py)
• [input] string pathA line containing a path presented in Unix style format. All directories in the path are guaranteed to consist only of English letters.

Constraints:
`1 ≤ path.length ≤ 5 · 104`.

• [output] stringThe simplified path.

# How to solve ‘removeDuplicateAdjacents’ in CodeFights

## The Problem

Given a string `s`, recursively remove any adjacent duplicate characters that it contains.

Example

• For `s = "cooodefightssforrrcodee"`, the output should be
`removeDuplicateAdjacent(s) = "cdefightfocod"`.
• For `s = "acaaabbbacdddd"`, the output should be
`removeDuplicateAdjacent(s) = "acac"`.

Input/Output

• [time limit] 4000ms (py)
• [input] string s

A string composed of lowercase English letters.

Constraints:

`1 ≤ s.length ≤ 50`.

• [output] string

A string obtained by removing all adjacent duplicates from the input string.