Zero-sum triplets challenge

Problem statement
Given an array of distinct elements find all triplets in array whose sum is equal to 0.

Sample input

Sample output

Solution
We will solve this algorithm in \mathcal{O}(n^2) time using hashing. The first iteration will be over all elements of our array. Let that elements be a[i]. Then we sum each a[i] with a second element a[j] (nested loop) and check whether we have a third element x that is equal to -(a[i] + a[j]) in our HashSet because x + a[i] + a[j] would then be equal to 0. If no such element exists we add the current a[j] to the HashSet for future lookups and continue. For each iteration for elements a[i], we generate a new lookup HashSet.

Full Code

 

Longest substring without repeating characters challenge

Problem statement
Given a string, find the length of the longest substring without repeating characters.

Examples

Example 1
Given abcabcbb, the answer is abc, which the length is 3.

Example 2
Given bbbbb, the answer is b, with the length of 1.

Example 3
Given pwwkew, the answer is wke, with the length of 3. Note that the answer must be a substring, pwke is a subsequence and not a substring.

Solution

 

Marc’s Cakewalk challenge

Problem statement
Marc loves cupcakes, but he also likes to stay fit. He eats n cupcakes in one sitting, and each cupcake i has a calorie count, c_i. After eating a cupcake with c calories, he must walk at least 2^j \times c (where c is the number cupcakes he has already eaten) miles to maintain his weight.

Given the individual calorie counts for each of the cupcakes, find and print a long integer denoting the minimum number of miles Marc must walk to maintain his weight. Note that he can eat the cupcakes in any order.

Input Format
The first line contains an integer, n, denoting the number of cupcakes.
The second line contains n space-separated integers describing the respective calorie counts of each cupcake, c_0, c_1, \dots, c_{n-1}.

Constraints
1 \le n \le 40
1 \le c_i \le 1000

Output Format
Print a long integer denoting the minimum number of miles Marc must walk to maintain his weight.

Sample Input 0

Sample Output 0

Explanation 0
Let’s say the number of miles Marc must walk to maintain his weight is miles. He can minimize miles by eating the n=3 cupcakes in the following order:

  1. Eat the cupcake with c_1 = 3 calories, so miles = 0 + (3 \times 2^0) = 3.
  2. Eat the cupcake with c_2 = 2 calories, so miles = 3 + (2 \times 2^1) = 7.
  3. Eat the cupcake with c_3 = 1 calories, so miles = 7 + (1 \times 2^2) = 11.

We then print the final value of miles, which is 11, as our answer.

Solution

 

Separate the numbers challenge

Problem statement
A numeric string, s, is beautiful if it can be split into a sequence of two or more positive integers, 1_1, a_2, \dots, a_n, satisfying the following conditions:

  1. a_i - a_{i-1} = 1 for any 1 \textless i \le n (i.e., each element in the sequence is 1 more than the previous element).
  2. No a_i contains a leading zero. For example, we can split s=10203 into the sequence \left[1, 02, 03\right], but it is not beautiful because 02 and 03 have leading zeroes.
  3. The contents of the sequence cannot be rearranged. For example, we can split s=312 into the sequence \left[3, 1, 2\right], but it is not beautiful because it breaks our first constraint (i.e., 1 - 3 \ne 1).

The diagram below depicts some beautiful strings:

You must perform q queries, where each query consists of some string s. For each query, print whether or not the string is beautiful on a new line. If it’s beautiful, print YES x, where x is the first number of the increasing sequence (if there are multiple such values of x, choose the smallest); otherwise, print NO instead.

Input Format
The first line contains an integer denoting (the number of strings to evaluate).
Each of the subsequent lines contains some string for a query.

Constraints
1 \le q \le 10
1 \le |s| \le 32
Each character in s is a decimal digit from 0 to 9 (inclusive).

Output Format
For each query, print its answer on a new line (i.e., either YES x where x is the smallest first number of the increasing sequence, or NO).

Sample Input 0

Sample Output 0

Explanation 0
The first three numbers are beautiful (see the diagram above). The remaining numbers are not beautiful:

For s = 101103, all possible splits violate the first and/or second conditions.
For s = 010203, it starts with a zero so all possible splits violate the second condition.
For s = 13, the only possible split is \left[1,3\right], which violates the first condition.
For s = 1, there are no possible splits because s only has one digit.

