class Solution {
    public boolean isPowerOfThree(int n) {
        if(n <= 0) return false;
        if(n == 1) return true;
        if(n % 3 == 0) return isPowerOfThree(n / 3);
        else return false;
    }
}

class Solution {
    public boolean isPowerOfFour(int n) {
        if(n <= 0) return false;
        if(n == 1) return true;
        
        if(n % 4 == 0) return isPowerOfFour(n / 4);
        else return false;
    }
}

class Solution {
    public boolean isPossible(int[] target) {
        int maxIndex = 0, sum = 0;
        for(int i = 0; i < target.length; i++){
            if(target[i] <= 0) return false;    //数组中出现小于1的数，则不成立，返回false
            if(target[maxIndex] < target[i]) maxIndex = i;
            sum += target[i];
        }
        if(sum == target.length) return true;   //加和等于长度，则数组内全部为1，返回true
        int others = sum - target[maxIndex];
        if(others == 0) return false;   //没有其他值时返回false
        target[maxIndex] -= others;
        int n = 1;
        while(target[maxIndex] > others){
            target[maxIndex] -= n * others;
            if(target[maxIndex] <= 0){
                target[maxIndex] += n * others;
                break;
            }
            n*=2;   //因子每次翻倍，快速逼近
        }
        return isPossible(target);
    }
}

class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int sum = 0;
        for(int num : target){
            pq.offer(num);
            sum+=num;
        }
        while(true){
            int max = pq.poll();
            if(max == 1) return true;

            sum -= max;
            max = max - sum;
            if(sum <= 0 || max <= 0) return false;
            
            int n = 1;
            while(max > sum){
                max -= n * sum;
                if(max <= 0){
                    max += n * sum;
                    break;
                }
                n*=2;
            }
            sum += max;
            pq.offer(max);
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0; //记录摄像头个数
    public int minCameraCover(TreeNode root) {
        if(judge(root) == 0) res++;  //如果根节点未被监控，则需要增加一个摄像机
        return res;
    }
    public int judge(TreeNode root){
        if(root == null) return 2;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1) return dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : -dividend; //当dividend为最小整数时，其负数溢出，此时返回Integer.MAX_VALUE
        int a = dividend, b = divisor;
        int sign = a > 0 && b > 0 || a < 0 && b < 0 ? 1 : -1;   //记录除数与被除数是否同号
        if(dividend > 0) a = -a;    //将除数与被除数转换为负数，因为负数能记录的数值比正数大1，防止溢出
        if(divisor > 0) b = -b;
        if(a > b) return 0; //被除数小于除数时返回0
        int res = 1;
        while(a <= b+b && b+b < 0){ //算法核心，快速乘法
            b += b; //除数每次翻倍，直到大于被除数
            res += res; //商的结果翻倍
        }
        res = sign == 1 ? res : -res;   //根据是否同号记录商
        
        divisor = dividend > 0 ? -divisor : divisor;  //当原有被除数是正数时，要将除数取反
        return res + divide(a-b, divisor);
    }
}

class Solution {
    public int numberOfSteps(int num) {
        int count =0;
        while(num != 0){
            count++;
            if((num & 1) == 0){
                num/=2;
            }
            else{
                num--;
            }
        }
        return count;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null) return null;
        if(original.equals(target)) return cloned;
        
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if(left != null) return left;
        else return getTargetCopy(original.right, cloned.right, target);
    }
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Queue<NestedInteger> q;
    public NestedIterator(List<NestedInteger> nestedList) {
        q = new LinkedList<>();
        for(NestedInteger item : nestedList){
            buildQueue(item);
        }
    }
    
    private void buildQueue(NestedInteger ni){
        if(!ni.isInteger()){
            for(NestedInteger item : ni.getList()){
                buildQueue(item);
            }
        }
        else{
            q.offer(ni);
        }
    }

    @Override
    public Integer next() {
        return q.poll().getInteger();
    }

    @Override
    public boolean hasNext() {
        return !q.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;     
        if(root.val > key) root.left = deleteNode(root.left, key);  //如果当前值大于搜索值则搜索左子节点，否则搜索右子节点
        else if(root.val < key) root.right = deleteNode(root.right, key);
        else{   //如果当前值等于搜索值，根据子节点情况删除节点
            if(root.right != null){ //右子节点不为空则将当前root的值设置为继任者的值，然后向下递归删除继任者
                root.val = getSuccessor(root);
                root.right = deleteNode(root.right, root.val);
            }
            else if(root.left != null){ //左子节点不为空则将当前root的值设置为前驱者的值，然后向下递归删除继任者
                root.val = getPredecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
            else{
                root = null;
            }
        }
        return root;
    }
    
    private int getSuccessor(TreeNode root){
        root = root.right;
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }
    private int getPredecessor(TreeNode root){
        root = root.left;
        while(root.right != null){
            root = root.right;
        }
        return root.val;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if(root == null) return null;
        if(root == p) return p; //found target and return
        if(root == q) return q; //found target and return
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);  //search left branch
        TreeNode right = lowestCommonAncestor(root.right, p, q);    //search right branch
           
        if(left == null) return right;  //if left not found target, return the right branch
        else if(right == null) return left; //if right not found target, return the left branch
        else return root;   //if both found target, return the root
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ret;
    int target;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ret = new ArrayList<>();
        if(root == null) return ret;
        target = targetSum;
        backTrack(root, 0, new ArrayList<>());
        return ret;
    }
    
    private void backTrack(TreeNode root, int sum, List<Integer> nodes){
        if(root.left == null && root.right == null){
            sum += root.val;
            if(sum == target){
                nodes.add(root.val);
                ret.add(new ArrayList<Integer>(nodes));
                nodes.remove(nodes.size()-1);
            }
            return;
        }
        nodes.add(root.val);
        sum += root.val;
        if(root.left != null) backTrack(root.left, sum, nodes);
        if(root.right != null) backTrack(root.right, sum, nodes);
        nodes.remove(nodes.size()-1);
        sum -= root.val;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length-1);
    }
    
    private TreeNode build(int[] nums, int left, int right){
        if(left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid-1);
        root.right = build(nums, mid+1, right);
        
        return root;
    }
}

class Solution {
    public int findTheWinner(int n, int k) {
        if(n == 1) return 1;
        int ans = findTheWinner(n-1, k) + k;
        return ans % n == 0 ? n : ans % n;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    int K;
    ListNode next;
    ListNode prev;
    ListNode last;
    ListNode first;
    ListNode second;
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        
        K = k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        prev = dummy;
        next = null;
        last = null;
        first = prev;
        second = prev.next;
        
        reverse(prev, dummy.next, k);
        
        return dummy.next;
    }
    
    private boolean reverse(ListNode prev, ListNode curr, int k){
        if(curr == null) return false;
        if(k == 1){
            last = curr;
            next = curr.next;
            curr.next = prev;
            return true;
        }
        
        if( reverse(curr, curr.next, k-1) ){
            curr.next = prev;
            if(k == K){
                first.next = last;
                second.next = next;
                first = curr;
                second = curr.next;
            
                reverse(first, second, k);
            }
            return true;
        }
        return false;
    }
    
    private void print(ListNode root){
        while(root != null){
            root = root.next;
        }
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        swap(dummy, head);
        return dummy.next;
    }
    
    private void swap(ListNode pre, ListNode root){
        if(root == null || root.next == null){
            return;
        }
        else if(root != null && root.next != null){
            
            ListNode last = root.next.next;
            ListNode next = root.next;
            pre.next = next;
            next.next = root;
            root.next = last;
        }
        swap(root, root.next);
    }
}