class Solution {
    public int binaryGap(int n) {
        int res=0, d=-30;
        
        while(n>0){
            if(n%2==1){
                res=Math.max(res, d);
                d=0;
            }
            n=n/2;
            d++;
        }
        
        return res;
    }
}

class Solution {
    public int numWaterBottles(int bottle, int exchange) {
        int count=0;
        
        while(bottle>0){
            count+=bottle-bottle%exchange;
            if(bottle>=exchange)
                bottle=bottle/exchange+bottle%exchange;
            else
                break;
        }
            
        return count+bottle;
    }
}

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int count=0;
        Arrays.sort(costs);
        
        for(int i=0; i<costs.length&&coins>0; i++){
            if(costs[i]<=coins){
                coins-=costs[i];
                count++;
            }
        }
        return count;
    }
}

class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        ArrayList<Integer> ans=new ArrayList<Integer>();
        int[] helper1=new int[101];
        int[] helper2=new int[101];
        int[] helper3=new int[101];
        
        for(int num:nums1)
            helper1[num]=1;
        
        for(int num:nums2)
            helper2[num]=1;
        
        for(int num:nums3)
            helper3[num]=1;
        
        for(int i=0; i<helper1.length; i++){
            if(helper1[i]+helper2[i]+helper3[i]>1)
                ans.add(i);
        }
        
        return ans;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return head;
        ListNode curr=head;
        while(curr.next!=null){
            if(curr.val==curr.next.val){
                curr.next=curr.next.next;
            }
            else
                curr=curr.next;
        }
        
        return head;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA=headA, currB=headB;
        
        while(currA!=currB){
            if(currA==null)
                currA=headB;
            else
                currA=currA.next;
            
            if(currB==null)
                currB=headA;
            else
                currB=currB.next;
        }
        
        return currA;
        
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> arr=new ArrayList<>();
        ListNode curr=head;
        
        while(curr!=null){
            arr.add(curr.val);
            curr=curr.next;
        }
        
        for(int i=0; i<arr.size()/2; i++){
            if(arr.get(i)!=arr.get(arr.size()-i-1))
                return false;
            
        }
        
        return true;
    }
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode curr=head;
        if(head==null) return head;
        while(curr.next!=null){
            if(curr.next.val==val)
                curr.next=curr.next.next;
            else
                curr=curr.next;
        }
        if(head.val==val) return head.next;
        
        return head;
    }
}

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res=new ArrayList<>();
        int[] count=new int[nums.length+1];
        
        for(int num:nums)
            count[num]++;
        
        for(int i=1; i<count.length; i++){
            if(count[i]==0)
                res.add(i);
        }
        
        return res;
    }
}

class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] count=new int[101];
        int year=0, max=0;
        
        for(int i=0; i<logs.length; i++){
            for(int j=logs[i][0]; j<logs[i][1]; j++)
                count[j-1950]++;
        }
        
        for(int i=count.length-1; i>=0; i--){
            if(count[i]>=max){
                max=count[i];
                year=i+1950;
            }
        }
        
        return year;
    }
}

class Solution {
    public int addDigits(int num) {
        
        return add(num);
    }
    
    int add(int num){
        if(num<10) return num;
        int rem=0, sum=0;
        while(num>0){
            rem=num%10;
            num/=10;
            sum+=rem;
        }
        
        num=sum;
        return add(num);
        
    }
}

class Solution {
    public int largestPerimeter(int[] nums) {
        int max=0;
        Arrays.sort(nums);
        for(int i=nums.length-3; i>=0; i--){
            if(nums[i]+nums[i+1]>nums[i+2])
                return nums[i]+nums[i+1]+nums[i+2];
        }
        
        return 0;
    }
}

class Solution {
    public int missingNumber(int[] nums) {
        int count[]=new int[nums.length+1];
        
        for(int num:nums)
            count[num]++;
        
        for(int i=0; i<count.length; i++){
            if(count[i]==0)
                return i;
        }
        
        return 0;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null) return false;
        ListNode curr=head, ahead=head;
        
        while(ahead.next!=null&&ahead.next.next!=null){
            curr=curr.next;
            ahead=ahead.next.next;
            
            if(curr==ahead)
                return true;
        }
        
        return false;
    }
}

class Solution {
    public int hammingDistance(int x, int y) {
        int num=x^y;
        int count=0;
        while(num>0){
            if(num%2==1)
                count++;
            
            num/=2;
        }
        
        return count;
    }
}

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int length=0, k1=k;
        ListNode curr=head;
        
        while(curr!=null){
            curr=curr.next;
            length++;
        }
        
        ListNode first=head, second=head;
        
        while(k>1){
            first=first.next;
            k --;
        }
        
        while(length-k1>0){
            second=second.next;
            length--;
        }
        
        int temp=first.val;
        first.val=second.val;
        second.val=temp;
        
        return head;
        
    }
}

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder res=new StringBuilder();
        Stack stack=new Stack();
        int size=0;
        for(char ch:s.toCharArray()){
            if(ch=='('){
                stack.push(ch);
                size++;
                if(size!=1)
                    res.append(ch);
            }
            
            if(ch==')'){
                stack.pop();
                size--;
                if(size!=0)
                    res.append(ch);
            }
        }
        
        return res.toString();
    }
}

class Solution {
    public int[] finalPrices(int[] prices) {
        Stack<Integer> stack=new Stack<>();
        for(int i=0; i<prices.length; i++){
            while(stack.size()>0&&prices[stack.peek()]>=prices[i]){
                prices[stack.peek()]-=prices[i];
                stack.pop();
            }
            stack.push(i);
        }
        
        return prices;
    }
}

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder res=new StringBuilder();
        Stack<Character> stack=new Stack<>();
        char[] letters=s.toCharArray();
        
        for(int i=letters.length-1; i>=0; i--){
            if(!stack.isEmpty()&&letters[i]==stack.peek())
                stack.pop();
            else
                stack.push(letters[i]);
        }
        
        while(!stack.isEmpty()){
            res.append(stack.pop());
        }
        
        return res.toString();
    }
}

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] count=new int[2];
        int i=0;
        
        for(int student:students)
            count[student]++;
        
        for(; i<sandwiches.length && count[sandwiches[i]]!=0; i++)
            count[sandwiches[i]]--;
        
        return sandwiches.length-i;
    }
}