Sum vs XOR

Problem Statement
Given an integer, n, find each x such that:

0 \le x \le n
n + x = n \oplus x

where \oplus denotes the bitwise XOR operator. Then print an integer denoting the total number of x‘s satisfying the criteria above.

Input Format
A single integer, n.

Constraints
0 \le n \le 10^{15}

Output Format
Print the total number of integer x‘s satisfying both of the conditions specified above.

Sample Input

Sample Output

Explanation

For n=5, the x values 0 and 2 satisfy the conditions:

5 + 0 = 5 \oplus 0 = 5
5 + 2 = 5 \oplus 2 = 7

Thus, we print 2 as our answer.

Solution

 

Simplified chess engine

Chess is a very popular game played by hundreds of millions of people. Nowadays, we have chess engines such as Stockfish and Komodo to help us analyze games. These engines are very powerful pieces of well-developed software that use intelligent ideas and algorithms to analyze positions and sequences of moves, as well as find tactical ideas. Consider the following simplified version of chess:

  • Board: It’s played on a 4 \times 4 board between two players named Black and White.

  • Pieces and Movement:

    • White initially has w pieces and Black initially has b pieces.
    • There are no Kings and no Pawns on the board. Each player has exactly one Queen, at most two Rooks, and at most two minor pieces (i.e., a Bishop and/or Knight).
    • Each piece’s possible moves are the same as in classical chess, and each move made by any player counts as a single move.
    • There is no draw when positions are repeated as there is in classical chess.
  • Objective: The goal of the game is to capture the opponent’s Queen without losing your own.

Given m and the layout of pieces for g games of simplified chess, implement a very basic (in comparison to the real ones) engine for our simplified version of chess with the ability to determine whether or not White can win in \le m moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win under the specified conditions; otherwise, print NO.

Input Format
The first line contains a single integer, g, denoting the number of simplified chess games. The subsequent lines define each game in the following format:

  • The first line contains three space-separated integers denoting the respective values of w (the number of White pieces), b (the number of Black pieces), and m (the maximum number of moves we want to know if White can win in).

  • The w + b subsequent lines describe each chesspiece in the format t c r, where t is a character \in \{Q,N,B,R\} denoting the type of piece (where Q is Queen, N is Knight, B is Bishop, and R is Rook), andc and r denote the respective column and row on the board where the figure is placed (where c \in \{A,B,C,D\} and r \in \{1,2,3,4\}). These inputs are given as follows:

  • Each of the w subsequent lines denotes the type and location of a White piece on the board.
  • Each of the b subsequent lines denotes the type and location of a Black piece on the board.

Constraints
It is guaranteed that the locations of all pieces given as input are distinct.
1 \le g \le 200
1 \le w,b \le 5
1 \le m \le 6
Each player initially has exactly one Queen, at most two Rooks and at most two minor pieces.

Output Format
For each of the g games of simplified chess, print whether or not White can win in \le m moves on a new line. If it’s possible, print YES; otherwise, print NO.

Sample Input 0

Sample Output 0

Explanation 0
We play g=1 games of simplified chess, where the initial piece layout is as follows:

White is the next to move, and they can win the game in 1 move by taking their Knight to A4 and capturing Black’s Queen. Because it took 1 move to win and 1 \le m, we print YES on a new line.

Additional Sample Input
input 1 expected output 1
input 2 expected output 2

Solution
Just to have an overview of the how the different chess pieces move, I have listed the moves below for quick reference:

Queen Knight Bishop Rook

Next, we need to figure out a strategy. Since the goal of the game is to capture the opponent’s Queen without losing your own a player can (1) avoid moves that put his Queen in jeopardy and (2) make a move that takes his Queen out of danger if the Queen happens to be in danger.

We are going to solve this problem using recursion. At this point it is worth noting the fact that depending on what player’s turn it is, a winning board has a different outcome depending on the current player. This will be important when handling return values from our recursive function calls. More on that later.

The board will internally be represented using an int[][] board array of size 4 \times 4. We also need to distinguish the White player pieces from the Black player pieces. I will use odd numbers for the pieces belonging to the White player and even numbers for the pieces belonging to the Black player:

Next, we are going to store all possible movement directions for each piece in a dedicated array:

Wer are going to also define some helper functions that will help us determine if a given row and column are within board limits and if a movement to a given square is valid:

The player parameter in the isValid(...) valid function takes two possible values: 1 when we are calling isValid(...) for the White player and 0 when we are calling isValid(...) for the Black player. isValid(...) returns true if we are within board limits and the square we are planning to move is not occupied by one of our own pieces. It return false otherwise.

