Fixing a “Damaged App” from App Store

Background:

  • OSX (From Apple, or Hackintosh)
  • The App was purchased from the App Store with the current iCloud ID

The problem:

  • Unable to open a previously purchased App

The error:

“Magnet” is damaged and can’t be opened. Delete “Magnet” and download it again from the App Store.

It could be any paid app, in my case, ‘Magnet’.

There exist a similar but common error caused by unsigned/modified third party apps (blocked by Gatekeeper)

App Is Damaged and Can’t Be Opened. You Should Move It To The Trash

This is NOT what my guide is talking about.

The Cause

The error basically means Apple is unable to verify the App purchased on this machine.

The MAC address of your en0 is part of the verification. Because all Macs come with a built-in Wifi/Ethernet Adapter.

Run this in your terminal to list all network interfaces.

networksetup -listallhardwareports

What exactly happened to my is, my hackintosh motherboard comes with two built-in Ethernet adapters. I disabled one (en0) from the BIOS few days after the OSX is installed.

How to fix

If you encountered the same error message, try the following:

(Software issue, basically sync your current en0 MAC address with iCloud)

  • Follow this guide from 1Password (also work for other apps from the App Store)
  • If that isn’t help, continue:

(Hardware issue. in most cases, en0 not found)

  • list all network interfaces, find en0
  • If en0 is not found, enable it from BIOS (if you disabled it before)
  • If you didn’t remove/disable any network hardware, rename your primary interface to en0, here are some useful resources
  • After that, follow the guide from 1Password again when necessary (when it’s still not working)

1089. Duplicate Zeros

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]

Note:

1 <= arr.length <= 10000
0 <= arr[i] <= 9

Solution:

class Solution {
    public void duplicateZeros(int[] arr) {
        int count  = 0;
        for (int i = 0; i < arr.length; i ++){
            if (arr[i] == 0){
                count ++;
            }
        }
        
        int offset = count;
        for (int i = arr.length - 1; i >= 0; i --){
            if (i + offset < arr.length){
                arr[i+offset] = arr[i];
            }
            if (arr[i] == 0){
                offset --;
                if (i + offset < arr.length){
                    arr[i+offset] = arr[i];
                }
            }
        }
    }
}

 

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

Constraints:

-10^9 <= nums1[i], nums2[i] <= 10^9 nums1.length == m + n nums2.length == n Solution.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // index for m
        int im = m -1;
        // index for n
        int in = n -1;
        // index for result
        int ir = m + n -1;
        
        for (;ir >= 0; ir --){
            
            if (im < 0){
                // If one of the array is all cleared, use the other
                nums1[ir] = nums2[in--];
            } else if (in < 0){
                nums1[ir] = nums1[im--];
            } else if (nums1[im] > nums2[in]){
                // Otherwise, pick the greater one.
                nums1[ir] = nums1[im--];
            } else {
                nums1[ir] = nums2[in--];
            }
        }
        
    }
}

640. Solve the Equation

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"


class Solution {
    public String solveEquation(String equation) {
        String[] explodes = equation.split("=");
        
        int coeffX = 0;
        int number = 0;
        int cur  = 0;
        int digit = 0;
        
        boolean left = false;
        
        for (String s : explodes){
            left = !left;
            boolean positive = true;
            
            for (int i = 0; i < s.length(); i ++){
                char c = s.charAt(i);
                
                if (c == '+' || c == '-'){
                    // Push previous integer to number
                    number -= cur*(positive? 1 : -1)*(left? 1 : -1);
                    cur = 0; digit = 0;
                    positive = c == '+';
                    
                } else if(c =='x') {
                    // Push previous coeff of x to coeffX
                    if (digit == 0){
                        // If no coeff, coeff = 1
                        cur = 1;
                    }
                    coeffX += cur*(positive? 1 : -1)*(left? 1 : -1);
                    cur = 0; digit = 0;
                } else {
                    // It's a number.
                    cur = 10 * cur +  Integer.valueOf(s.charAt(i)-'0');
                    digit ++;
                }
            }
            
            // If last in group is a number, redundant
            if (digit > 0){
                number += cur*( ! positive? 1 : -1)*(left? 1 : -1);
                cur = 0; digit = 0;
            }
        }
        
        if (coeffX == 0 && number == 0){
            return "Infinite solutions";
        } else if (coeffX == 0){
            return "No solution";
        }
        return "x="+String.valueOf(number/coeffX);
    }
}

 

