class Solution {
    public int subtractProductAndSum(int n) {
    
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(n != 0){
        list.add(n%10);
        n = n/10;
    }
    int product = 1;
    int sum = 0;
    for(int i = 0; i < list.size(); i++){
        product *= list.get(i);
        sum+= list.get(i);
    }
    return product - sum;
}
}

class Solution {
    public boolean isMonotonic(int[] nums) {
        boolean increasing = true;
        boolean decreasing = true;

        for(int i = 1; i < nums.length; i++){
            if(nums[i]< nums[i-1]) {
                increasing = false;
                break;
            }
        }

        for( int i = 1; i < nums.length; i++){
            if(nums[i]> nums[i-1]){
                decreasing = false;
                break;
            }
        }


        return increasing|decreasing;
    }
}

class Solution {
    public String reverseOnlyLetters(String s) {
        char[] arr = s.toCharArray();
            int arrIndex = getNextEmpty(arr.length,arr);

        for(int i = 0 ; i < s.length(); i++){
                char c = s.charAt(i);
                if((c>='a' && c <='z') ||
                    (c>='A' && c <='Z')){
                    arr[arrIndex] = c;
                    arrIndex = getNextEmpty(arrIndex,arr);
                    }
        }
        return new String(arr);
    }
    public int getNextEmpty(int current, char[] arr){
        for(int i = current-1; i >=0; i--){
            char c = arr[i];
            if((c >='a' && c <='z') ||
                    (c>='A' && c <='Z')) return i;
        }
        return 0;
    }
}

class ParkingSystem {
 static int big = 0;
 static int medium = 0;
 static int small = 0;
    public ParkingSystem(int big1, int medium1, int small1) {
        big = big1;
        medium = medium1;
        small = small1;
    }
    
    public boolean addCar(int carType) {
        if(carType == 1){
            if(big >= 1){
                big--;
                return true;
            }else return false;
        }else if(carType == 2){
            if(medium >= 1){
                medium--;
                return true;
            } else return false;
        }else if (carType == 3){
            if(small >= 1){
                small--;
                return true;
            }else return false;
        }
        return false;
    }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * ParkingSystem obj = new ParkingSystem(big, medium, small);
 * boolean param_1 = obj.addCar(carType);
 */

class Solution {
    public int mostWordsFound(String[] sentences) {
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < sentences.length; i++){
            max = Math.max(max, sentences[i].split(" ").length);
        }
        return max;
    }
}

class Solution {
    public int kthFactor(int n, int k) {
            for(int i = 1 ; i <= n; i++){
                
                if((n%i) ==0 ){
                if( k == 1) return i;
                    k--;
                } 
                
            }

     return -1;   
    }
}

class Solution {
    public double average(int[] salary) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        double sum = 0;
        for(int i = 0; i < salary.length; i++){
                sum+=salary[i];
                min = Integer.min(min,salary[i]);
                max = Integer.max(max, salary[i]);
        }
        return (sum-min-max)/(salary.length - 2);
    }
}

class Solution {
    public int countOdds(int low, int high) {
        int count  = (high-low)/2;
           if(high%2 ==0 && low%2 == 0){}
           else count +=1;
        return count;
    }
}

class Solution {
    public boolean wordPattern(String pattern, String s) {
        HashMap<Character,String> map = new HashMap<>();
        String[] sWords = s.split(" ");
        if(sWords.length != pattern.length()) return false;
        for(int i = 0; i < pattern.length(); i++){
            for (Map.Entry<Character, String> entry : map.entrySet()) {
                if(entry.getValue().equals(sWords[i]) && entry.getKey() != pattern.charAt(i)) return false;
                 if(!entry.getValue().equals(sWords[i]) && entry.getKey() == pattern.charAt(i)) return false;
            }
                 map.put(pattern.charAt(i),sWords[i]);

        }
        return true;
    }
}