Next, we are going to define helper functions, that we can call for a given board to determine if White or Black have won the game. That is, if the opponent does not have a Queen on the board:

player takes two possible values: 1 when we are calling isWinForPlayer(...) for the White player and 0 when we are calling isWinForPlayer(...) for the Black player. It returns true if the player wins and false otherwise.

We also define a function that returns the position of a player’s Queen on the board:

Next, we need a function that lets us know if the Queen of a player is safe in a given board:

Note above that for Queen, Bishop and Rook we take the movement directions and try them out for lengths 1\dots 4. This is not the case for a Knight (see Knight movement illustration above) where the movement does not have a variable length. Also notice for Queen, Bishop and Rook, if any piece is in the way we do not need to check the positions beyond that square since it blocks any opponent’s piece beyond that point.

Now that we have implemented our helper functions we can proceed with the actual algorithm. We are going to solve this by calling our main function canWhiteWin(int[][] board, int m, int player) recursively. Our exit conditions will be reaching the limit of our allowed number of moves, reaching a state where White wins or reaching a state where Black wins:

canWhiteWin(...) is called for every possible positions the player can move a piece and for all the player’s pieces on the board. A player recursively calls canWhiteWin(...) only for valid positions and if his Queen is safe in the resulting board. canWhiteWin(...) returns true if White player can win and false otherwise. We need to handle the result after every recursive function call differently depending on the current player. If the current player who called canWhiteWin(...) is White and the resulting value is true we do not need to examine any further positions. We exit by returning true, since White has found a move from the current board state that guaranties a win, no matter how Black plays next. If the current player who called canWhiteWin(...) is Black and the resulting value is false, we exit by returning false since from the current board state Black can make a move that results in White losing.

For Queen, Bishop and Rook we take the movement directions and try them out for lengths 1\dots 4. This is not the case for a Knight (see Knight movement illustration above) where the movement does not have a variable length. Also notice for Queen, Bishop and Rook, if any piece is in the way we do not need to check the positions beyond that square since it blocks the route to a square beyond that point.

Finally, if White cannot make a move, because his Queen would not be safe we return false. If a Black cannot make a move and m>1 we return true since black will be forced to make a move that puts his Queen at risk, which White can take in his next move.

That’s it! The full algorithm is listed below.

Full code

 

3Sum closest challenge

Problem statement
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Sample Input

Sample Output

Solution

 

Summary ranges challenge

Problem statement
Given a sorted integer array without duplicates, return the summary of its ranges for consecutive numbers.

For example, given [0,1,2,4,5,7], return [0\rightarrow 2,4\rightarrow 5,7].

Solution

 

Search for a range challenge

Problem statement
Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of \mathcal{O}(log n). If the target is not found in the array, return [-1, -1]. For example, given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Solution

 

Minimum window substring challenge

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity \mathcal{O}(n).

Sample Input 0

Sample Output 0

Solution
The first step we are going to take is, count the occurrences of each letter in string T. We will use a Map for that.

We then iterate over each character of string S using an iterator i and keep a count of characters encountered so far. Again, for that we will use a Map<Character, Integer> count. We will track the start and ending of the smallest substring using start and end. At first both, start and end are initialised to -1. As soon, as we hit a character that is contained in T we set start = i, as this is the soonest possible way that a substring may contain all characters in T.

While we are iterating over the letters in S, we check if we have collected all the required characters. As soon as that is the case, we set end = i. Now we have a substring that contains all the characters of T. But we are not done yet. Maybe there exists a smaller substring that also contains all the characters of T.

We continue iterating over the remaining characters in S while incrementing our end to i and adding them to count. If we hit a character that is equal to S[start] (the tail of the current substring) we remove it from the current substring. We also keep removing characters from the tail that are not contained in T or characters that are in T but we have in excess.

When we are done removing characters, we check if the new resulting substring is shorter than the previous one. If such is the case we update our answer.

The algorithm terminates when we have iterated over all characters in S.

The full implementations (two variations) are listed below.

Full code (Implementation 1)

Full code (Implementation 2)

 

Append and delete challenge

Problem statement
You have a string, s, of lowercase English alphabetic letters. You can perform two types of operations on s:

  1. Append a lowercase English alphabetic letter to the end of the string.
  2. Delete the last character in the string. Performing this operation on an empty string results in an empty string.

Given an integer, k, and two strings, s and t, determine whether or not you can convert s to t by performing exactly k of the above operations on s. If it’s possible, print Yes; otherwise, print No.

