# HackerRank Solutions

Over the course of the next few (actually many) days, I will be posting the solutions to previous Hacker Rank challenges. The page is a good start for people to solve these problems as the time constraints are rather forgiving. I have most solutions in C++, but I will be trying to post them in Python. The language is more readable. Recently I started adding Rust code as well.

My public HackerRank profile here.

I have solutions to all listed solutions. If the solution is not listed, I have not solved it yet. If there is no link, it means that I did not parse the algorithm to a readable format yet.

## Search

• [Easy] Encryption
• [Easy] Ice Cream Parlor
• [Easy] Sherlock and Array
• [Moderate] Circle City
• [Moderate] Connected Cell in a Grid
• [Moderate] Cut the tree
• [Moderate] Count Luck
• [Moderate] Find Maximum Index Product
• [Moderate] Gena Playing Hanoi
• [Moderate] Missing Numbers
• [Moderate] Number List
• [Moderate] Pairs
• [Moderate] Short Palindrome
• [Moderate] The Grid Search
• [Difficult] Absolute Element Sums
• [Difficult] Bike Racers
• [Difficult] Journey Scheduling
• [Difficult] King Richard’s Knights
• [Difficult] Maximum Subarray Sum
• [Difficult] Playing with numbers

## Dynamic Programming

• [Easy] The Maximum Subarray
• [Moderate] Bricks Game
• [Moderate] Candies
• [Moderate] Fibonacci Modified
• [Moderate] Hexagonal Grid
• [Moderate] Knapsack
• [Moderate] Red John is Back
• [Moderate] Stock Maximize
• [Moderate] Substring Diff
• [Moderate] The Coin Change Problem
• [Moderate] The Longest Common Subsequence
• [Moderate] XOR and SUM
• [Advanced] The Longest Increasing Subsequence
• [Expert] Lucky Numbers
• …..

## Strings

• [Easy] Alternating Characters
• [Easy] Anagram
• [Easy] Beautiful Binary String
• [Easy] Caesar Cipher
• [Easy] Camel Case
• [Easy] Funny String
• [Easy] Game of Thrones – I
• [Easy] Gem Stones
• [Easy] Make It Anagram
• [Easy] Mars Exploration
• [Easy] Palindrome Index
• [Easy] Pangrams
• [Easy] Richie Rich
• [Easy] String Construction
• [Easy] Super Reduced String
• [Easy] The Love-Letter Mystery
• [Easy] Two Strings
• [Moderate] Bear and Steady Game
• [Moderate] Sherlock and Anagrams
• [Moderate] Yet Another KPM Problem
• [Difficult] Ashton and String
• [Difficult] Build a Palindrome
• [Difficult] Build a String
• [Difficult] Circular Palindromes
• [Difficult] Common Child
• [Difficult] Count Strings
• [Difficult] Find Strings
• [Difficult] Gridland Provinces
• [Difficult] Letter Islands
• [Difficult] Morgan and a String
• [Difficult] Palindromic Border
• [Difficult] Pseudo-Isomorphic Substrings
• [Difficult] Sherlock and Valid String
• [Difficult] Save Humanity
• [Difficult] String Function Calculation
• [Difficult] String Similarity
• [Difficult] Two Strings Game
• [Difficult] Two Two
• ….

## Bit Manipulation

• [Easy] Cipher
• [Easy] Flipping Bits
• [Easy] Lonely Integer
• [Moderate] A or B
• [Moderate] AND Product
• [Moderate] Cipher
• [Moderate] Counter Game
• [Moderate] Sansa and XOR
• [Moderate] What’s Next?
• [Moderate] Xor-sequence
• [Difficult] 2’s Complement
• [Difficult] Changing Bits
• [Difficult] Hamming Distance
• [Difficult] String Transmission
• [Difficult] Manipulative Numbers
• [Difficult] Stone Game
• [Difficult] String Transmission
• [Difficult] XOR Key
• [Difficult] XOR Subsequences
• [Difficult] Xoring Ninja

## Combinatorics

• [Easy] A Chocolate Fiesta
• [Easy] Building a List
• [Easy] Connecting Towns
• [Easy] Handshake
• [Easy] Minimum Draws
• [Easy] Merge List
• [Easy] Picking Cards

## Queues

• Tom English

Hi Martin,
Thanks for the solutions. I am an intermediate-to-advanced developer. I’ve been trying the challenges at Hackerrank and I’ve done several. Thanks for posting your solutions, especially since their in C++ since that’s what I use for Hackerrank. I was wondering have you tried the Morgan and a String problem (Strings category)? I’ve been beating my head against it for a while now but I can only get it to pass 9 of 17 test cases. Test cases 10-17 fail for me. I’ve downloaded test cases 10 and 11 to debug on my PC and as far as I can tell my code is correct. But obviously there is a solution that is evading me. Have you tried it? Do you have a solution for it? I’ve posted my code on the discussion forum for the problem (user te777) so you can look at it if you have the time. I guess you could post back here or on the discussion forum if you have any suggestions on possible fixes for me. Thanks, I really would appreciate your help.