Solution

 

An interesting game challenge

Problem statement
Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, A, of n distinct integers. The rules are as follows:

  • Bob always plays first and the two players move in alternating turns.
  • In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if A = \left[2,3,5,4,1\right], then it becomes A = \left[2,3\right] after the first move because we remove the maximum element (i.e., 5) and all elements to its right (i.e., 4 and 1).
  • The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play g games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print ANDY; if Bob wins, print BOB.

Input Format
The first line contains a single integer denoting g (the number of games). The 2\times g subsequent lines describe each game array over two lines:

  1. The first line contains a single integer, n, denoting the number of elements in A.
  2. The second line contains n distinct space-separated integers describing the respective values of a_0, a_1, \dots, a_{n-1} for array A.

Constraints
Array contains n distinct integers.
1 \le g \le 100
1 \le n \le 10^5
1 \le a_i \le 10^9
The sum of n over all games does not exceed 10^5.

Output Format
For each game, print the name of the winner on a new line (i.e., either BOB or ANDY).

Sample Input 0

Sample Output 0

Explanation 0
Andy and Bob play the following two games:

1.
Initially, the array looks like this:

In the first move, Bob removes 6 and all the elements to its right, resulting in A = \left[5,2\right]:

In the second move, Andy removes 5 and all the elements to its right, resulting in A = \left[\right]:

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print ANDY on a new line.

2.
In the first move, Bob removes 3 and all the elements to its right, resulting in A = \left[\right]. As there are no elements left in the array for Andy to make a move, Bob wins and we print BOB on a new line.

Solution

 

Gena playing Hanoi challenge

Problem statement
The Tower of Hanoi is a famous game consisting of 3 rods and a number of discs of incrementally different diameters. The puzzle starts with the discs neatly stacked on one rod, ordered by ascending size with the smallest disc at the top. The game’s objective is to move the entire stack to another rod, obeying the following rules:

  1. Only one disc can be moved at a time.
  2. Each move consists of taking the topmost disc from a stack and moving it to the top of another stack.
  3. No disc may be placed on top of a smaller disc.

Gena has a modified version of the Tower of Hanoi. His Hanoi has 4 rods and N discs ordered by ascending size. He made a few moves (following the rules above), but stopped and lost his place. He wants to restore the tower to its original state by making valid moves. Given the state of Gena’s Hanoi, help him calculate the minimum number of moves needed to restore the tower to its original state.

Note: Gena’s rods are numbered from 1 to 4. All discs are initially located on rod 1.

Input Format
The first line contains a single integer, N, denoting the number of discs.
The second line contains N space-separated integers, where the i^{th} integer is the index of the rod where the disk with diameter i is located.

Constraints
1 \le N \le 10

Output Format
Print the minimum number of moves Gena must make to restore the tower to its initial, ordered state on the first rod.

Sample Input

Sample Output

Explanation
3 moves are enough to build the tower. Here is one possible solution:

Solution
We will use BFS to solve this challenge. We will use a helper array minForTower with minForTower[i] holding the size of the smallest disc located at tower i. The validMovesFromState() method will compute and return a Set<Integer[]> of all valid directly subsequent moves that can be made from a given tower-disc allocation. We will store visited states in an array int[] visited = new int[(int) Math.pow(4, n)] using a key. The array length is 4^N since we can have a maximum of 4^N possible tower-disc allocations/states. Each state has an integer key. For example, given a state \left[1, 4, 1\right], a key is an integer representing that allocation. Bits 2i and 2i+1 of the key represent the tower (Tower 0 = 00_b, Tower 1 = 01_b, Tower 2 = 10_b, Tower 3 = 11_b). For \left[1, 4, 1\right] the key is 12 = 001100_b.

We then do a BFS putting the states in a queue along with the depth of the given state. The depth or number of steps it took us to get to that state is stored at index 0 of the state array. Each time we reach our goal state we check we update our minimum if necessary.

The full code is listed below.

Full code

 

The power sum challenge

Find the number of ways that a given integer, X, can be expressed as the sum of the N^{th} power of unique, natural numbers.

Input Format
The first line contains an integer X.
The second line contains an integer N.

Constraints
1 \le X \le 1000
2 \le N \le 10

