Interview Question
Software Engineer InternsCountry: United States
Then you can calculate factorials and inverse-factorials (modulo some large prime).
x/factorial(y) = x*inverse-factorial(y) (mod p), where p is a prime. See Fermat's Little Theorem.
To find the multiplicative-inverse of a number 'a', we do the following.
a^p = a (mod p) ->>> follows from Fermat's little theorem.
a^(p-1) = 1 (mod p)
a^(p-2) = inverse(a) (mod p)
You'll have to preprocess the factorials and inverse-factorials in arrays using the following relation:
factorial[i] = i*factorial[i-1];
Alternatively you could compute the actual answer without actually computing the factorials. Since the answer is integral, you can intelligently divide and multiply things so that the intermediate result never overflows the integer range.
@all who voted down.... could you please tell me where my solution lags? .... I think its better than generating all the permutations which has an exponential complexity.
And yes if length of the string is 10^6 then all the solutions which depend on generating permutations can never give the answer.
If the length of string is 'n' then number of permutations = n!
If length of string is 30 (a very very small number) then:
number of permutations = 30! = 2.6525286e+32
Thus on a modern machine it will require (nearly) 10^16 years to give the answer for string of length = 30 (Yes! THIRTY).
This is a coding competition question: w w w.hackerrank.com/contests/july13/challenges/game-of-throne-ii
I will make the same argument that you did. Imagine the string is 200 characters long, then 100! will overflow even with 64bit unsigned long/integer. The question in the contest says the length of the string is: 1<=length of string <= 10^5, so imagine a string 100000 characters long and calculating 50000!.
I am sure there must be a better way of doing this.
IMO, EOF's solution is an optimized one. The logic to solve the problem is apparently correct, though the technical issues like overflowing can be handled by using modular arithmetic as suggested by him.
For every possible permutation of the string where here every permutation of the string means an anagram then for a particular permutation or anagram we check whether it is a palindrome or not in the following way:
a. Divide the string into two halves.
b. Check for the left half if it is palindrome by again recursively dividing that left half further. Note that here the base case would be when at last two characters are are left and they are palindrome. Then when the recursive call returns check for the right half of this left half. And also note that when a single character is left then it is already a palindrome. (Single characters are always palindromes of themselves).
c. Similarly check for the right half.
d. Thus if this anagram is palindrome increase the count of palindromes.
e. At last return the number of palindromes that can occur with all the anagrams of the string.
Generate all possible anagrams, add it to a Set (to avoid duplicates, in case of repeated alphabets) and check for Palindrome string individually..
public class PalindromeAnagrams {
private static Set<String> anagrams = new HashSet<String>();
public static void main(String[] args)
{
String str = "ABBA";
permutation("", str);
System.out.println("ANAGRMAS\n-------------------");
for(String s : anagrams)
{
System.out.println(s);
}
System.out.println("\n\nPALINDROME\n-------------------");
checkForPalindroms();
}
private static void permutation(String prefix, String str)
{
int n = str.length();
if (n == 0)
{
anagrams.add(prefix);
}
else
{
for (int i = 0; i < n; i++)
{
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1));
}
}
}
private static void checkForPalindroms()
{
for(String str : anagrams)
{
boolean isPalindrome = false;
int middle = str.length()/2;
if(middle % 2 == 0)
{
isPalindrome = isPalindrome(str.substring(0, middle), str.substring(middle, str.length()));
}
else
{
isPalindrome = isPalindrome(str.substring(0, middle), str.substring(middle+1, str.length()));
}
if(isPalindrome)
{
System.out.println(str);
}
}
}
private static boolean isPalindrome(String firstHalf, String secondHalf)
{
StringBuilder sb = new StringBuilder(secondHalf);
return firstHalf.equalsIgnoreCase(sb.reverse().toString());
}
}
import java.util.HashMap;
import java.util.Map.Entry;
public class CountPalindrome {
public static void main(String[] args) {
String input = "neveroddoreven";
CountPalindrome cp = new CountPalindrome();
char[] inpChars = new char[input.length()];
input.getChars(0, input.length(), inpChars, 0);
System.out.println(cp.countPalinAnags(inpChars));
}
public int countPalinAnags(char[] inp) {
HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
for (int i = 0; i < inp.length; i++) {
Integer val = hm.get(inp[i]);
if (null == val)
hm.put(inp[i], 1);
else
hm.put(inp[i], val + 1);
}
int oddCharCnt = 0;
int mirrCnt = 0;
int denom = 1;
for(Entry<Character, Integer> e : hm.entrySet()) {
int n = e.getValue();
if (n % 2 != 0)
oddCharCnt++;
if (oddCharCnt > 1)
return 0;
n /= 2;
e.setValue(n);
mirrCnt += n;
denom *= factorial(n);
}
return factorial(mirrCnt) / denom;
}
private int factorial(int n) {
int res = 1;
while (n > 0) {
res *= n;
n -= 1;
}
return res;
}
}
-Calculate the length of string. [length]
-As Palindrome consists of two kind of char... at most only one char can be single else it should be couple chars
For ex: abbcbba, abbbba,ababbcbbaba
-now get the no. of couple char [noOfCoupleChar]
-and get the no of non-coupled char [noOfNonCoupleChar]
for Ex: abbababbac
no of char 'a'=4
no of char 'b'=5
no of char 'c'=1
hence
noOfCoupleChar = 8 and
noOfNonCoupleChar =2
-get the no of all palindrome anagrams having length = noOfCoupleChar + 1
[facorialOf(noOfCoupleChar / 2)] / [factorialOf(noOfOccuranceOfChar(a)/2)*factorialOf(noOfOccuranceOfChar(b)/2)..... ]*[noOfNonCoupleChar ]
-same as get the no of all palindrome anagrams having length = noOfCoupleChar
[facorialOf(noOfCoupleChar / 2)] / [factorialOf(noOfOccuranceOfChar(a)/2)*factorialOf(noOfOccuranceOfChar(b)/2)..... ]
-like as we can calculate all possible palindromes of various length
<End Of Logic>
For Ex:
String: abbabcabba
no of couple # 4(a) + 4(b) = 8
no of non couple # 1(b) + 1(c) = 2
no of palindromes for length = 8+1 =>
[fact(4)]/[fact(2)*fact(2)]*[2] = 12
like wise calculate for all possible length of palindrome.
I think your question is >>> "Find the number of anagrams of a given string which are palindrome".
Here is how I approach:
We assume that the string will contain only lowercase characters of the English alphabet.
1) Let the length of the string be 'n'.
2) Declare a count[0...25] array and count the number of occurrences of each character in the string. Note that there can be atmost one character with odd number of occurrences and it has to be in the middle of palindrome. Fix this character at the middle of the anagram string and reduce its count by 1. Now every character has even number of occurrences.
3) Divide the count array by 2 (i.e. reduce the count of every character by half).
4) We have to arrange these half of the characters in the first half of the anagram (and the other half has to be exactly the reverse of the first half). Now the problem reduces to >>> Find number of ways of arranging count[0] a's, count[1] b's, ... , count[25] z's in floor(n/2) positions.
Please correct me if I've made a mistake.
- EOF July 06, 2013