Formatted question description: https://leetcode.ca/all/679.html

679. 24 Game

Level

Hard

Description

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]

Output: True

Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]

Output: False

Note:

  1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
  2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
  3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Solution

Simply consider all possible postfix expressions using the given 4 numbers and the 4 operators. In postfix expressions, brankets do not exist.

Obtain all possible permutations of the given 4 numbers. Since there are 3 operators used when there are 4 numbers, obtain all possible permutations that contains 3 operators.

Given 4 numbers and 3 operators, there are 4 possible postfix expressions, which are listed as follows, where n represents a number and o represents an operator.

n n n n o o o
n n n o n o o
n n o n o n o
n n o n n o o

For each permutation of numbers, each permutation of operators and each possible postfix expression, calculate the value. If there exists a postfix expression that has value 24, return true. Otherwise, return false.

Since the division operator represents real division, maintain a rational number for the result of calculation, which contains a numerator and a denominator.

class Solution {
    public boolean judgePoint24(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> permutations = permuteUnique(nums);
        char[] operators = {'+', '-', '*', '/'};
        for (List<Integer> permutation : permutations) {
            for (int i = 0; i < 64; i++) {
                int[] base4 = toBase4(i);
                char[] curOperators = new char[3];
                for (int j = 0; j < 3; j++)
                    curOperators[j] = operators[base4[j]];
                char[][] postfixes = new char[4][7];
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 4; k++)
                        postfixes[j][k] = (char) (permutation.get(k) + '0');
                    for (int k = 4; k < 7; k++)
                        postfixes[j][k] = curOperators[k - 4];
                }
                char temp2 = postfixes[1][3];
                postfixes[1][3] = postfixes[1][4];
                postfixes[1][4] = temp2;
                char temp3 = postfixes[2][5];
                postfixes[2][5] = postfixes[2][3];
                postfixes[2][3] = postfixes[2][2];
                postfixes[2][2] = postfixes[2][4];
                postfixes[2][4] = temp3;
                char temp4 = postfixes[3][4];
                postfixes[3][4] = postfixes[3][3];
                postfixes[3][3] = postfixes[3][2];
                postfixes[3][2] = temp4;
                for (int j = 0; j < 4; j++) {
                    if (equals24(postfixes[j]))
                        return true;
                }
            }
        }
        return false;
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        int length = nums.length;
        List<List<Integer>> permutations = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < length; i++)
            list.add(nums[i]);
        permutations.add(list);
        int[] array = new int[length];
        for (int i = 0; i < length; i++)
            array[i] = nums[i];
        nextPermutation(array);
        while (!Arrays.equals(nums, array)) {
            List<Integer> permutation = new ArrayList<Integer>();
            for (int i = 0; i < length; i++)
                permutation.add(array[i]);
            permutations.add(permutation);
            nextPermutation(array);
        }
        return permutations;
    }

    public void nextPermutation(int[] array) {
        int length = array.length;
        int index = -1;
        int curNum = -1;
        for (int i = length - 1; i > 0; i--) {
            int difference = array[i] - array[i - 1];
            if (difference > 0) {
                index = i - 1;
                curNum = array[i - 1];
                break;
            }
        }
        if (index < 0) {
            Arrays.sort(array);
            return;
        }
        int nextIndex = -1;
        int nextNum = Integer.MAX_VALUE;
        for (int i = index + 1; i < length; i++) {
            if (array[i] > curNum && array[i] < nextNum) {
                nextIndex = i;
                nextNum = array[i];
            }
        }
        array[index] = nextNum;
        array[nextIndex] = curNum;
        Arrays.sort(array, index + 1, length);
    }

    public int[] toBase4(int num) {
        int[] base4 = new int[3];
        for (int i = 2; i >= 0; i--) {
            int remainder = num % 4;
            base4[i] = remainder;
            num /= 4;
        }
        return base4;
    }

    public boolean equals24(char[] postfix) {
        int length = postfix.length;
        Stack<int[]> stack = new Stack<int[]>();
        for (int i = 0; i < length; i++) {
            char c = postfix[i];
            if (Character.isDigit(c)) {
                int num = c - '0';
                stack.push(new int[]{num, 1});
            } else {
                int[] num2 = stack.pop();
                int[] num1 = stack.pop();
                int[] newNum = new int[2];
                switch (c) {
                    case '+':
                        newNum[0] = num1[0] * num2[1] + num2[0] * num1[1];
                        newNum[1] = num1[1] * num2[1];
                        break;
                    case '-':
                        newNum[0] = num1[0] * num2[1] - num2[0] * num1[1];
                        newNum[1] = num1[1] * num2[1];
                        break;
                    case '*':
                        newNum[0] = num1[0] * num2[0];
                        newNum[1] = num1[1] * num2[1];
                        break;
                    case '/':
                        newNum[0] = num1[0] * num2[1];
                        newNum[1] = num1[1] * num2[0];
                        break;
                    default:
                }
                int gcd = gcd(newNum[0], newNum[1]);
                newNum[0] /= gcd;
                newNum[1] /= gcd;
                if (newNum[1] < 0) {
                    newNum[0] = -newNum[0];
                    newNum[1] = -newNum[1];
                }
                stack.push(newNum);
            }
        }
        int[] result = stack.pop();
        return result[0] == 24 && result[1] == 1;
    }

    public int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        if (a == 0 && b == 0)
            return 1;
        while (a != 0 && b != 0) {
            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }
            b %= a;
        }
        return a == 0 ? b : a;
    }
}

All Problems

All Solutions