## Google Interview Question for Software Engineer in Tests

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 6 vote

Let's first solve simplified problem: Let assume that we are only interested if there exist a solution such that 'target' integer can be expressed by combination of given integers in array 'a', operators '+ - * /' and braces '( )'. For instance, given integers 30 2 2 and a target value 16 then 16 = (2+30)/2, however there is no solution if the target value was 8.

Notice that if you remove two numbers from the array 'a' of the length N, apply an operator to these values and append the new value to the array 'a', you obtain a new array of the length N-1. Now you have to solve exactly the same problem as in the beginning, however with reduced size to N-1.

Hence the problem can be solved recursively, in each recursive call try all pairs from 'a' with all operators, while reducing the problem. Eventually the array contains a single integer, the base case. If the integer is equal to the target value we are done : the target value can be expressed as valid mathematical expression composed of given operators, braces and by given N integers. Otherwise we have to explore different branch of the tree.

There are two important remarks:
1) Let assume that non-integer division is not allowed
2) Division operator is not symmetric, hence in general x/y != y/x
This must be carefully handled in the code.

Finally, to solve the original problem we have to modify the recursive algorithm such that it will be able to keep track of the expression. This can be implemented via linked list of strings.

A sample code is shown below:

``````public static String decompose(int[] a, int target) {
for (Integer y : a) {
}

return decompose(x, expr, target);
}

if (x.size() == 1) { 			// Base case
if (x.get(0) == target) 	return (expr.get(0)+" = "+target);
else 						return null;
}

for (int i = 0; i<x.size(); i++) {
for (int j = i+1; j<x.size(); j++) {
int a = x.get(j);
int b = x.get(i);

String ae = exp.get(j);
String be = exp.get(i);

for (int k=0; k<5; k++) {
// Copy of the integer list
for (Integer y : x) { xnew.addLast(y); }
xnew.remove(j); xnew.remove(i);
// Copy of the expression string list
for (String s : expr) { exprnew.addLast(s); }
exprnew.remove(j); exprnew.remove(i);
// Handling division and zero
if ( k==3 && (b==0 || a%b != 0)) 	continue;
if ( k==4 && (a==0 || b%a != 0)) 	continue;
// Applying operator
int res = applyOperator(a, b, k);
// Merging expression strings
String e = stringOperator(ae, be, k);

String ans = decompose(xnew, exprnew, target);
if (ans != null)					return ans;
}
}
}
return null;
}

private static int applyOperator(int a, int b, int k) {
switch (k) {
case 0: 	return a+b;
case 1: 	return a-b;
case 2: 	return a*b;
case 3:     return a/b;
}
return b/a;
}

private static String stringOperator(String ae, String be, int k) {
if (ae.matches(".+[-+*/].+"))	ae = "(" + ae + ")";
if (be.matches(".+[-+*/].+"))	be = "(" + be + ")";

switch (k) {
case 0: 	return ae + "+" + be;
case 1: 	return ae + "-" + be;
case 2: 	return ae + "*" + be;
case 3: 	return ae + "/" + be;
}
return be + "/" + ae;
}``````

Notice that division is handled by two cases: 'k=3' for 'a/b' and 'k=4' for b/k. Indeed it works, example:
input: 4, [5 7 13 169]
output: (7+(169/13))/5 = 4

Comment hidden because of low score. Click to expand.
0

There's a bug when applying the division operator no? You're returning a/b, both integers. What if the solution requires a/b to be not an integer?

Comment hidden because of low score. Click to expand.
0

You code produce wrong ouptut,
Take this case
a[] {2,3,4,5} and target 18
whereas the output is
(((2*5)-4)*3)=18

but if you say that () allowed only once, then
with example: {1, 3, 4,6}, target: 12
6+(4+(3-1)) = 12
Which usese multiple ()

Comment hidden because of low score. Click to expand.
1
of 1 vote

Brute force here is fine .. we don't need to count any parenthesis and just try to invoke +,-,*,/,j.
So the complexity will be:
4! - Generating permutations of the given number
4^4 - Assigning the operators between the number and evaluating them.

which is very reasonable to run in a more than fair amount of time.

A simple recursive solution:

``````#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
if (start >= v.size()) {
return res == RES;
}

for (int k=start;k<v.size();++k) {
swap(v[start],v[k]);
if (is24(v,start+1,res + v[start])) return true; // check addition
if (is24(v,start+1,res * v[start])) return true; // check mul
if (is24(v,start+1,res - v[start])) return true; // check minus
if (is24(v,start+1,res / v[start])) return true; // check divide
swap(v[start],v[k]);
}
return false;
}

