Java BitMask+DFS and Funny Hacky solutions


  • 0
    Z

    Hi there! Today I want to share two different solutions. They are:

    • Bit Mask + DFS solution that is Faster than simple DFS solution
    • Randomized funny solution that I submitted in the contest

    In order to form a square, sum of all sticks must be evenly divisible by 4, otherwise we can immediately return false. After that we can find what should be the side of the square be equals to. That is sum/4. According to the problem statement, maximum size of the input array do not exceed 15. It allows us to know all tuples of numbers that can form a side of the square, by applying bit masks. Next step is to determine if we can 4 tuples that do not intersect with each other. We can realize that by launching dfs of depth 4. At this point bit operations again help us to simplify the process. We store a buffer, which is bitwise or of tuples along the dfs path. To check whether a tuple has intersection with previous tuples, it is sufficient to check whether the buffer and the tuple and(&) up to 0.

    public class Solution {
        public boolean makesquare(int[] nums) {
            if(nums == null || nums.length<4) return false;
            int sum = 0 ;
            for(int num:nums) sum+=num;
            if(sum%4 != 0) return false;
            int side =  sum/4;
            int n  =nums.length;
            int max= (1<<n);
            List<Integer> g  = findSideMatches(max,side,nums);
            boolean res = false;
            for(int i = 0;i<g.size();i++){
                res = res || dfs(max-1,g.get(i),1, g, i);
            }
            return res;
        }
        
        public List<Integer> findSideMatches(int max, int side, int nums[]){
            List<Integer> g  = new ArrayList<>();
            for(int i = 1;i<max;i++){
                int sum = 0;
                for(int j = 0, bit = 1;j<nums.length;j++, bit<<=1){
                    if((bit&i) == bit){
                        sum+=nums[j];
                    }
                }
                if(sum == side){
                    g.add(i);
                }
            }
            return g;
        }
        
        public boolean dfs(int max, int buff, int count , List<Integer> g, int v){
            if(count == 4 ) {
                return buff == max;
            }
            boolean res = false;
            for(int i = v+1;i<g.size();i++){
                if((buff & g.get(i)) == 0){
                    res = res || dfs(max,(buff|g.get(i)),count+1, g, i);
                }
            }
            return res;
        }
    }
    

    Solution above could be accelerated by memoization technique (DP), but it gives few advantage on speed vs huge memory occupation.

    Well, the second solution is based on dp and randomization. We could solve this problem by using 2D DP[n][4] where n is the length of input array. A (i, j) state of the DP, stores information about the length of side we can build, j equal sides by i sticks. Transition function is simple. I think all the details are understandable from canBuild() method in the code below. So far so good, but this dp solution depends on the order of sticks. It means, if square can be formed from the input array, that dp solution will return true for some permutation of it. Therefore to solve the problem it is necessary to brute force all the permutations, which is O(n!*n^2) time. It is too long... But, we can guess the solution by randomly shuffling the array and running dp. Fortunately I have got accepted by 5000 random iterations (700ms) at the contest. But this solution does not guarantee success, and probability of hitting correct answer rises by number of iterations. However I find it funny:=)

    public class Solution {
       public boolean makesquare(int[] nums) {
           if(nums == null || nums.length<4) return false;
           //Arrays.sort(nums);
            int dp[][] = new int[nums.length][5];
          
           List<Integer> shuffle = new ArrayList<>();
           for(int num:nums) shuffle.add(num);
           
           for(int i = 0;i<5000;i++){
               if(canBuild(shuffle, dp)){
                   return true;
               }
               Collections.shuffle(shuffle);
           }
           
           return false;
       }
       
       public boolean canBuild(List<Integer> nums, int dp[][]){
           for(int i = 0;i<nums.size();i++) Arrays.fill(dp[i], 0);
           dp[0][1] = nums.get(0);
           for(int i = 1;i<nums.size();i++){
               dp[i][1] = dp[i-1][1]+nums.get(i);
           }
             
           for(int i = 2;i<5;i++){
               for(int j = 1;j<nums.size();j++){
                   int len = nums.get(j);
                   for(int k = j-1;k>=0;k--){
                       if(dp[k][i-1] == len){
                           dp[j][i] = len;
                           break;
                       }
                       len+=nums.get(k);
                   }
               }
           }
           return dp[nums.size()-1][4] != 0;
       }  
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.