• Trần Minh Tấn

Hi Guys,
I have a question hackerrank with detail:

Billy is testing an experimental slot machine that has unequal spinning wheels that shift positions at random. A wheel can have any number of stops from 1 to 9. If it has f stops, then its stops are numbered from 1 to f. After every spin, every wheel will show one stop number in the slot machine’s window, but the order of the wheels at the window will be random. On any spin, each stop of a wheel has the same probability of stopping at the window as every other stop on that wheel. Billy runs a series of up to 50 test spins and writes down the all the digits visible in the window.

Given the list all the test results, find the minimum possible total number of stops on all the wheels inside the machine that could have given rise to that series of results.

Format:
The code to parse the input and print the output is already provided. You are to complete the function slotGame in the language chosen, which takes an array of strings of digits and returns an integer.

Constraints:
The test results will contain between 1 and 50 spin notes, inclusive.
Each spin note will contain between 1 and 50 digits, inclusive.
All notes contain the same number of characters.
Each digit in each element will be one of ‘1’-‘9’.

Sample Input #00:
4
137
364
115
724
Sample Output #00:
14

Explanation #00:
The numbers showing are:
1, 3 and 7 in the first spin
3, 6 and 4 in the second spin
1, 1 and 5 in the third spin
7, 2 and 4 in the fourth spin.

The three wheels may have 3, 4 and 7 stops giving a total of 14 faces. Any fewer stops would have failed to give the results in the input.
Sample Input #01:
4
1112
1111
1211
1111
Sample Output #01:
5
Explanation #01:
Three wheels with one stop each one with two stops could have produced the results.

• I haven’t seen this task yet. Do you have a link? Google is not of much help either. Is it part of any ongoing competition on HR?

• gvs chaitanya

HI , martin can u please post the solutons for Breadth First Search: Shortest Reach,Prim’s : Special Subtree

• The task is to implement a *minimum spanning tree*. You can use either Kruskal’s or Primm’s algorithm to do so. There are plenty of implementations online. Keep in mind that Kruskal might be hard as you need some disjoint-set structure (such as Union-Find). I have not yet started the graph theory so you will have to solve that. If you do, consider sharing it here 😉

• gvs chaitanya

ok sure !wil be sharing it once i finish it .

Cheers

• Sidharth Samant

Hi Martin. I noticed you haven’t posted the code for Bigger is Greater. It’s part of the sorting domain now. Are you working on it or did you intentionally leave it because it’s too easy?

• I have many solutions in C++ from older days but I never translated them to Python. This is one of them. I’ve done it now on your request: http://www.martinkysel.com/hackerrank-bigger-is-greater-solution/

• Sidharth Samant

Oh, that’s okay! I’d already done it. But thanks anyway! 🙂
Just one question, I tried using the itertools.permutations class to solve this, basically calling next() on the permutations generator to go to the next permutation, but it didn’t work. So I tried to print out the entire list of permutations in lexicographic order, to see what’s going on behind the scenes, like they show in the example here – https://docs.python.org/2/library/itertools.html#itertools.permutations (permutations of ‘abcd’ of size 2). But what I noticed, is that when I did permutations(‘abcd’), it printed the 4! permutations in order. But when I passed in ‘bdac’ as the argument, it didn’t print in order. Do you have any idea about that?

• Yes. The param r in itertooms.permutations does not define the number of permutations but the number of elements from the array that should be used.

permutations(“ABC”, 2) generates AB, BC, AC and yields the first of them. You might just need to consume the first.

``` from itertools import permutations s = list("CDBA") print "---list of all perm---" for value in permutations(s): print value print "--- list of perm of size 2---" for value in permutations(s, 2): print value ```

```print "---- get next perm ----" print next(permutations(s)) ```

• Sidharth Samant

I see. Thank you!

• Kusu025

Hi Martin..Do you have Hackerrank QA challenge Questions & Answers..If you have please share it with me

• Jay Patel

Hi Martin,
Can you please provide code for Xor-sequence in Python3 in O(1)? Or just provide any hint about that?
Thanks.

• theslomo

Great solutions. By any chance you know anyone who answered these challenges in Swift?

• Sidharth Samant

Hi Martin, have you by any chance attempted the “Larry’s Array” problem? I have been trying to solve it by reading up on the parity of a permutation and inversions, but just can’t figure it out. Reading through some code posted on the HackerRank forums also doesn’t help. For example – https://www.hackerrank.com/contests/101hack35/challenges/larrys-array/submissions/code/5545135 – this code passes the tests, but fails on (2 3 1).

