Google Interview Question
Country: United States
Interview Type: Phone Interview
can any body explain this code? What is the overlapping problem of the subproblem. More precisely, why {dp[i-2] + d[i-1]} gives out the combination number for d[i]?
def numStrings(s, n):
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
num = int(s[n-1] * 10) + int(s[n])
s = ( num >=10 and num <=25)? 3 : 2
return s
else:
num = int(s[n-1] * 10) + int(s[n])
s = (num >=10 and num <=25)?1 : 2
return s + numStrings(s, n-2)
At any pt i where i > 1, you have a chance to consider char at i-1 and i together if they form a number between 10 and 25 both inclusive, if so then you have one extra string along with 2 others formed by single chars at i-1 and i, to which you will add strings formed at i-2. If you draw out the recursion tree you can see that there are overlapping calls which ultimately leads to the DP soln above
def numStrings(number):
n = len(number)
print "n is: ", n
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
num = int(number[-2])* 10 + int(number[-1])
s = 3 if (num >=10 and num <= 25) else 2
print "num now: ", num
print "s is: ", s
return s
else:
num = int(number[-2])* 10 + int(number[-1])
s = 3 if (num >=10 and num <=25) else 2
print "num now: ", num
print "s is: ", s
return (s + numStrings(number[:-1]))
Improved the code above a bit
@Anonymous and @saurav: I don't agree with your solution
if string = "25", you can either generate "CF" or "Z", => you suggested 3
if string = "55", you can only generate "FF",=> you suggested 2
I don't think the questions is asking for sub-strings, if you want to consider sub-strings, then you have to count the number of distinct strings,
Am I missing something here?
I'm afraid the answers given are wrong,
consider the string "11111" (5 characters), here are the strings you can generate:
1- "BBBBB"
2- "BBBL"
3- "BBLB"
4- "BLBB"
5- "LBBB"
6- "BLL"
7- "LBL"
8- "LLB"
NONE OF THE ANSWERS ABOVE GENERATES THIS
This solution clearly does not have an optimal substructure because it ignores the presence of duplicate characters when using the smaller substring to obtain the count for a larger substring. It would only work if all characters were unique.
This solution clearly does not work because it does not have an optimal substructure. It fails every time the string has duplicate characters.
Tested with a very basic sample: "123" your solution returns 3, but shouldn't it be: 5? - 1 = B, 2 = C, 3 = D, 12 = M and 23 = X ?
We will use dynamic programming by creating an int[] count array, where each element, count[i], stores the number of strings we can make with a substring starting from i. For example, input = "01234", count[3] = # of diff strings of "34", count[2] = # of diff string of "234".
To find count[0], we use a the following relationship:
Number of different string of "1234" = number of different string of "234" + number of different string of "34" if "12" is in the mapping lookup table.
Let LU be the lookup table containing the keys, and let N = input length. Then, initialize count[N] = 1, count[N-1] = 1 and follow the relationship
count[i] = count[i+1] + LU.containsKey(input.substring[i, i+2])? count[i+2]: 0;
Loop through i from N-2 to 0.
Finally, count[0] is what we are looking for.
here is the c++ code
int CountStrings( char * s, int n )
{
if ( n < 2 )
{
return 1;
}
int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
if ( ( number >= 10 ) && ( number <= 25 ) )
{
return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
}
else
{
return CountStrings( s, n-1 );
}
}
int CountStrings( char * s, int n )
{
if ( n < 2 )
{
return 1;
}
int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
if ( ( number >= 10 ) && ( number <= 25 ) )
{
return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
}
else
{
return CountStrings( s, n-1 );
}
}
This is a linear combinatorics question
given 2 digit numbers that are > 10 and < 25 for example, count the number of adjacent numbers:
22222 = 5 adjacent numbers
1111 = 4 adjacent numbers
1101 = 2 adjacent numbers
it becomes a n choose k. What that means is for a string of 22222 the number of combinations is 5 choose 2 (since there's 2 possibilities for each pair).
given that information the problem becomes easier to understand.
Step 1: iterate through the string by pairs for instance:
[22]222 -> 2[22]222
count the number of continuos pairs >10 < 25 and store them in a hashmap. So you would have the key be the n in (n choose 2) and the value is the number of times the continuous pair has been seen.
At the end, iterate over the hash map and add all the numbers ignoring singles.
Example:
2205022
220 = 3 choose 2
22 = 2 (because there's 2 values here)
So the answer is 7 for that example string
public static int noOfStringsFromIntegerString(String s,int index,int length)
{ int count =0;
if(index+1>=length)
count = 1;
else {
count = noOfStringsFromIntegerString(s, index+1, length);
int temp = Integer.parseInt( s.substring(index,index+2));
if(temp < 26){
count += noOfStringsFromIntegerString(s, index+2, length);
}
}
return count;
}
I think you have a mistake because you also consider the case that numbers can also be written in the form 03, 04, 05... I don't suppose that this is the case. To avoid this stuff you should add the statement
Integer.parseInt(s.substring(index, index + 1)) > 0
into your "if" which checks if temp is less than 26.
public static int noOfStringsFromIntegerString(String s,int index,int length)
{ int count =0;
if(index+1>=length)
count = 1;
else {
count = noOfStringsFromIntegerString(s, index+1, length);
int temp = Integer.parseInt( s.substring(index,index+2));
if(temp < 26){
count += noOfStringsFromIntegerString(s, index+2, length);
}
}
return count;
}
C++ DP solutions with O(n) space and O(1) space
// O(n) time, O(n) space
int CountPossibleStrings(const string &s) {
vector<int> cnt(s.size()+1, 1);
for (int i = s.size()-2; i >= 0; --i) {
cnt[i] = cnt[i+1];
if (s[i] == '1' || (s[i] == '2' && s[i+1] <= '5'))
cnt[i] += cnt[i+2];
}
return cnt[0];
}
// O(n) time, O(1) space
int CountPossibleStringsO1Space(const string &s) {
int cnt[] = {1, 1}, slot = 0;
for (int i = s.size()-2; i >= 0; --i, ++slot) {
int v = cnt[slot%2];
if (s[i] == '1' || (s[i] == '2' && s[i+1] <= '5'))
v += cnt[(slot+1)%2];
cnt[(slot+1)%2] = v;
}
return cnt[slot%2];
}
Perform DFS via reursion or stack. At each step on can either (i) use one digit or (ii) use two digits to map to char. Well not actually, be careful because two digits can be used if and only if the first digit is 1 or if the first digit is 2 and the following is 0-5.
A sample code is shown below:
public int howMany(String s) {
return howMany(s, 0);
}
private int howMany(String s, int k) {
int N = s.length();
if (k >= N) return 0;
int cnt = 1;
cnt += howMany(s, k+1);
if (k == N-1) return cnt;
char c = s.charAt(k);
char d = s.charAt(k+1);
if (c == '1' || (c == '2' && d <= '5'))
cnt += howMany(s, k+2);
return cnt;
}
This is a non-recursive version:
Based on this function
f(n)(k) means
for a string of length n in which any adjacent character are combinable,
the solution number of splitting it so that there k substring with a pair of character while others of one character.
Then.
f(n)(0) = 1
f(n)(1) = n-1
f(n)(k) = f(n-2)(k-1) + f(n-3)(k-1) + ... + f(2k-2)(k-1)
f(n)(n/2) = 1 if n is oven else f[l-2][l/2-1]
This is a simple implementation:
#The string can be divided into 'super substring'
# 11111121, is a kind of super substring
# any adjacent unit in super substring is combinable.
#calculate all possible combination of super_substring
data_dict = {1:[1]}
# l is length of super substring
def solv_super_substring(l):
if l <= 1:
return
data_dict[l] = [0] * (l/2+1)
data_dict[l][0] = 1
data_dict[l][1] = l-1
for i in xrange(2, l/2):
for j in xrange((i-1)*2, l-1):
data_dict[l][i] += data_dict[j][i-1]
if l % 2 == 1:
data_dict[l][l/2] = 1+data_dict[l-2][l/2-1]
else:
data_dict[l][l/2] = 1
def extract_super_substring(s):
ssstr = []
tmp = ''
lofs = len(s)
for c in xrange(lofs):
if s[c] in '12':
tmp += s[c]
continue
elif s[c] in '3456' and len(tmp) > 0:
tmp += s[c]
ssstr.append(tmp)
tmp = ''
return ssstr
#test
if __name__ == '__main__':
s = '123121241291'
sstr = extract_super_substring(s)
print s
print sstr
lofss = map(lambda x: len(x), sstr)
ml = max(lofss)
for i in xrange(ml+1):
solv_super_substring(i)
print data_dict
res = []
for l in lofss:
res.append(sum(data_dict[l]))
print res
r = 1
for i in res:
r *= i
print r
def countPossibleStrings(str):
strNumSoFar = [0 for i in xrange(0, len(str))]
for i in xrange(0, len(str)):
if (i > 0):
if (strNumSoFar[i-1] > 0):
strNumSoFar[i] += strNumSoFar[i-1]
else:
strNumSoFar[i] = 1
if (i > 1):
if (strNumSoFar[i-2] > 0 and int(str[i-1]) > 0 and int(str[i-1])*10 + int(str[i])< 26):
strNumSoFar[i] += strNumSoFar[i-2]
else:
if (i > 0):
if (int(str[i-1]) > 0 and int(str[i-1])*10 + int(str[i]) < 26):
strNumSoFar[i] += 1
print strNumSoFar[len(str) - 1]
countPossibleStrings("132493820173849029382910382")
public int countStrings(String string) {
if("".equals(string) || (string == null)) {
return 0;
} else if(string.length() == 1) {
return 1;
} else {
int twoDigits = Integer.valueOf(string.substring(0, 2));
if((twoDigits >= 10) && (twoDigits <= 25)) {
return 1 + countStrings(string.substring(1)) + countStrings(string.substring(2));
} else {
return 1 + countStrings(string.substring(1));
}
}
}
// 1 -> B
// 13 -> BD, N
// 132 -> BDC, NC
// 112 -> BBC, LC, BM
def stringFinder(s:String):List[String] = {
// convert integer String to a letter
val is2letter: String => String = (si:String) =>('a' + si.toInt).asInstanceOf[Char].toString
implicit def cToS(c:Char):String = c.toString
if(s.length == 1) {
List(is2letter(s))
}else if(s.length == 2){
val s1 = is2letter(s(0)) + is2letter(s(1))
val s2:String = s match{
case a if a.toInt >= 'a'-'a' && a.toInt <= 'z'-'a'=> is2letter(a)
case _ =>""
}
if(!s2.isEmpty) List(s1,s2) else List(s1)
} else {
var results = List[String]()
val s0 = is2letter(s(0))
for(_s:String <- stringFinder(s.tail)) {
results = (s0+_s) :: results
}
if(s0 != "a") {
s.substring(0,2) match{
case a if a.toInt >= 'a'-'a' && a.toInt <= 'z'-'a'=> {
val s1 = is2letter(a)
for(_s:String <-stringFinder(s.tail.tail)) {
results = (s1+_s) :: results
}
}
case _ =>""
}
}
results
}
}
c# implementations
int CountOfPossible(string input)
{
if (String.IsNullOrWhiteSpace(input))
{
return 0;
}
int count = input.Length; // each number corresponds to letters
for (int i = 0; i < input.Length - 2; i++)
{
string sub = input.Substring(i, 2);
int num = ConvertToNum(sub);
if (10 <= num && num <= 25) // the two digits neighbors
{
count++;
}
}
return count;
}
int ConvertToNum(string input)
{
int parsedInt = -1;
int.TryParse(input, out parsedInt);
return parsedInt;
}
import java.util.Map;
import java.util.TreeMap;
public class StringCounter {
private Map<String, Character> myMap;
public StringCounter() {
myMap = new TreeMap<String, Character>();
//Builds the map: 0 -> A, ..., 25->Z
for(int i = 0; i < 26; i++) {
myMap.put(i+"", (char) (i+65));
}
}
//slow recursive strategy.
public int countStrings(String input) {
if(input.isEmpty()) return 1;
int num = countStrings(input.substring(1));
if(input.length() >=2 && myMap.containsKey(input.substring(0, 2)))
num += countStrings(input.substring(2));
return num;
}
//DP Soln - O(n) space, O(n) time
public int countStringsDP(String input) {
int[] numStrings = new int[input.length()];
numStrings[0] = 1;
numStrings[1] = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
for(int i = 2; i < input.length(); i++) {
numStrings[i] = numStrings[i-1];
if(myMap.containsKey(input.substring(i-1, i+1)))
numStrings[i] += numStrings[i-2];
}
return numStrings[input.length()-1];
}
//DP Soln - O(n) time, constant space
public int countStringsDP2(String input) {
int val1 = 1;
int val2 = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
for(int i = 2; i < input.length(); i++) {
int temp = val2;
if(myMap.containsKey(input.substring(i-1, i+1)))
temp += val1;
val1 = val2;
val2 = temp;
}
return val2;
}
}
Solution with Fibonacci Terms:
Sequences for continuous two digit matching numbers can be broken down as Fibonacci term, and the final result is the multiplication of each such terms.
Example:
11 -> 2 F(3)
111 -> 3 F(4)
1111 -> 5 F(5)
11111 -> 8 F(6)
.....
......
n consecutive -> F(n-1)
so, 110511 -> F(4)*F(3) = 3*2 = 6
Here are the 6 variations:
BBAFBB
LAFBB
BKFBB
BBAFL
LAFL
BKFL
Here is the O(n) time and O(1) space solution
int getVariation(char* array)
{
int retVal = 1;
int len = strlen(array);
int prevSum=1, currSum=1;
for (int i=0; i< len; i++)
{
int twoDigitNum = -1;
if( i>0 && array[i-1] > '0')
{
twoDigitNum = (array[i-1]-'0')*10 + array[i] - '0';
}
if (twoDigitNum >=10 && twoDigitNum <=25)
{
int tmp = currSum;
currSum += prevSum;
prevSum = tmp;
}
else
{
retVal *= currSum;
currSum = 1;
prevSum = 1;
}
}
retVal *= currSum;
return retVal;
}
public static char[] getChars(String s) {
char[] charsExists = new char[26];
if (s == null)
return charsExists;
else if (s.length() < 2) {
charsExists[Character.getNumericValue(s.charAt(0))] = (char) ((65 + Character
.getNumericValue(s.charAt(0))));
} else {
for (int i = 0; i < s.length(); i++) {
if (charsExists[Character.getNumericValue(s.charAt(i))] == '\u0000') {
charsExists[Character.getNumericValue(s.charAt(i))] = (char) ((65 + Character
.getNumericValue(s.charAt(i))));
/* System.out.println(" 1 :"
+ Character.getNumericValue(s.charAt(i)));*/
} else {
System.out.println("character Exists + "
+ String.valueOf(s.charAt(i)));
}
// int num = Character.getNumericValue(s.charAt(i) + s.charAt(i
// + 1));
if (i != s.length() - 1) {
int num = Integer.parseInt(s.substring(i, i + 2));
//System.out.println("2 :" + num);
if (num < 26 && charsExists[num] == '\u0000') {
charsExists[num] = (char) (65 + num);
} else {
System.out
.println("character Exists or not valid number: "
+ num);
}
}
}
}
return charsExists;
}
Can be solved in O(n) time, both recursively and iteratively. Here is an iterative version:
import java.util.Scanner;
class NumToString {
public static void main (String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter the Number-string");
String str = s.nextLine();
char [] cArray = str.toCharArray();
int [] array = new int[str.length()];
for (int i = 0; i < array.length; i++) {
if (cArray[i] >= '0' && cArray[i] <= '9') {
array[i] = cArray[i] - '0';
}
else {
System.err.println("Wrong input. Exiting...");
}
}
int [] memArray = new int[array.length + 1];
memArray[array.length] = 1;
memArray[array.length - 1] = 1;
for (int i = array.length - 2; i >= 0; i--) {
if (array[i] > 2 || array[i] == 0 || (array[i] == 2 && array[i + 1] > 5)) {
memArray[i] = memArray[i + 1];
}
else {
memArray[i] = memArray[i + 1] + memArray[i + 2];
}
}
System.out.println("Number of strings possible = " + memArray[0]);
}
}
int get_combination_num(char* s) {
if (s == NULL) return -1;
int str_len = strlen(s);
if (str_len == 0) return 0;
int* dp = (int*)malloc(sizeof(int)*str_len);
if (dp == NULL) return -1;
int i;
dp[0] = 1;
for (i = 1; i < str_len; i++) {
dp[i] = dp[i-1];
int value = (s[i-1] - '0') * 10 + (s[i] - '0');
if (value >= 10 && value <= 25) {
dp[i] += (i-2 >= 0 ? dp[i-2] : 1);
}
}
int ret = dp[str_len-1];
free(dp);
return ret;
}
public int NumberOfPossibleStrings(String str){
if(str == null || str.length()==0) return 0;
if(str.length()==1)return 1;
if(str.length()==2)
if(str.charAt(0)<'3'&&str.charAt(0)>'0')return 2;
else return 1;
if(str.charAt(0)=='0'||str.charAt(0)>'2')
return NumberOfPossibleStrings(str.substring(1));
return NumberOfPossibleStrings(str.substring(1))+
NumberOfPossibleStrings(str.substring(2));
}
#include <iostream>
using namespace std;
int num2letter( char num0, char num1)
{
assert( num0 >= '0'|| num0 <= '9' );
assert( num1 >= '0'|| num1 <= '9' );
if (0
|| num0 > '2'
|| (num0 == '2') && (num1 > '5')
) {
return 0;
}
return 1;
}
int search_str( const char * str, int start, int end, int num_found ) {
int num = num_found;
if (start < end) {
num++; // the very first one
num += num2letter(str[start], str[end]);
num += search_str(str, start+1, end, num);
} else if (start == end) {
num ++; // last one char
}
return num;
}
int main() {
const char num_str[] = "132493820173849029382910382";
int str_num = search_str( num_str, 0, sizeof(num_str) - 1 - 1, 0);
cout << "number of string is " << str_num << endl;
}
Sorry. The above code is wrong. The fixed one using simple DP is below:
{
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int num2letter( char num0, char num1)
{
assert( num0 >= '0'|| num0 <= '9' );
assert( num1 >= '0'|| num1 <= '9' );
if (0
|| num0 > '2'
|| (num0 == '2') && (num1 > '5')
) {
return 0;
}
return 1;
}
int search_str( const string &input) {
int num = 0;
vector<int> A(input.size(), 0);
A[0] = 1;
for(int i=0; i< input.size() - 1; i++) {
A[i+1] = A[i] + 1 + num2letter(input[i], input[i+1]);
}
return A.back();
}
int main() {
const string input = "132493820173849029382910382";
cout << "input:" << input << endl;
int str_num = search_str(input);
cout << "number of sub string is " << str_num << endl;
const string input1 = "1234";
cout << "input1:" << input1 << endl;
str_num = search_str(input1);
cout << "number of sub string is " << str_num << endl;
}
}
# s non empty
def findComb(s):
# base cases:
if len(s) == 0:
return 1
elif len(s) == 1:
return 1
elif len(s) == 2:
if int(s) < 26:
return 2
else:
return 1
# recursive case, split the original string number to left and right
# total = findComb(left) * findComb(right) + \
# findComb(left[:-1]) * findComb(right[1:]) //if <26
else:
mid = len(s) / 2
# print mid
left = s[:mid]
right = s[mid:]
easyComb = findComb(left) * findComb(right)
addon = 0
if int(s[mid-1:mid+1]) < 26:
addon = findComb(left[:-1]) * findComb(right[1:])
return easyComb + addon
it should be simple to implement.
If english alphabets were from 1-99 then solution would have been (2n-1)
Since alphabets are till 25, we need to iterate through the list and figure out how many adjacent digits form a number more than 25 and exclude them from the ans.
number_of_string(int [] arr)
{
int exclude = 0;
for(int i=1;i<arr.length;i++)
{
if(arr[i-1]*10 + arr[i] > 25) exclude++;
}
return 2*arr.length -1 - exclude;
}
Only need to count numbers less than 26.
input: "132493820173849029382910382";
13, ...24, ... 20, ... 17, ... 10, ...
2^5 =32
output: 32
Only need to count numbers less or equal than 26
input: "132493820173849029382910382"
13, ... 24, ... 20, ...17,...13
2^5 = 32
output: 32
public class Main {
public static void printString(String prefix,String suffix, int len){
if(prefix.length()==len)
System.out.println(prefix);
else{
for(int i=0;i<suffix.length();i++){
char temp = (char)(Integer.parseInt(suffix.substring(0, 1)) + 65);
printString(prefix + String.valueOf(temp),suffix.substring(i+1, suffix.length()),len);
if(i<suffix.length()-1){
temp = (char)(Integer.parseInt(suffix.substring(0, 2)) + 65);
if(Integer.parseInt(suffix.substring(0, 2))<=25)
printString(prefix + String.valueOf(temp),suffix.substring(i+2, suffix.length()),len-1);
}
}
}
}
public static void main(String args[]){
String input = "1223" ;
String prefix="";
String suffix = "";
printString("",input,input.length());
}
}
1. assume the existence of a Hashtable<String, String> table that contains the mapping of a String number to String letter, e.g <"0", "A"> .... <"25", "Z">
2. assume the existence of a function:
private boolean isValid(String str) {
return table.containsKey(str);
}
3. The requested function:
public int CountCombo(String str) {
if(str.length <=0) return 0;
int ones = 0;
int twos = 0;
ones = (isValid(str.substring(0,1)))?1:0 + CountCombo(str.substring(1));
if(str.length>=2)
twos = (isValid(0,2))?1:0 + CountCombo(str.substring(2));
return ones + twos;
}
}
Solution in Java based on recursion:
public static int countStrings( char[] s, int n )
{
if ( n < 2 ) {
return 1;
}
int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
if ( ( number >= 10 ) && ( number <= 25 ) ) {
return 1 + countStrings( s, n-1 ) + countStrings( s, n-2 );
}
else {
return 1 + countStrings( s, n-1 );
}
}
int num_strings_o1space(const std::string& s)
{
int count_0 = 1;
int count_1 = 1;
int len = s.length();
for (auto i = 1; i < len; ++i)
{
int num = s[i-1] - '0';
num *= 10;
num += s[i] - '0';
if (s[i-1] != '0' && num < 26)
{
int count_new = count_0 + count_1;
count_0 = count_1;
count_1 = count_new;
}
else
{
count_0 = count_1;
}
}
return count_1;
}
Below is a recursive solution in Java. I've also added cache to avoid calculating the same things more than once.
In each step, we try to take both 1 character and 2 characters (in case it's in the legal range).
The complexity without the cache is: 2^n (since the recurrence relation is T(n) = T(n-1) + T(n-2) in case the 2 chars forms a valid key).
public static int countValidWords(String input) {
if (input == null || input.isEmpty()) {
return 0;
}
Map<String, String> dict = new HashMap<>();
for (int i = 0; i < 26; i++) {
char c = (char) ('A' + i);
dict.put(i + "", c + "");
}
// memorizing already calculated strings
Map<String, Integer> cache = new HashMap<>();
return countValidWordsHelper(input, dict, "", cache);
}
private static int countValidWordsHelper(String input, Map<String, String> dict, String currentWord, Map<String, Integer> cache) {
// you can comment out the if below to get a print of all options (using cache
// doesn't print the parts that are already in the cache
if (cache.containsKey(input)) {
return cache.get(input);
}
if (input.length() == 0) {
System.out.println(currentWord);
return 1;
}
if (input.length() == 1) {
System.out.println(currentWord + ", " + dict.get(input));
return 1;
}
String currentPartCode = input.substring(0, 2);
String currentPartStr = dict.get(currentPartCode);
int validaWordsMinusChar = countValidWordsHelper(input.substring(1), dict, currentWord + ", " + dict.get(input.substring(0, 1)), cache);
cache.put(input.substring(1), validaWordsMinusChar);
int validWordsMinusTwoChars = 0;
if (currentPartStr != null) {
validWordsMinusTwoChars = countValidWordsHelper(input.substring(2), dict, currentWord + ", " + currentPartStr, cache);
cache.put(input.substring(2), validWordsMinusTwoChars);
}
return validaWordsMinusChar + validWordsMinusTwoChars;
}
DP solution
If you wish, you can optimize it to use O(1) memory.
- GK January 15, 2015