1170. Compare Strings by Frequency of the Smallest Character

Let’s define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

 

Example 1:

Input:

 queries = ["cbd"], words = ["zaaaz"]

Output:

 [1]

Explanation:

 On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Example 2:

Input:

 queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]

Output:

 [1,2]

Explanation:

 On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

 

Constraints:

  • 1 <= queries.length <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].length, words[i].length <= 10
  • queries[i][j]words[i][j] are English lowercase letters.

 

Straight forward solution O(q * w)

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] result = new int[queries.length];
        for (int i = 0 ; i < queries.length; i ++){
            int score = s(queries[i]);
            
            for (String w : words){
                if (s(w) > score){
                    result[i] ++;
                }
            }
        }
        return result;
    }
    
    public static int s(String s) {
        char min = 'z';
        char[] ca = s.toCharArray();
        for(char c : ca){
            if (c < min){
                min = c;
            }
            if (c == 'a'){
                break;
            }
        }
        int r = 0;
        for(char c : ca){
            if (c == min)
                r ++;
        }
        return r;
    }
}

Optimized solution O (q + w)

since we have 1 <= queries[i].length, words[i].length <= 10

which means query will have only 10 possible values (limited), so for the result.

so we can use counting.

 

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        
		int[] freqCounter = new int[11];
		int[] result = new int[queries.length];
		for (int i = 0; i < words.length; i++) {
			int freq = s(words[i]);
			freqCounter[freq]++;
		}

		for (int i = 1; i < freqCounter.length; i++) {
			freqCounter[i] += freqCounter[i - 1];
		}
		for (int i = 0; i < queries.length; i++) {
			int freq = s(queries[i]);
			result[i] = words.length - freqCounter[freq];
		}
        
        return result;
    }
    
    public static int s(String s) {
        char min = 'z';
        int r = 0;
        char[] ca = s.toCharArray();
        for(char c : ca){
            if (c < min){
                r = 1;
                min = c;
            } else if(c == min) {
                r ++;
            }

        }
        return r;
    }
    
}

 

1278. Palindrome Partitioning III

You are given a string s containing lowercase letters and an integer k. You need to :

  • First, change some characters of s to other lowercase English letters.
  • Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

 

Example 1:

Input:

 s = "abc", k = 2

Output:

 1

Explanation:

 You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input:

 s = "aabbc", k = 3

Output:

 0

Explanation:

 You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input:

 s = "leetcode", k = 8

Output:

 0

 

Constraints:

  • 1 <= k <= s.length <= 100.
  • s only contains lowercase English letters.

Failed to build the dp during the contest : ( .   it was quite close

class Solution {
    public int palindromePartition(String s, int k) {
        if (k == s.length()){
            return 0;
        }
        
        int[][] dp = new int[s.length()+1][k+1];
        
        
        for (int i = 0; i <= s.length(); i++)
            for (int j = 0; j <= k; j++)
                dp[i][j] = s.length();
        
        dp[0][0] = 0;
        for (int i = 0; i < s.length(); i ++){
          
            for (int j = 0; j < k; j ++){
                
                for (int len = 1; i + len <= s.length(); len++) {
                    int cost = 0;

                    for (int a = i, b = i + len - 1; a < b; a++, b--){
                        if (s.charAt(a) != s.charAt(b)){
                            cost ++;
                        }
                    }
    

                    dp[i + len][j + 1] = Math.min(dp[i + len][j + 1], dp[i][j] + cost);
                }
            }
        }
        
        return dp[s.length()][k];
    }
    

}

Few things to point out:

  • I initialize each value of dp with s.length(), since it can’t be worse than replacing every chars. Integer.MAX_VALUE will cause an integer overflow while building the dp

1277. Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

 

Example 1:

Input:

 matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]