Input Format
The first line contains a string, s, denoting the initial string.
The second line contains a string, t, denoting the desired final string. The third line contains an integer, k, denoting the desired number of operations.

Constraints
1 \le |s| \le 100
1 \le |t| \le 100
1 \le k \le 100
s and t consist of lowercase English alphabetic letters.

Output Format
Print Yes if you can obtain string t by performing exactly k operations on s; otherwise, print No.

Sample Input 0

Sample Output 0

Explanation 0
We perform 5 delete operations to reduce string s to hacker. Next, we perform 4 append operations (i.e., r, a, n, and k), to get hackerrank. Because we were able to convert s to t by performing exactly k=9 operations, we print Yes.

Sample Input 1

Sample Output 1

Explanation 1
We perform 4 delete operations to reduce string s to the empty string (recall that, though the string will be empty after 3 deletions, we can still perform a delete operation on an empty string to get the empty string). Next, we perform 3 append operations (i.e., a, b, and a). Because we were able to convert s to t by performing exactly k=7 operations, we print Yes.

Solution

 

Mini-max sum challenge

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.

Input Format
A single line of five space-separated integers.

Constraints
Each integer is in the inclusive range [1, 10^9].

Output Format
Print two space-separated long integers denoting the respective minimum and maximum values that can be calculated by summing exactly four of the five integers. (The output can be greater than 32 bit integer.)

Sample Input

Sample Output

Solution

 

Kangaroo challenge

There are two kangaroos on an x-axis ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location x_1 and moves at a rate of v_1 meters per jump. The second kangaroo starts at location x_2 and moves at a rate of v_2 meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever land at the same location at the same time?

Input Format
A single line of four space-separated integers denoting the respective values of x_1, v_1, x_2, and v_2.

Constraints
0 \le x_1 \textless x_2 \le 10000
1 \le v_1 \le 10000
1 \le v_2 \le 10000

Output Format
Print YES if they can land on the same location at the same time; otherwise, print NO.

Note: The two kangaroos must land at the same location after making the same number of jumps.

Sample Input 0

Sample Output 0

Explanation 0
The two kangaroos jump through the following sequence of locations:
0 \rightarrow 3 \rightarrow 6 \rightarrow 9 \rightarrow  12
4 \rightarrow  6 \rightarrow 8 \rightarrow 10 \rightarrow 12
Thus, the kangaroos meet after 4 jumps and we print YES.

Sample Input 1

Sample Output 1

Explanation 1
The second kangaroo has a starting location that is ahead (further to the right) of the first kangaroo’s starting location (i.e., x_2 \textgreater x_1). Because the second kangaroo moves at a faster rate (meaning v_2 \textgreater v_1) and is already ahead of the first kangaroo, the first kangaroo will never be able to catch up. Thus, we print NO.

Solution
In order for the two kangaroos to land at the same location after i amount of time, the following must be true: x_1 + i \times v_1 == x_2 + i \times v_2. In other words, x_2 - x_1 == (v_1 - v_2)\times i. Thus, if (x_2 - x_1) % (v_1 - v_2) == 0 we return YES otherwise we return NO.

The full code is listed below.

Full code

 

The Knuth shuffle

The Knuth shuffle algorithm is an algorithm for randomly shuffling the elements of an array arr of size n given a function that generates a uniformly distributed random number in \mathcal{O}(1) time. The algorithm produces an unbiased permutation. That is, every permutation is equally likely.

Proof that the algorithm is unbiased
For any element e, the probability that it will be shuffled into position n-1 (last position at zero based indexing) is: the probability that it gets selected when i=n-1, which is \frac{1}{n}.

For any element e, the probability that it will be shuffled into position n-2 (second-to-last position) when i=n-2 is: the probability that it gets selected when i=n-2, which is \frac{1}{n-1} multiplied by the probability that it is not selected for the last position, which is 1 - \frac{1}{n} = \frac{n-1}{n}, giving  \frac{1}{n-1}\times\frac{n-1}{n} = \frac{1}{n}

For any element e, the probability that it will be shuffled into position n-3 (third-to-last position) when i=n-3 is: the probability that it gets selected when i=n-3, which is \frac{1}{n-2} multiplied by the probability that it is not selected for the last nor second-to-last position, which is 1 - \frac{2}{n} = \frac{n-2}{n}, giving \frac{1}{n-2}\times\frac{n-2}{n} = \frac{1}{n}.

This can easily be generalised for any other position.

So we can see that for any element e, the probability that it will be shuffled into the last, second-to-last, third-to-last, etc position is \frac{1}{n}.