Java Code for String From Rank (TCS Codevita) | PrepInsta
String From Rank
TCS CodeVita is a coding competition organized by TCS every year, in search of world’s best coder. This is a global level coding competition in which coders from all around the world compete for the title of World’s Best Coder. String From Rank is one of the sample problem of this year TCS CodeVita season 11 competition.
Question -: Finding the rank of a string is the basic concept one needs to learn to understand Permutations. To understand it deeply why don’t we reverse engineer it?
Rank is nothing but the position of string among all the possible permutations without repetition of alphabets of length N in lexicographical order. The possible permutations without repetition of length 1 is a, b, c .. z, length 2 is ab, ac, ad .. zy, length 3 is abc, abd, abe, … bac, bad, bae … zyx, and so on. Now, given rank of a string and its length, compute the string that can be formed with all the alphabets. Check example section for more understanding.
Constraints
1 < = R < = 26!
1 < = N < = 26
Input
First line consists of a single integer R, which denotes the rank of the string
Second line consists of a single integer N, which denotes the length of string
Output
Print the string of length N and rank R in a single line
Note: Formed string may or may not be a meaningful word.
Time Limit (secs)
1
Examples
Example 1
Input
8
1
Output
h
Explanation
Rank and length of string are given as 8 and 1 respectively. As the length of string is 1, the one lettered word that can be formed from all the alphabets a to z are a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z.
When these words are ordered lexicographically, the word at 8th position or 8th rank would be ‘h’. Hence, the output is ‘h’.
Example 2
Input
29
2
Output
be
Explanation
Rank and length of string are given as 29 and 2 respectively. As the length of string is 2, the two lettered word that can be formed from all the alphabets a to z are ab, ac, ad, ae, af, ag, ah, ai, aj, ak, al, am, an, ao, ap, aq, ar, as, at, au, av, aw, ax, ay, az, ba, bc, bd, be, bf and so on till zy.
When these words are ordered lexicographically, the word at 29th position or 29th rank would be ‘be’. Hence, the output is ‘be’.
import java.util.Scanner;
public class RankToAlphabetString {
public static String generateStringFromRank(int rank, int length) {
StringBuilder result = new StringBuilder();
char[] alphabets = new char[26];
for (int i = 0; i < 26; ++i) {
alphabets[i] = (char) ('a' + i);
}
rank -= 1;
for (int i = 0; i < length; ++i) {
int index = rank % 26;
result.insert(0, alphabets[index]);
rank /= 26;
}
return result.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Input
int rank = scanner.nextInt();
int length = scanner.nextInt();
// Output
String resultString = generateStringFromRank(rank, length);
System.out.println(resultString);
scanner.close();
}
}
Login/Signup to comment