HackerRank: Repeated String

Problem

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.

Given an integer, n, find and print the number of letter a‘s in the first letters of Lilah’s infinite string.

Input Format

The first line contains a single string, s.
The second line contains an integer, n.

Constraints

  • 1<=|s|<=100
  • 1<=|n|<=10^12
  • For 25% of the test cases, n <= 10^6

Output Format

Print a single integer denoting the number of letter a’s in the first letters of the infinite string created by repeating infinitely many times.

Sample Input 0

aba
10

Sample Output 0

7

Explanation 0

The first n = 10 letters of the infinite string are abaabaabaa. Because there are 7 a‘s, we print on a new line.

Sample Input 1

a
1000000000000

Sample Output 1

1000000000000

Explanation 1

Because all of the first n=1000000000000 letters of the infinite string are a, we print 1000000000000 on a new line.

Solution

What is the dumbest code ever made that has become famous?

BogoSort is a moderately well-known algorithm to sort a list. Here’s how it works:

  1. Put the elements of the list in a random order.
  2. Check if the list is sorted. If not, start over.

BogoSort has an average running time of O((n+1)!), which is not very good. It is also the rare algorithm which has NO worst-case running time; if the input has at least two elements, it is possible for the algorithm to run for any amount of time.

Source: Quora

CodeEval: Penultimate Word

Challenge Description:

Write a program which finds the next-to-last word in a string.

Input Sample:

Your program should accept as its first argument a path to a filename. Input example is the following

some line with text
another line

Each line has more than one word.

Output Sample:

Print the next-to-last word in the following way.

with
another

Solution:

 

CodeEval: Shortest Repetition

Challenge Description:

Write a program to determine the shortest repetition in a string.
A string is said to have period p if it can be formed by concatenating one or more repetitions of another string of length p. For example, the string “xyzxyzxyzxyz” has period 3, since it is formed by 4 repetitions of the string “xyz”. It also has periods 6 (two repetitions of “xyzxyz”) and 12 (one repetition of “xyzxyzxyzxyz”).

Input Sample:

Your program should accept as its first argument a path to a filename. Each line will contain a string of up to 80 non-blank characters. E.g.

abcabcabcabc
bcbcbcbcbcbcbcbcbcbcbcbcbcbc
dddddddddddddddddddd
adcdefg

Output Sample:

Print out the smallest period of the input string. E.g.

3
2
1
7

Solution:

 

HackerRank: The Love-Letter Mystery

Problem

James found a love letter his friend Harry has written for his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter into palindromes.

To do this, he follows two rules:

  1. He can reduce the value of a letter, e.g. he can change d to c, but he cannot change c to d.
  2. In order to form a palindrome, if he has to repeatedly reduce the value of a letter, he can do it until the letter becomes a. Once a letter has been changed to a, it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

Input Format

The first line contains an integer T, i.e., the number of test cases.
The next T lines will contain a string each. The strings do not contain any spaces.

Constraints
1T10
1 length of string 10^4
All characters are lower case English letters.

Output Format

A single line containing the number of minimum operations corresponding to each test case.

Sample Input

4
abc
abcba
abcd
cba

Sample Output

2
0
4
2

Explanation

  1. For the first test case, abc -> abb -> aba.
  2. For the second test case, abcba is already a palindromic string.
  3. For the third test case, abcd -> abcc -> abcb -> abca = abca -> abba.
  4. For the fourth test case, cba -> bba -> aba.

Solution