Output:

 15

Explanation:

 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is one square of side 3.
Total number of squares = 10 + 4 + 1 = 15

Example 2:

Input:

 matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

Output:

 7

Explanation:

 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7

 

Constraints:

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

 

Example:

[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

  1. count single ones
  2. count 2×2
  3. count 3×3
  4. ……

Goal: reduce n x n to (n-1)x(n-1) … to 2×2

Now scan 2×2 block, for each position(i,j) scan (i+1,j) (i,j+1) (i+1, j+1)
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

if the 2×2 scanning block contains 0, update (i,j) to 0
[0,1,1,1],
[0,1,1,1],
[0,1,1,1]

then we can reduce it by removing (ignoring) the last row and column.

[0,1,1],
[0,1,1]

Then walk through with the 2×2 scanning block again.

the counter could be updated when the whole 2×2 block is 1, OR count number of ones in the next round.

Version A, update counter during 2×2 scan

class Solution {
    public int countSquares(int[][] matrix) {
        int c = 0;
        
        int m  = matrix.length;
        int n  = matrix[0].length;
        
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j ++){
                if (matrix[i][j] == 1){
                    c++;
                } 
            }
        }
        
        
        while (m > 1 && n > 1){
            for (int i = 0; i < m-1; i ++){
                for (int j = 0; j < n-1; j ++){
                    if (  matrix[i][j]     == 0 
                       || matrix[i+1][j]   == 0
                       || matrix[i][j+1]   == 0
                       || matrix[i+1][j+1] == 0)
                    {
                        matrix[i][j] = 0;
                    }  else {
                        c++;
                    }
                }
            }
            // lower m and n (ignoring last row and column)
            m --;
            n --;
        }
        return c;
        
    }
}

 

B, a more compact version, update counter next round, count number of ones.
slightly slower for more loops

 

class Solution {
    public int countSquares(int[][] matrix) {
        int c = 0;
        
        int m  = matrix.length;
        int n  = matrix[0].length;
        
        
        
        while (m > 0 && n > 0){
            
            for (int i = 0; i < m; i ++){
                for (int j = 0; j < n; j ++){
                    if (matrix[i][j] == 1){
                        c++;
                    } 
                }
            }
            
            
            for (int i = 0; i < m-1; i ++){
                for (int j = 0; j < n-1; j ++){
                    if (matrix[i][j] == 0 
                       || matrix[i+1][j] == 0
                       || matrix[i][j+1] == 0
                       || matrix[i+1][j+1] == 0){
                        matrix[i][j] = 0;
                    }
                }
            }
            // lower m and n (ignoring last row and column)
            m --;
            n --;
        }
        return c;
        
    }
}

A: 86-110 ms
B: 160-170 ms

1276. Number of Burgers with No Waste of Ingredients

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

  • Jumbo Burger: 4 tomato slices and 1 cheese slice.
  • Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

 

Example 1:

Input:

 tomatoSlices = 16, cheeseSlices = 7

Output:

 [1,6]

Explantion:

 To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input:

 tomatoSlices = 17, cheeseSlices = 4

Output:

 []

Explantion:

 There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input:

 tomatoSlices = 4, cheeseSlices = 17

Output:

 []

Explantion:

 Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input:

 tomatoSlices = 0, cheeseSlices = 0

Output:

 [0,0]

Example 5:

Input:

 tomatoSlices = 2, cheeseSlices = 1

Output:

 [0,1]

 

Constraints:

  • 0 <= tomatoSlices <= 10^7
  • 0 <= cheeseSlices <= 10^7

 

Should be an easy question..

class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        
        List<Integer> result = new ArrayList<>();
        
        if (tomatoSlices % 2 ==1 || cheeseSlices * 4 < tomatoSlices || cheeseSlices * 2 > tomatoSlices){
            return result;
        }
        
        int x = (tomatoSlices - cheeseSlices*2)/2;
        result.add(x);
        result.add(cheeseSlices-x);
        
        return result;
    }
}