int main()
{
vector<int> v = {1,2,3,88};
if (is24(v,0,0))
cout << "True" << endl;
else
cout << "False" << endl;
}``````

Comment hidden because of low score. Click to expand.
0

It looks like your code is not working, did you test it? :)

Comment hidden because of low score. Click to expand.
0

Yes i did, the example in the main should not work.
On which input it doesn't work for you ?

Comment hidden because of low score. Click to expand.
0

Yes i did, the example in the main should not work.
On which input it doesn't work for you ?

Comment hidden because of low score. Click to expand.
0

I agree with no parens.
We don't need to worry about parens in general because the problem did not specify the order so one of permutations will eventually cover paren case.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````var decompose = function (A, B, s) {
if (!A.length) {
B.push(s);
return;
}
if (!s.length) {
s += '(' + A[0] + ')';
return decompose(A.slice(1), B, s);
}
for (var i = 0; i < A.length; i++) {
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' + ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' * ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' - ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' - ' + s + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' / ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' / ' + s + ')');
}
}

var solveFourIntegers = function (A, target) {
var B = [];
decompose(A.slice(), B, "");
return B.filter(function (exp) {
return eval(exp) === target;
});
};

console.log(solveFourIntegers([2,3,4,6], 24));

//output

[ '(((3 - (2)) * 4) * 6)',
'(6 / ((3 - (2)) / 4))',
'((4 / (3 - (2))) * 6)',
'(((3 - (2)) * 6) * 4)',
'(4 / ((3 - (2)) / 6))',
'((6 / (3 - (2))) * 4)',
'((((2) + 4) * 3) + 6)',
'((6 - ((2) - 4)) * 3)',
'(((4 - (2)) + 6) * 3)',
'(((4 / (2)) + 6) * 3)',
'((((2) * 6) - 4) * 3)',
'((4 - ((2) - 6)) * 3)',
'(((6 - (2)) + 4) * 3)',
'(((6 / (2)) + 3) * 4)' ]``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````var decompose = function (A, B, s) {
if (!A.length) {
B.push(s);
return;
}
if (!s.length) {
s += '(' + A[0] + ')';
return decompose(A.slice(1), B, s);
}
for (var i = 0; i < A.length; i++) {
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' + ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' * ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' - ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' - ' + s + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' / ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' / ' + s + ')');
}
}

var solveFourIntegers = function (A, target) {
var B = [];
decompose(A.slice(), B, "");
return B.filter(function (exp) {
return eval(exp) === target;
});
};

console.log(solveFourIntegers([2,3,4,6], 24));

//output
[ '(((3 - (2)) * 4) * 6)',
'(6 / ((3 - (2)) / 4))',
'((4 / (3 - (2))) * 6)',
'(((3 - (2)) * 6) * 4)',
'(4 / ((3 - (2)) / 6))',
'((6 / (3 - (2))) * 4)',
'((((2) + 4) * 3) + 6)',
'((6 - ((2) - 4)) * 3)',
'(((4 - (2)) + 6) * 3)',
'(((4 / (2)) + 6) * 3)',
'((((2) * 6) - 4) * 3)',
'((4 - ((2) - 6)) * 3)',
'(((6 - (2)) + 4) * 3)',
'(((6 / (2)) + 3) * 4)' ]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
output:
[2,3,5,11] = 24
(5-(3-(2*11))) = 24

[7,8,9,3] = 24
(8*3) = 24

[7,7,7,7] = 24
NO SOLUTION = 24

[1,2,3,4] = 24
(3*(2*4)) = 24

[100,50,20,5] = 24
((100+20)/5) = 24

*/
function express(tree) {
if(tree.left) {
return "("+express(tree.left)+tree.operation+express(tree.right)+")";
}
else {
return tree.value;
}
}