Output Format
Output a single integer, the answer to the problem explained above.

Sample Input 0

Sample Output 0

Explanation 0
If X = 10 and N=2, we need to find the number of ways that 10 can be represented as the sum of squares of unique numbers.

10 = 1^2 + 3^2

This is the only way in which 10 can be expressed as the sum of unique squares.

Sample Input 1

Sample Output 1

Explanation 1
100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2

Sample Input 2

Sample Output 2

Solution

 

Minimum loss challenge

Problem statement
Lauren has a chart of distinct projected prices for a house over the next n years, where the price of the house in the i^{th} year is p_i. She wants to purchase and resell the house at a minimal loss according to the following rules:

The house cannot be sold at a price greater than or equal to the price it was purchased at (i.e., it must be resold at a loss). The house cannot be resold within the same year it was purchased. Find and print the minimum amount of money Lauren must lose if she buys the house and resells it within the next years.

Note: It’s guaranteed that a valid answer exists.

Input Format
The first line contains an integer, n, denoting the number of years of house data. The second line contains space-separated long integers describing the respective values of p_1, p_2,\dots, p_n.

Constraints
2\le n \le 2 \times 10^5 1 \le p_i \le 10^{16} All the prices are distinct. It’s guaranteed that a valid answer exists.

Output Format
Print a single integer denoting the minimum amount of money Lauren must lose if she buys and resells the house within the next n years.

Sample Input 0

Sample Output 0

Explanation 0
Lauren buys the house in year 1 at price p_1 = 5 and sells it in year 3 at p_3 = 3 for a minimal loss of 5 - 3 = 2.

Sample Input 1

Sample Output 1

Explanation 1
Lauren buys the house in year 2 at price p_2 = 7 and sells it in year 5 at p_5 = 5 for a minimal loss of 7 - 5 = 2.

Sample Input & Output 3
minimum-loss-input
minimum-loss-output

Solution
Naive approach
The naive approach is to iterate over each price p_i and compare it with all the subsequent prices, storing any new found minimum loss based on the two rules stated in the problem statement. This obviously has a running time of \mathcal{O}(n^2).

Binary Search Tree (BST) approach
We can construct a BST from the prices array. The construction has a running time of \mathcal{O}(nlogn). We then go through all the nodes. Starting at node x we traverse up (go to its parent) the BST as long as the current node is not a left child of its parent (or no parent is available). If the current node is a left child then we return the value of its parent. This value is the smallest value that is greater than the value of the original/starting node x. Searching the BST for every node has a total worst case running time of \mathcal{O}(nlogn).

Full code

 

Word in string challenge

Problem statement
We say that a string, s, contains the word hackerrank if a subsequence of the characters in s spell the word hackerrank. For example, haacckkerrannkk does contain hackerrank, but haacckkerannk does not (the characters all appear in the same order, but it’s missing a second r).

More formally, let p_0, p_1, \dots, p_9 be the respective indices of h, a, c, k, e, r, r, a, n, k in string s. If p_0 \textless p_1, \textless p_2 \dots \textless p_9 is true, then s contains hackerrank.

You must answer q queries, where each query i consists of a string, s_i. For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Input Format
The first line contains an integer denoting q (the number of queries).
Each line i of the q subsequent lines contains a single string denoting s_i.

Output Format
For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Sample Input 0

Sample Output 0

Solution

 

Recursive Digit Sum challenge

Problem statement
We define super digit of an integer x using the following rules:

  • If x has only 1 digit, then its super digit is x.
  • Otherwise, the super digit of x is equal to the super digit of the digit-sum of x. Here, digit-sum of a number is defined as the sum of its digits.

For example, super digit of 9875 will be calculated as:

You are given two numbers n and k. You have to calculate the super digit of P.

P is created when number n is concatenated k times. That is, if n = 123 and k = 3, then P=123123123.

Input Format
The first line contains two space separated integers, n and k.

Constraints
1 \le n \textless 10^{100000}
1 \le k \le 10^{5}

Output Format
Output the super digit of P, where P is created as described above.

Sample Input 0

Sample Output 0

Explanation 0
Here n=148 and k=3, so P=148148148.

Sample Input 1
recursive-digit-sum-input-1

Sample Output 1
recursive-digit-sum-output-1

Solution