• I have not solved this exact problem but I have seen a similar one in the past. You have already figured out that you need to count the number of inversions (bigger elements preceding smaller elements, and the number of smaller after bigger ones). I have a few spare minutes, so I will attempt to solve it now.

• here you go
``` #!/usr/bin/py def get_inversion(n, values): count = 0 for i in xrange(0, n-1): for j in xrange(i+1, n): if (values[i] > values[j]): count += 1 return count```

``` ```

```if __name__ == '__main__': t = input() for _ in xrange(t): n = input() values = map(int, raw_input().split()) if get_inversion(n, values) & 1: print "NO" else: print "YES" ```

• Sidharth Samant

Thank you so much! I had made a mistake when I was working out on the algorithm on paper. It makes sense now. Thank you!

• Vidhi Katkoria

Hi Martin, could help me out with the coffee break string generation problem? This is the link to the problem:
https://www.hackerrank.com/contests/cisco-icode/challenges/sherlock-and-string-generation

• Hi Vidhi,

I had a quick look today, so that I do not tell you something wrong, here goes:

The rules are explained pretty clearly. There are three rules
1) each element has to occur at least once
2) odd elements occur odd number of times, even even times
3) the string has to be of length N

Let us compact those rules into examples:
1+2) mean that each element has to occur at least 1 or 2 times. The minimal string (a suffix really) is “abbcddeff” etc.
2+3) because of the length limitation, the string can only be the length of the minimal viable suffix (explained above) + a multiply of 2. You could add 2xA, 2xB etc making it “abbcddeffaa” for example. But not “abbcddeffa” because that would violate rule 2).
extra) the string has to be the minimal lexical variant of all the above rules. That means that you want to be pre-pending A’s to your string. Aka the previous one becomes “aaabbcddeff”.

Following these rules you should be able to write an algorithm that solves the problem.

Cheers! Martin

• Vidhi Katkoria

Thank you, Martin. This is a lot simpler than what I was thinking.

• yes it is. Given it’s a “Hard” task for 100pt, I would expect to spend hours on it. But it is a 10min task.

• yes it is. Given it’s a “Hard” task for 100pt, I would expect to spend hours on it. But it is a 10min task.

• Shubendu Sharma

hi martin,
After the first movie became a super hit, Catherine becomes a celebrity at her university, and her facebook profile is full of friend requests. Catherine has accepted all the requests. But her parents worried about all the attention she is getting from certain people, so they ask her to delete some of the people from her friend list.

To avoid a ‘scene’, Catherine decides to remove some friends from her friend list, since she knows the popularity of each of the friend she has, she uses an algorithm to delete a friend. If the popularity of one friend is less than the popularity of the immediate next friend, then delete that friend. If this condition is not satisfied at all, then delete the last friend. Please help Catherine to implement this algorithm.

Input:
First line of each test case contains N, the number of friends Catherine currently has and K, the number of friends Catherine decides to delete. Next lines contain popularity of her friends separated by space.

Output:
For each test case print N-K numbers which represent popularity of Catherine friend’s after deleting K friends.

Constraints
0<=K< N
0<=popularity_of_friend<=100

NOTE:
Order of friends after deleting exactly K friends should be maintained as given in input.

SAMPLE INPUT 1

3 1

3 100 1

SAMPLE OUTPUT 1

100 1

SAMPLE INPUT 3

5 6

SAMPLE OUTPUT 3

Invalid Input

SAMPLE INPUT 4

3 1

3 101

SAMPLE OUTPUT 4

Invalid Input: The popularity should be between 0 and 100

• sandeep

Hi martin could you help me with my code for the hacker rank question https://www.hackerrank.com/challenges/bus-station/copy-from/47189573

here is my solution
http://ideone.com/EUcoTL
this is giving floating point exception for test case 7 and 22 on my local .

• saikumar

can u solve this
Choose the starting point of the Fibonacci series as 1, 1
if n value is not present in the series, print the series below n

Number N

Constraints

N>1

Output Format

Fibonacci series numbers

Sample Input 0

3

Sample Output 0

1, 1, 2, 3

Sample Input 1

10

Sample Output 1

1, 1, 2, 3, 5, 8

• Teja Legend

can u solve this?
In a social network, online communities refer to the group of people with an interest towards the same topic. People connect with each other in a social network. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.

We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.

Input Format

Input will consist of three parts, viz.

The total number of people on the social network (N)
Queries
C I J, connect I and J
Q 0 0, print the number of communities with even member-count
-1 will represent end of input.
Constraints

1<=N<=10^6

1<=I, J<=N

• Sounds like a Union-Find application.

• Aayush

Hi Martin,
Can you please help me in solving this, ” make a compiler using assembly language and a keyboard simulator”. How do i do it?

• is this a task in HR? Do you have a link?