function solve(array, target) {

var nodes = [];
for(var i=0;i<array.length;i++) {
nodes.push(
{
value:array[i],
bits: 1<<i
}
);
}

for(var i=0;i<nodes.length;i++) {
for(var j=0;j<nodes.length;j++) {
if(i!=j) {
if(nodes[j].value==target) {
return express(nodes[j]);
}

var nodeLeft = nodes[i];
var nodeRight = nodes[j];
if((nodeLeft.bits & nodeRight.bits) == 0) {
nodes.push(
{
operation:'+',
value:nodeLeft.value+nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'-',
value:nodeLeft.value-nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'*',
value:nodeLeft.value*nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'/',
value:nodeLeft.value/nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
}
}
}
}
return "NO SOLUTION";
}

function outputSolution(array, target) {
var html = "<b>[" + array + "]</b> = <i>" + target + "</i>";
var div = document.createElement("div");

var result = solve(array, target);
div.innerHTML = html + "<br>" + result + " = " + target + "<hr>";
document.body.appendChild(div);
}

outputSolution([2, 3, 5, 11], 24);
outputSolution([7, 8, 9, 3], 24);
outputSolution([7, 7, 7, 7], 24);
outputSolution([1, 2, 3, 4], 24);
outputSolution([100, 50, 20, 5], 24);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript code on jsfiddle/jacklehamster/z3gyv29a/

``````/* output:
[2,3,5,11] = 24
(5-(3-(2*11))) = 24

[7,8,9,3] = 24
(8*3) = 24

[7,7,7,7] = 24
NO SOLUTION = 24

[1,2,3,4] = 24
(3*(2*4)) = 24

[100,50,20,5] = 24
((100+20)/5) = 24
*/

function express(tree) {
if(tree.left) {
return "("+express(tree.left)+tree.operation+express(tree.right)+")";
}
else {
return tree.value;
}
}

function solve(array, target) {

var nodes = [];
for(var i=0;i<array.length;i++) {
nodes.push(
{
value:array[i],
bits: 1<<i
}
);
}

for(var i=0;i<nodes.length;i++) {
for(var j=0;j<nodes.length;j++) {
if(i!=j) {
if(nodes[j].value==target) {
return express(nodes[j]);
}

var nodeLeft = nodes[i];
var nodeRight = nodes[j];
if((nodeLeft.bits & nodeRight.bits) == 0) {
nodes.push(
{
operation:'+',
value:nodeLeft.value+nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'-',
value:nodeLeft.value-nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'*',
value:nodeLeft.value*nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'/',
value:nodeLeft.value/nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
}
}
}
}
return "NO SOLUTION";
}

function outputSolution(array, target) {
var html = "<b>[" + array + "]</b> = <i>" + target + "</i>";
var div = document.createElement("div");

var result = solve(array, target);
div.innerHTML = html + "<br>" + result + " = " + target + "<hr>";
document.body.appendChild(div);
}

outputSolution([2, 3, 5, 11], 24);
outputSolution([7, 8, 9, 3], 24);
outputSolution([7, 7, 7, 7], 24);
outputSolution([1, 2, 3, 4], 24);
outputSolution([100, 50, 20, 5], 24);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

(((160%4 )-20)*3)+(-36) = 24

PS: Question says use Integers so (-34) is a negative integer not an operand minus that is used twice.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool find_exp_aux(std::vector<int> & v, std::vector<std::string>& e, const int t, std::string& r)
{
if (v.empty()) return false;
auto n = v.size();
if (1 == n)
{
if (t == v[0])
{
r = e[0];
return true;
}
return false;
}
for (auto i = 0; i < n; ++i)
{
auto v1 = v[i];
const auto& e1 = e[i];
for (auto j = i + 1; j < n; ++j)
{
auto v2 = v[j];
const auto& e2 = e[j];
auto vc(v);
auto ec(e);
vc.erase(vc.begin() + j);
vc.erase(vc.begin() + i);
ec.erase(ec.begin() + j);
ec.erase(ec.begin() + i);
auto vnew = 0;
std::string enew = "";
vnew = v1 + v2;
enew = "(" + e1 + ")" + "+" + "(" + e2 + ")";
vc.push_back(vnew);
ec.push_back(enew);
if (find_exp_aux(vc, ec, t, r)) return true;
ec.pop_back();
vc.pop_back();
vnew = v1 * v2;
enew = "(" + e1 + ")" + "*" + "(" + e2 + ")";
vc.push_back(vnew);
ec.push_back(enew);
if (find_exp_aux(vc, ec, t, r)) return true;
ec.pop_back();
vc.pop_back();
vnew = v1 - v2;
enew = "(" + e1 + ")" + "-" + "(" + e2 + ")";
vc.push_back(vnew);
ec.push_back(enew);
if (find_exp_aux(vc, ec, t, r)) return true;
ec.pop_back();
vc.pop_back();
vnew = v2 - v1;
enew = "(" + e2 + ")" + "-" + "(" + e1 + ")";
vc.push_back(vnew);
ec.push_back(enew);
if (find_exp_aux(vc, ec, t, r)) return true;
ec.pop_back();
vc.pop_back();
if (0 != v2)
{
vnew = v1 / v2;
enew = "(" + e1 + ")" + "/" + "(" + e2 + ")";
vc.push_back(vnew);
ec.push_back(enew);
if (find_exp_aux(vc, ec, t, r)) return true;
ec.pop_back();
vc.pop_back();
}
if (0 != v1)
{
vnew = v2 / v1;
enew = "(" + e2 + ")" + "/" + "(" + e1 + ")";
vc.push_back(vnew);
ec.push_back(enew);
if (find_exp_aux(vc, ec, t, r)) return true;
ec.pop_back();
vc.pop_back();
}
}
}
return false;
}

bool find_exp(const std::vector<int>& v, const int t, std::string& r)
{
std::vector<int> vc(v);
std::vector<std::string> ec;
for (auto i : vc)
{
ec.push_back(std::to_string(i));
}
return find_exp_aux(vc, ec, t, r);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a somewhat different solution, brute force using polish expression for evaluation
and infix to print out the solution (superfluous parentheses are skipped):

``````import java.util.*;

class CareerCup_5735906000502784{
public static void main(String[]arg){
System.out.println(gen(new int[]{5, 7, 13, 169}, 4));
}

private static char[] OPERATORS = "+-*/".toCharArray();

public static String gen(int[] numbers, int target){
String[] expr = new String[2*numbers.length-1];
for(int j = 0; j < numbers.length; ++j){
expr[j] = ""+numbers[j];
}

int[] selectedOperatorIds = new int[numbers.length-1];
selectedOperatorIds[0] = -1;
int allOperatorComboCount = exp(OPERATORS.length,selectedOperatorIds.length);
for(int i = 0; i < allOperatorComboCount; ++i){
genNextOperatorCombos(expr, numbers.length, selectedOperatorIds);
String ret = find(expr, target, 0, expr.length);
if (ret != null) return ret;
}

return null;
}

private static String find(String[] expr, int target, int lo, int hi){
if (lo == hi){
String ret = eval(expr, target);
return ret;
}
for(int i = lo; i < hi; ++i){
swap(expr, lo, i);
String ret = find(expr, target, lo+1, hi);
if (ret != null) return ret;
swap(expr, lo, i);
}
return null;
}

private static String eval(String[] expr, int target){
Deque<String> stack = new ArrayDeque<>();
for(int i = expr.length-1; i >= 0; --i){
String op = expr[i];
if (isOperand(op)){
stack.push(op);
} else {
String operator = op;
if (stack.isEmpty()) return null;
String a = stack.pop();
if (stack.isEmpty()) return null;
String b = stack.pop();
Integer val = eval(Integer.parseInt(a), operator.charAt(0), Integer.parseInt(b));
if (val == null) return null;
stack.push(val.toString());
}
}
if (stack.isEmpty()) return null;
if (target == Integer.parseInt(stack.pop())){
return polishToInfix(expr);
}
return null;
}

private static String polishToInfix(String[] expr){
Deque<String> stack = new ArrayDeque<>();
for(int i = expr.length-1; i >= 0; --i){
String op = expr[i];
if (isOperand(op)){
stack.push(op);
} else {
stack.push(
String.format("%s%s%s%s%s",
parenthesesIfNeeded(op, "("),
stack.pop(), op, stack.pop(),
parenthesesIfNeeded(op, ")")));
}
}
return stack.pop();
}

private static String parenthesesIfNeeded(String operator, String p){
if (operator.equals("+") || operator.equals("-")) return p;
return "";
}

private static Integer eval(int a, char op, int b){
switch (op){
case '+': return a+b;
case '*': return a*b;
case '-': return a-b;
case '/':
if (b == 0) return null;
else return a/b;
default: throw new IllegalArgumentException(""+op);
}
}

private static boolean isOperand(String s){
return s.charAt(s.length()-1) >= '0' && s.charAt(s.length()-1) <= '9';
}

private static void swap(String[] ss, int from, int to){
String tmp = ss[from];
ss[from] = ss[to];
ss[to] = tmp;
}

private static void genNextOperatorCombos(String[] expr, int shift, int[] selectedOperatorIds){
stepCursor(selectedOperatorIds, OPERATORS.length);
for(int j = 0; j < selectedOperatorIds.length; ++j){
expr[shift+j] = ""+ OPERATORS[selectedOperatorIds[j]];
}
}

private static void stepCursor(int[] cursor, int limit){
for(int i = 0; i < cursor.length; ++i){
int prev = cursor[i];
cursor[i] = (cursor[i]+1)%limit;
if (prev < cursor[i]) break;
}
}

public static int exp(int base, int exp){
int ret = 1;
while(exp > 0){
if ((exp & 1) > 0) ret *= base;
base *= base;
exp >>= 1;
}
return ret;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution below also handles non integer division. Brackets aren't normalized, but returned expression is nevertheless valid. I think the code is self explanatory:

``````static string GetExp(int[] nums)
{
bool[] used = new bool[nums.Length];
return GetExp(nums, used, nums.Length, 24);
}

static string GetExp(int [] nums, bool [] used, int numsLeft, double sum)
{
for (int i = 0; i < nums.Length; i++)
{
if (used[i])
continue;

int x = nums[i];

if (numsLeft == 1)
{
return x == sum ? x.ToString() : null;
}

used[i] = true;

string res = GetExp(nums, used, numsLeft, sum, x);
if (res != null)
{
return res;
}

used[i] = false;
}

return null;
}

static string GetExp(int[] nums, bool[] used, int numsLeft, double sum, int x)
{
string res;

// x + <next>
res = GetExp(nums, used, numsLeft - 1, sum - x);
if (res != null)
{
return "(" + x.ToString() + "+" + res + ")";
}

// x - <next>
if (x >= sum)
{
res = GetExp(nums, used, numsLeft - 1, x - sum);
if (res != null)
{
return "(" + x.ToString() + "-" + res + ")";
}
}

// <next> - x
res = GetExp(nums, used, numsLeft - 1, sum + x);
if (res != null)
{
return "(" + res + "-" + x.ToString() + ")";
}

// x * <next>
res = GetExp(nums, used, numsLeft - 1, sum / x);
if (res != null)
{
return x.ToString() + "*" + res;
}

// x / <next>
res = GetExp(nums, used, numsLeft - 1, x / sum);
if (res != null)
{
return x.ToString() + "/" + res;
}

// <next> / x
if (x != 0)
{
res = GetExp(nums, used, numsLeft - 1, x * sum);
if (res != null)
{
return res + "/" + x.ToString();
}
}

return null;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I'm kinda confused by this question personally, for example can we only use the numbers given or can we use any number as well as the given numbers?

If we can use any numbers we want then I think something along the lines of:

``````public int return24(int one, int two, int three, int four) {
return ((one + two + three + four) * 0) + 24;
}``````

Would solve this problem. I could be missing something though?

Comment hidden because of low score. Click to expand.
0

I think according to problem description usage of numbers like 0 or 24 from your example is not allowed.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

2*6+3*4

Comment hidden because of low score. Click to expand.
-1
of 1 vote

2*6+3*4

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Brute force here is fine .. we don't need to count any parenthesis and just try to invoke +,-,*,/,j.
So the complexity will be:
4! - Generating permutations of the given number
4^4 - Assigning the operators between the number and evaluating them.

which is very reasonable to run in a more than fair amount of time.

A simple recursive solution:

``````#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
if (start >= v.size()) {
return res == RES;
}

for (int k=start;k<v.size();++k) {
swap(v[start],v[k]);
if (is24(v,start+1,res + v[start])) return true; // check addition
if (is24(v,start+1,res * v[start])) return true; // check mul
if (is24(v,start+1,res - v[start])) return true; // check minus
if (is24(v,start+1,res / v[start])) return true; // check divide
swap(v[start],v[k]);
}
return false;
}

int main()
{
vector<int> v = {1,2,3,88};
if (is24(v,0,0))
cout << "True" << endl;
else
cout << "False" << endl;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just use brute force. (4! * 4^4)

``````#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
if (start >= v.size()) {
return res == RES;
}

for (int k=start;k<v.size();++k) {
swap(v[start],v[k]);
if (is24(v,start+1,res + v[start])) return true; // check addition
if (is24(v,start+1,res * v[start])) return true; // check mul
if (is24(v,start+1,res - v[start])) return true; // check minus
if (is24(v,start+1,res / v[start])) return true; // check divide
swap(v[start],v[k]);
}
return false;
}

/*
bool is24i(const vector<v>& v)
{
// generate all permutations - can be done by preprocessing.

// check assignments
}
*/

int main()
{
vector<int> v = {1,2,3,88};
if (is24(v,0,0))
cout << "True" << endl;
else
cout << "False" << endl;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just use brute force. (4! * 4^4)

``````#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
if (start >= v.size()) {
return res == RES;
}

for (int k=start;k<v.size();++k) {
swap(v[start],v[k]);
if (is24(v,start+1,res + v[start])) return true; // check addition
if (is24(v,start+1,res * v[start])) return true; // check mul
if (is24(v,start+1,res - v[start])) return true; // check minus
if (is24(v,start+1,res / v[start])) return true; // check divide
swap(v[start],v[k]);
}
return false;
}

/*
bool is24i(const vector<v>& v)
{
// generate all permutations - can be done by preprocessing.

// check assignments
}
*/

int main()
{
vector<int> v = {1,2,3,88};
if (is24(v,0,0))
cout << "True" << endl;
else
cout << "False" << endl;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

(2*6) + (4*3)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.