Google Interview Question
Software Engineer / DevelopersCountry: India
This is a really interesting solution. However, it seems that the inclusion-exclusion principle is actually causing you to do more work since you have to calculate F(s, {p, q}) many times. I suspect there's probably a way to use the dynamic programming and calculate whether the substring is a walprime in the inner loop. That would probably improve the performance by a constant multiple, especially since you'd get good cache performance on the inner loop.
Surely the search space for this problem will always be exponential no matter what you do? There are 3^(N-1) combinations for applying the operators, even if you were only solving the problem for those that factorise to a single prime so F runs in exponential time not polynomial time?
The time complexity of F(s, q) is obviously p * n^2. Since the primes set {2, 3, 5, 7} is unchanged, the whole time complexity is only related to the length of input string which can be considered as polynomial time.
Actually, you avoid Inclusion-Exclusion completely here, by using the dp state as
f(l,r,p,q,r,s) where p,q,r,s are the mod values take 2,3,5,7.
You need to find f(1,n,p,q,r,s) where p | q | r | s belongs to {0}.
for a given f(1,n,p,q,r,s) you can calculate it as matrix chain multiplication, by breaking into l,r;
f(L,R,p,q,r,s) = sum over( f(L,K,a,b,c,d)*f(K+1,R,e,f,c,d)) s.t ((a+e)%2 =p, (b+f)%3 = 0 etc.)
The total time complexity is O(N^3 * 2*3*5*7) since there are O(N^2*2*3*5*7) subproblems and each subproblem takes O(N) time to solve, if done in a bottom up way.
The optimal solution for this would be to solve by dynamics programming. I will solve it in a non-optimal way - by recursion. You can convert it to dynamic programming.
Start with a given number, split it by first char and rest and apply operator (+/- or none) between numbers and previously calculate sum and store output if wall prime
Helper Functions:
bool IsWallPrime(int num) // checks if given number os wall prime
int CoverToInt(char* str, int len=strlen(str)) // converts len numbers of str into integer. Default value is whole strlen(str) i.e. whole string
To Invoke:
int ans = 0;
CheckPrime("12345", ans, 0);
print ans;
void CheckWallPrime(char* str, int& ans, int prevSum)
{
if(*str == '\0')
{
return ;
}
// For original "123", think that we are here with prevSum = 1 & str = "23"
int sum = prevSum + ConvertToInt(str); // convert whole str to int (case 1 +23)
if(IsWallPrime(sum))
ans += 1;
sum = prevSum- ConvertToInt(str); // convert whole str to int : (case 1 - 23)
if(IsWallPrime(sum))
ans += 1;
int firstNumber = ConvertToInt(str, 1); // split by first char and rest of string
// Apply +ve operator
CheckWallPrime(str+1, ans, prevSum + firstNumber); // (case 1+2 + rest of string "3")
// Apply -ve operator
CheckWallPrime(str+1, ans, prevSum - firstNumber); // (case 1-2 + rest of string "3")
// Apply no operator:
CheckWallPrime(str+1, ans, prevSum*10 + firstNumber); // (case 12 + rest of string "3")
}
I am not handling the case for the first character of string. This code applies operator to it which it shouldn't. e.g. for "123", it will consider +123, -123 and 123 (no operator) which is not correct. I am not handling that to avoid code looking obscure
Do you know what the time bound on this is? I'm a moron with time bounds, but it seems like for each digit you're executing the function three times on the remaining digits and so forth. Is that O(3^n)? Please don't ream me for suggesting the idiotic, I'm having a hard time with this one.
Yes, 3 recursive calls means each input is evaluated 3 times
In turn each nesting will also get called 3 times, resulting in 3 ^ N.
Intuitive way to think why would be thinking of a family tree, where each person as 3 kids.
Thanks -- I was just having a hard time believing I was analyzing tha right.
I think this can be done in 2^(2n) or less. If you're able to gauge it clearly would you look at my solution posted below and see if I got that bound estimate right? I have been thinking it might actually be 2^(n logn) since the length of the 2^n digit permutations range evenly from 1-n.
Below is my C++ solution. For each string of length n there are 3^(n-1) expressions.
$ c++ wallprimes.cpp -o wallprimes
$ ./wallprimes 2 011 12345
6
64
#include <iostream>
#include <string>
#include <cstddef>
#include <cstdlib>
int count = 0;
bool is_wallprime(int n)
{
return n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0;
}
void count_wallprimes(int result, std::string n, const std::string& str, size_t index)
{
if (index < str.length())
{
// first digit uses no operator
if (index > 0)
{
count_wallprimes(result + atoi(n.c_str()), std::string("+") + str[index], str, index + 1);
count_wallprimes(result + atoi(n.c_str()), std::string("-") + str[index], str, index + 1);
}
count_wallprimes(result, n + str[index], str, index + 1);
}
else
{
// add or subtract remaining digits
result += atoi(n.c_str());
if (is_wallprime(result))
count++;
}
}
int main(int argc, char** argv)
{
for (int i = 2; i < argc; i++)
{
count = 0;
int result = 0;
std::string n("0");
size_t index = 0;
count_wallprimes(result, n, argv[i], index);
std::cout << count << std::endl;
}
return 0;
}
Hey u mentioned that for an n digit number there can be 3N - 1 valid expressions which can be formed. I tried this with a 4 digit number and didn't find it to be working. I found more than 3N - 1 expression that is more than 11 expressions. M i correct or m i missing anything in it. These are the expressions which I found for a 4 digit number 2357
2 + 3 + 5 + 7
2 - 3 - 5 - 7
2 + 3 + 5 - 7
2 + 3 - 5 + 7
2 - 3 + 5 + 7
2 - 3 - 5 + 7
2 + 3 - 5 - 7
23 + 57
23 - 57
2 + 35 + 7
2 - 35 - 7
2 + 35 - 7
2 - 35 + 7
235 + 7
235 - 7
2 + 357
2 - 357
2357
A typo correction in the original question: There are 3 ^ (n-1) i.e. 3 raise to (n-1) such combinations (instead of 3n-1). Why? For n digits, you have n-1 'empty' spaces between consecutive numbers. Where you can decide to put 3 of possible options (+/- or none). So total combinations are 3*3*... (n-1) times
Calculate possible set of possible sums, then count walprime
Let’s define dp as follows.
dp[i] is a set of possible number if we use i numbers.(dp[1] uses only input[0])
dp[0] should be only contain 0 because we don’t use any number.
Let’s define k as number of numbers we combine.
For example, if k = 3, we comine input[i - 0] and input[i-1] and input[i-2].
Also. let’s define numK as the combined number.
For example if k = 3, numK = input[i - 0]*100 + input[i-1]*10 + input[i-2]
We can build dp[i] for possible k using
//Calculate numK
//then
{{
for(int j:dp[i-k]){
dp[i].add(numK + j)
dp[i].add(numK - j)
}
}}
Then we can count walprimes in the set of dp[N+1].
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
class Walprime {
public static void add(Map<Integer,Integer> map,int key,int value){
if(map.containsKey(key)){
map.put(key, value % 1000000007 + map.get(key) % 1000000007);
}else{
map.put(key, value % 1000000007);
}
}
public static int solve(String inputString) {
int N = inputString.length();
int M = 2*3*5*7;
int[] input = new int[N];
for(int i = 0; i < N;i++){
input[i] = Integer.parseInt(inputString.charAt(N - i - 1) + "");
}
Map<Integer,Integer>[] dp = new Map[N + 1];
for (int i = 0; i <= N; i++) {
dp[i] = new HashMap<Integer, Integer>();
}
dp[0].put(0, 1);
//dp[1].put(input[0], 1);
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= i; k++) {
int numK = 0;
for (int l = i; l > i - k; l--) {
numK = numK * 10 + input[l - 1];
numK %= M;
}
for (int j : dp[i - k].keySet()) {
add(dp[i], (numK + j)%M, dp[i-k].get(j));
add(dp[i], (numK - j)%M, dp[i-k].get(j));
}
}
}
int answer = 0;
for (int i : dp[N].keySet()) {
if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0 || i == 0)
answer = answer + dp[N].get(i) % 1000000007;
}
return answer / 2; // dp[0] case will be double counted (+ and -). so we need to get half the answer
}
public static void main(String[] argv) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in),
1);
// We don’t assume illegal input.
int num = Integer.parseInt(r.readLine());
String[] inputs = new String[num];
for (int i = 0; i < num; i++) {
inputs[i] = r.readLine();
}
for (String input : inputs) {
System.out.println(solve(input));
}
}
}
Note: Additional test cases
11 1+1=2 :1
12 1+2=3 :1
13 1+3=4 1
14 1+5=5 1-4=-3 14: 3
21 2+1=3,21 :2
I couldn't estimate time complexity and space complexity.
This code works up to 20 digits.
# I believe 0 isn't prime number.. but the problem statements says so, I have written such code.
I would like to know the datasets also.
I did it in php because it's cheap and dirty. First calculates a possible permutation of the digits, and only at that point does it calculate the permutations of the +/-. That should save a lot of operations, since other solutions which calculate the permutations along with the +/- at the same time will be calculating the same digit permutation over and over again with different combinations of +/-.
This problem is NP and huge, yes? it seems like for each of the 2^n digit permutations there are 2^n permutations of +/- on the digits. At the risk of asking something really stupid, is that O(2^(2n)) bound?
It uses O(n) extra space though. There's commented code in there to return an answer array which would use much more, but this version just prints. I'm aware this doesn't fit the output requirements of the problem.
This algorithm works up to the max int, could be made to work for much larger numbers using GMP. But the universe might end before that completes.
<?php;
$tests = array(
'12345',
'123412341234',
'3462',
);
function isWallPrime($int) {
if (($int % 2) == 0) return 2;
if (($int % 3) == 0) return 3;
if (($int % 5) == 0) return 5;
if (($int % 7) == 0) return 7;
}
function getWallPrimes($str) {
$localAnswers = array();
$runningNumbers = array();
h_getWallPrimes(intval($str), $localAnswers, $runningNumbers);
return $localAnswers;
}
function h_getWallPrimes($int, &$localAnswers, &$runningNumbers) {
if ($int == 0 ) {
$runningAnswer = array();
h_getWallPrimes_arith(0, 0, $runningNumbers, $localAnswers, $runningAnswer);
return;
}
$int10 = 10 * $int;
$rnLen = count($runningNumbers);
for ($mod = 10 ; $mod < $int10 ; $mod *= 10) {
$runningNumbers[] = $int % $mod;
h_getWallPrimes(floor($int/$mod), $localAnswers, $runningNumbers);
$runningNumbers = array_slice($runningNumbers, 0, $rnLen);
}
}
function h_getWallPrimes_arith($runningNum, $index, &$runningNumbers, &$localAnswers, &$runningAnswer) {
if (! isset($runningNumbers[$index])) {
$ret = isWallPrime($runningNum);
if ($ret) {
//$localAnswers[] = array($runningNum, array_reverse($runningAnswer), $ret);
echo 'Wallprime ', $runningNum, "\t", 'divisible by ', $ret, "\t", 'Permutation ', json_encode(array_reverse($runningAnswer)), "\n";
}
return;
}
$newNum = $runningNumbers[$index];
$runningAnswer[] = $newNum;
h_getWallPrimes_arith($runningNum+$newNum, $index+1, $runningNumbers, $localAnswers, $runningAnswer);
array_pop($runningAnswer);
$runningAnswer[] = 0-$newNum;
h_getWallPrimes_arith($runningNum-$newNum, $index+1, $runningNumbers, $localAnswers, $runningAnswer);
array_pop($runningAnswer);
}
//=======================================
//=======================================
echo "\n\n";
foreach ($tests as $str) {
$ret = getWallPrimes($str);
echo "\n\n";
}
?>
Here's my (Java) solution. I didn't include the io part, just a method that calculates the number of walprimes for an array of digits.
public class Walprime {
public static int count(int[] ds, int acc, int i, char opi, int j) {
int a = 0;
for (int k = i; k <= j; k++) a = a * 10 + ds[k];
int accNew = opi == '+' ? acc + a : acc - a;
if (j == ds.length - 1) {
return isWalprime(accNew);
}
return count(ds, accNew, j+1, '+', j+1)
+ count(ds, accNew, j+1, '-', j+1)
+ count(ds, acc, i, opi, j+1);
}
public static int isWalprime (int n) {
return n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 ? 1 : 0;
}
public static int countWalPrime(int[] ds) {
return count(ds, 0, 0, '+', 0);
}
}
here is my java BFS solution
static int abs(int i){
return i<0?-i:i;
}
static boolean isWallprime(int n){
return (n%2==0)||(n%3==0)||(n%5==0)||(n%7==0);
}
static int bfs(String num){
int n = Integer.parseInt(num);
// state --> i : split after digit i from the left
// val : value of the exp. preceding i
// prevSplit : position of the prev split
int i = 1, val = 0;
int ways = 0;
int curVal, val2, ssVal;
int prevSplit = 0;
Queue<Integer> splitQ = new LinkedList<Integer>();
Queue<Integer> prevSplitQ = new LinkedList<Integer>();
Queue<Integer> valQ = new LinkedList<Integer>();
// if lastsplit < 0 prev op was -
// if lastsplit > 0 prev op was +
if(isWallprime(n))
ways++;
splitQ.add(i);
valQ.add(val);
prevSplitQ.add(prevSplit);
while (!splitQ.isEmpty()){
i = splitQ.poll();
val = valQ.poll();
prevSplit = prevSplitQ.poll();
// not to split
ssVal = Integer.parseInt(num.substring(abs(prevSplit),i));
curVal = (prevSplit>0)?val-ssVal:val+ssVal;
curVal = curVal*10 + Integer.parseInt(num.substring(i,i+1));
if (i<num.length()-1){
splitQ.add(i+1);
valQ.add(curVal);
prevSplitQ.add(0);
}
// operation split at i
// trying addition
val2 = Integer.parseInt(num.substring(i));
if(isWallprime(val+val2))
ways++;
//value between 2 splits
ssVal = Integer.parseInt(num.substring(abs(prevSplit),i));
curVal = (prevSplit>0)?val-ssVal:val+ssVal;
curVal+=Integer.parseInt(num.substring(i,i+1));
if (i<num.length()-1){
splitQ.add(i+1);
valQ.add(curVal);
prevSplitQ.add(i);
}
// trying subtraction
val2 = Integer.parseInt(num.substring(i));
if(isWallprime(val-val2))
ways++;
ssVal = Integer.parseInt(num.substring(abs(prevSplit),i));
curVal = (prevSplit>0)?val-ssVal:val+ssVal;
curVal-=Integer.parseInt(num.substring(i,i+1));
if (i<num.length()-1){
splitQ.add(i+1);
valQ.add(curVal);
prevSplitQ.add(i);
}
}
return ways;
}
I did it for only %5 and %7 .. but you should get the idea.
package com.intv.combinations;
public class PrintValidExpressions {
public static int expressionCount = 0;
/**
* Definition of a valid expression: any expression that evaluates to a number that is divisible by 5 or 7
*
* q. find all valid expressions given a string "s" by inserting - or + between the numbers.
*
* ex: 122 -> 1+2+2 = 5
* 12+2 = 14;
*
* @param args
*/
public static void main(String[] args) {
// Complexity:
// let k be the number of operators. O( (k+1)^(n-1)) .. so in this case for k = 2 (+,-) .. O(3 ^ n-1)
String numbers = "123";
System.out.println(validExpressions(numbers));
System.out.println(expressionCount);
}
public static int validExpressions(String numbers) {
return validExpressionHelper(numbers, "", "",0, 0);
}
public static int validExpressionHelper(String numbers, String operator, String expression, int result, int position) {
StringBuffer buffer = new StringBuffer(1024);
int count = 0;
for(int i = position ; i < numbers.length() ; i++) {
buffer.append(numbers.charAt(i));
int currentNumber = new Integer(buffer.toString()).intValue();
int currentResult = eval(currentNumber, result, operator);
if(i+1 == numbers.length()) {
boolean check = checkExpression(expression, currentNumber, currentResult);
if(check) return (count+1);
}
String plusExpr = expression + currentNumber + "+";
count += validExpressionHelper(numbers, "+" , plusExpr, currentResult, i+1);
String minExpr = expression + currentNumber + "-";
count += validExpressionHelper(numbers, "-" , minExpr, currentResult , i+1);
}
return count;
}
private static boolean checkExpression(String expression, int currentNumber, int currentResult) {
// I am the last number in the expression
String currentExpression = expression + currentNumber;
System.out.println(currentExpression + " = " + currentResult );
expressionCount++;
return (currentResult % 5 == 0 || currentResult % 7 == 0);
}
private static int eval(int currentNumber, int result, String prevOperator) {
if(prevOperator.isEmpty()) return currentNumber;
else if(prevOperator.equals("-")) {
return result - currentNumber;
} else { // assume for now it is +
return result + currentNumber;
}
}
}
We could use Inclusion–exclusion principle AND dynamic programming. The time complexity can be reduced to polynomial.
Firstly, Inclusion–exclusion principle:
Define F(s, p) to be the no. of expressions whose result are divisible by number p. For example, F("011", 2) = 6, F("011", 3) = 3.
Define F(s, {p, q}) to be the no. of expressions whose result are divisible by at least one of the digit prime in {p, q}.
Then, by Inclusion–exclusion principle, F(s, {p, q}) = F(s, p) + F(s, q) - F(s, p * q)
We have F(s, {2, 3, 5, 7}) = F(s, 2) + F(s, 3) + F(s, 5) + F(s, 7) - F(s, 2 * 3) - ... + F(s, 2 * 3 * 5) + ... - F(s, 2 * 3 * 5 * 7)
Now, we use dynamic programming to find F(s, p).
let s[i:]be the suffix string start at index i,
let n be the length of string s.
let num[i:j] be the number converted from substring s[i:j] inclusive.
Define R[i][j] be the no. of expressions which are formed from substring s[i:] and the remainder is j while mod p. (0 <= i < n, 0 <= j < p)
For example, s = "011", p = 2, R[1][0] is the no. of expressions formed from substring "11" and the remainder is 0 while they mod 2. R[1][0] = 2, since (1 + 1) % 2 = 0, (1 - 1) % 2 = 0, and R[1][1] = 1, since 11 % 2 = 1.
R[i][j] can be calculated from sub-problems R[k][l], where (num[i:k -1] + l) % p == j or (num[i: k - 1] - l) % p == j, for all k > i and k < n.
Then R[i][j] = Sum(R[k][(j - num[i:k - 1]) % p] +R[k][(num[i:k - 1] - j) % p], k = i + 1, ..., n - 1)
We get F(s, p) from R[0][0].
Here is code:
- guo deng October 31, 2013