Leet Code 300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/ 

package pep.Day84;

import java.sql.Array;
import java.util.Arrays;

public class LeetCode_300_Longest_Increasing_Subsequence {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS_recursion(nums));
        System.out.println(lengthOfLIS_memoisation(nums));

        System.out.println(lengthOfLIS_tabulation(nums));
    }

    static int finalAnswer = 1;

    public static int lengthOfLIS_recursion(int[] nums) {
        finalAnswer = 1;
        int n = nums.length;
        LIS_recursion(nums, n - 1);

        return finalAnswer;
    }

    public static int LIS_recursion(int[] nums, int endIndex) {

        int maxLength = 1;
        for (int startingIndex = 0; startingIndex < endIndex; startingIndex++) {
            // har element ne apna apna LIS laa kr diya
            int len = LIS_recursion(nums, startingIndex);

            // jiska LIS chotta hoga, uske lea check krenge
            if (nums[startingIndex] < nums[endIndex]) {
                int l = len + 1;

                // jo bhi length aae usko maxLength se compare krenge
                maxLength = Math.max(maxLength, l);
            }
        }
        finalAnswer = Math.max(finalAnswer, maxLength);
        return maxLength;
    }


    public static int lengthOfLIS_memoisation(int[] nums) {
        finalAnswer = 1;
        int n = nums.length;
        LIS_memoisation(nums, n - 1, new int[n]);

        return finalAnswer;
    }

    public static int LIS_memoisation(int[] nums, int endIndex, int[] dp) {
        if (dp[endIndex] != 0)
            return dp[endIndex];
        int maxLength = 1;
        for (int startingIndex = 0; startingIndex < endIndex; startingIndex++) {
            // har element ne apna apna LIS laa kr diya
            int len = LIS_memoisation(nums, startingIndex, dp);

            // jiska LIS chotta hoga, uske lea check krenge
            if (nums[startingIndex] < nums[endIndex]) {
                int l = len + 1;

                // jo bhi length aae usko maxLength se compare krenge
                maxLength = Math.max(maxLength, l);
            }
        }
        finalAnswer = Math.max(finalAnswer, maxLength);
        return dp[endIndex] = maxLength;
    }

    public static int lengthOfLIS_tabulation(int[] nums) {
//        finalAnswer = 1;
        int n = nums.length;
        int[] dp = new int[n];
//        LIS_recursion(nums, n - 1);
        return LIS_tabulation(nums, dp);
//
//        return finalAnswer;
    }

    private static int LIS_tabulation(int[] nums, int[] dp) {

        // by default 1 toh hoga hi sabme
        Arrays.fill(dp, 1);


        int maxLength = 1;
        for (int endIndex = 0; endIndex < nums.length; endIndex++) {
            for (int startingIndex = 0; startingIndex < endIndex; startingIndex++) {
                // jiska LIS chotta hoga, uske lea check krenge
                if (nums[startingIndex] < nums[endIndex]) {
                    dp[endIndex] = Math.max(dp[endIndex], dp[startingIndex] + 1);
                }
            }

            maxLength = Math.max(maxLength, dp[endIndex]);

        }
        return maxLength;
    }
}

Unbounded Knapsack

package pep.Day84;

public class Unbounded_Knapsack {
    public static void main(String[] args) {

        int[] values = {15, 14, 10, 45, 30};
        int[] weight = {2, 5, 1, 3, 4};

        int maxCapacity = 7;
        int[] dp = new int[maxCapacity + 1];

        for (int cap = 0; cap <= maxCapacity; cap++) {
            int max = 0;
            for (int i = 0; i < values.length; i++) {
                int val = values[i];
                int wt = weight[i];

                // check item
                if (cap >= wt) {
                    int amt = val + dp[cap - wt];
                    max = Math.max(max, amt);

                }
            }

            dp[cap] = max;
        }

        System.out.println(dp[maxCapacity]);
    }
}

Zero One Knapsack

package pep.Day83;

public class Zero_One_Knapsack {
    public static void main(String[] args) {

        int[] values = {15, 14, 10, 45, 30};
        int n = values.length;
        int[] weight = {2, 5, 1, 3, 4};

        int maxCap = 7;

        int[][] dp = new int[n + 1][maxCap + 1];

        for (int i = 1; i <= n; i++) {

            for (int cap = 1; cap <= maxCap; cap++) {
                int val = values[i - 1];
                int wt = weight[i - 1];

                if (cap >= wt) {
                    // INCLUDE WALA CASE: jisme weight<= capacity se

                    int include = val + dp[i - 1][cap - wt];

                    int exclude = dp[i - 1][cap];
                    dp[i][cap] = Math.max(include, exclude);
                } else {
                    // EXCLUDE WALA CASE

                    dp[i][cap] = dp[i - 1][cap];
                }
            }
        }

        System.out.println(dp[n][maxCap]);
    }
}

Leet Code 140. Word Break II

package pep.Day83;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class LeetCode_140_Word_Break_2 {

    public static void main(String[] args) {
        String s = "catsanddog";
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");

        System.out.println(wordBreak(s, wordDict));
    }

    public static List<String> wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        int maxLen = 0;

        for (String ss : wordDict) {
            set.add(ss);
            maxLen = Math.max(maxLen, ss.length());
        }

        int n = s.length();
        boolean[] dp = new boolean[n + 1];

        // yha tak ka word present hai, yha se check krna start kr do
        dp[0] = true;
        for (int i = 0; i <= n; i++) {
            if (dp[i] == true) {
                for (int l = 1; l <= maxLen && i + l <= n; l++) {
                    String sb = s.substring(i, i + l);
                    if (set.contains(sb)) {
                        dp[i + l] = true;
                    }

                }
            }
        }

        List<String> ans = new ArrayList<>();
        // koi answer hi nhi mila to return empty List
        if (dp[n] == false)
            return ans;

        // recursion call lagaenge ki mujhe answer laa kr de de
        helper(ans, 0, "", s, set, dp, maxLen);

        return ans;

    }

    public static void helper(List<String> ans, int i, String asf, String s, HashSet<String> set, boolean[] dp, int maxLen) {
        if (i >= s.length()) {
            ans.add(asf.substring(0, asf.length() - 1));
            return;
        }
        for (int l = 1; l <= maxLen && i + l <= s.length(); l++) {
            // agr (0,2) wala substring milta tha to hum 3 index pr TRUE mark krte the
            // hence, hum dp me check krenge
            if (dp[i + l]) {
                String ss = s.substring(i, i + l);
                if (set.contains(ss)) {
                    helper(ans, i + l, asf + ss + " ", s, set, dp, maxLen);
                }
            }

        }

    }
}

Leet Code 139. Word Break

https://leetcode.com/problems/word-break/

Example 1:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Iss wale eg. me 9th index pr False reh jaega, because "og" word nhi mila humein dictionary me,

hence, will return FALSE.

package pep.Day83;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class LeetCode_139_Word_Break {

    public static void main(String[] args) {
        String s = "applepenapple";
        List<String> wordDict = Arrays.asList("apple", "pen");

        System.out.println(wordBreak(s, wordDict));
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        int maxLen = 0;

        for (String ss : wordDict) {
            set.add(ss);
            maxLen = Math.max(maxLen, ss.length());
        }

        int n = s.length();
        boolean[] dp = new boolean[n + 1];

        // yha tak ka word present hai, yha se check krna start kr do
        dp[0] = true;
        for (int i = 0; i <= n; i++) {
            if (dp[i] == true) {
                for (int l = 1; l <= maxLen && i + l <= n; l++) {
                    String sb = s.substring(i, i + l);
                    if (set.contains(sb)) {
                        dp[i + l] = true;
                    }

                }
            }
        }
        // LAST INDEX PR TRUE HOGA TO SAB WORD MIL JAENGE
        return dp[n];
    }
}

Utf - 8 Encoding

package pep.Day82;

public class UTF8_Encoding {
    public static void main(String[] args) {
        int[] arr = {197, 1};
        for (int i : arr) {
            System.out.println(Integer.toBinaryString(i));
        }
        System.out.println(solution(arr));
    }

    private static boolean solution(int[] arr) {
        int byteToBeChecked = 0;
        for (int i : arr) {
            // pehle byte check krne ke lea
            if (byteToBeChecked == 0) {
                if (i >> 7 == 0b0)
                    byteToBeChecked = 0;
                else if (i >> 5 == 0b110)
                    byteToBeChecked = 1;
                else if (i >> 4 == 0b1110)
                    byteToBeChecked = 2;
                else if (i >> 3 == 0b11110)
                    byteToBeChecked = 3;
            } else {
                // agr byteToBeChecked= 1,2,3 to baki sab remaining byte 10 se start hogi
                if (i >> 6 != 0b10)
                    return false;
                byteToBeChecked--;
            }

        }

        if (byteToBeChecked == 0)
            return true;
        return false;
    }
}

XOR Of Sum Of All Pairs

package pep.Day82;

public class XOR_of_Sum_of_all_pairs {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7};

        int ans = 0;
        for (int i : arr) {
            ans = ans ^ i;
        }

        System.out.println(ans);
    }
}

One Repeating And One Missing

package pep.Day82;

import java.util.Scanner;

public class One_Repeating_and_One_Missing {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        solution(arr);
    }

    private static void solution(int[] arr) {
        int xor_of_array = 0, a = 0, b = 0;

        // xor of array and number find krnge
        // xor_of_array = a^b
        for (int i : arr) {
            xor_of_array = xor_of_array ^ i;
        }

        for (int i = 1; i <= arr.length; i++) {
            xor_of_array = xor_of_array ^ i;
        }

        // aab humein a, b ki value find krne hain

        int right_most_set_bit = xor_of_array & (-xor_of_array);

        for (int i : arr) {
            if ((i & right_most_set_bit) == 0)
                a = a ^ i;
            else
                b = b ^ i;
        }

        for (int i = 1; i <= arr.length; i++) {
            if ((i & right_most_set_bit) == 0)
                a = a ^ i;
            else
                b = b ^ i;
        }

        // aab missing and repeating print krna hai
        for (int i : arr) {
            if (i == a) {
                System.out.println("Missing Number -> " + b);
                System.out.println("Repeating Number -> " + a);
            } else if (i == b) {
                System.out.println("Missing Number -> " + a);
                System.out.println("Repeating Number -> " + b);
            }
        }

    }
}

All Repeating Except Two

package pep.Day82;

import java.io.*;
import java.util.*;

public class All_Repeating_Except_Two {

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scn.nextInt();
        }
        solution(arr);
    }

    public static void solution(int[] arr) {
        int xor_of_array = 0;
        for (int i : arr) {
            xor_of_array = xor_of_array ^ i;
        }

        int right_most_set_bit = (xor_of_array & (-xor_of_array));
        int a = 0, b = 0;
        for (int i : arr) {
            if ((i & right_most_set_bit) == 0)
                a = a ^ i;
            else b = b ^ i;
        }

        if (a > b) {
            System.out.println(b + "\n" + a);
        } else {
            System.out.println(a + "\n" + b);
        }

    }

}

All Repeating Except One

package pep.Day82;

public class All_Repeating_Except_One {
    public static void main(String[] args) {
        int arr[] = {2, 2, 1, 3, 3, 4, 4, 7, 9, 9, 7};
        int ans = 0;
        for (int x :
                arr) {
            ans = ans ^ x;
        }

        System.out.println(ans);
    }

} 

Minimum Number Of Software Developers

package pep.Day81;

import java.io.*;
import java.util.*;

public class Minimum_Number_Of_Software_Developers {
    static ArrayList<Integer> sol = new ArrayList<>();

    //nskills -> total number of skills
    // cp -> current person
    // onesol -> solution
    // skills -> a OR b  agr a+b krna hoga
    public static void solution(int[] people, int nskills, int cp, ArrayList<Integer> onesol, int skills) {
        // BASE CASE
        // cp out of range nhi jaana cheye
        if (cp == people.length) {
            if (skills == Math.pow(2, nskills) - 1) {
                //if (skills == (1 << nskills) - 1) {

                // ek ans mil gya hai
                // sol.size() == 0 -> first ans
                // onesol.size() < sol.size() -> better ans mil gya
                if (sol.size() == 0 || onesol.size() < sol.size()) {
                    // sol = onesol; -> this will not work
                    // sol mujhe humesha khale array return krega
                    // jab hum backtracking krte hain toh hum onesol se remove krte hain
                    // sol, onesol ko point krne lagega and hume onesol ko khale kr diya

                    // SOlution: deep copy bnaenge
                    sol = new ArrayList<>(onesol);
                }

            }

            return;
        }
        // write your code here

        // 1. jisme banda aana nhi chahta hai
        // jisme hum skill ko include nhi kr rhe

        // cp+1 islea kiya -> 'a' ne decide kr liya hai ki woh nhi aaega, now check for 'b'
        // onesol
        // skills -> jab 'a' aana hi nhi chahta to uski skills bhi add nhi krnge, toh skills same rhenge
        solution(people, nskills, cp + 1, onesol, skills);

        // 2. agr banda aana chahta hai

        // add krenge currentPerson ke index ko
        onesol.add(cp);

        // kise person ko add kr rhe hain, to hum current person ke skill set se OR kr denge
        solution(people, nskills, cp + 1, onesol, (skills | people[cp]));

        // back tracking ki jrurt padege
        onesol.remove(onesol.size() - 1);


    }

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        HashMap<String, Integer> smap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            smap.put(scn.next(), i);
        }

        int np = scn.nextInt();
        int[] people = new int[np];
        for (int i = 0; i < np; i++) {
            int personSkills = scn.nextInt();
            for (int j = 0; j < personSkills; j++) {
                String skill = scn.next();
                int snum = smap.get(skill);
                people[i] = people[i] | (1 << snum);
            }
        }

        solution(people, n, 0, new ArrayList<>(), 0);
        System.out.println(sol);

    }

}

Kernighans Algorithm

package pep.Day81;

import java.util.Scanner;

public class Kernighans_Algorithm {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int ans = 0;

        while (n > 0) {
            int rmsbm = n & -n;
            ans++;
            n -= rmsbm;
        }

        System.out.println(ans);
    }
}

Print Value Of Rsb Mask

 

                                           

package pep.Day81;

public class Print_Value_Of_Rsb_Mask {

    public static void main(String[] args) {
        int n = 58;

        System.out.println(Integer.toBinaryString(n & (-n)));
    }
}

Bits Introduction

 

Leet Code 720. Longest Word in Dictionary

Example 1:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

package pep.Day80;

public class LeetCode_720_Longest_Word_in_Dictionary {
    public static void main(String[] args) {
        String[] words = {"w", "wo", "wor", "worl", "world", "worles", "worle"};
        System.out.println(longestWord(words));
    }

    static class Node {
        Node[] children = new Node[26];
        String isEnd = null;
    }

    static Node root = new Node();

    public static void insert(String word) {
        Node curr = root;
        for (int i = 0; i < word.length(); i++) {
            char tba = word.charAt(i);
            if (curr.children[tba - 'a'] == null)
                curr.children[tba - 'a'] = new Node();
            curr = curr.children[tba - 'a'];
        }
        curr.isEnd = word;
    }

    static String ans = "";

    public static String longestWord(String[] words) {
        for (String word : words) {
            insert(word);
        }
        dfs(root);
        return ans;
    }

    private static void dfs(Node node) {
        for (Node child : node.children) {
            if (child != null && child.isEnd != null) {
                // aab check krenge ki better potential ans mil rha ho

                if (child.isEnd.length() > ans.length())
                    ans = child.isEnd;
                dfs(child);

            }
        }
    }
}

Leet Code 677. Map Sum Pairs

Example 1:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");  

package pep.Day80;

import java.util.HashMap;

public class LeetCode_677_Map_Sum_Pairs {
    public static void main(String[] args) {

        insert("car", 1);
        insert("card", 4);
        insert("cards", 5);
        insert("carts", 6);
        insert("cars", 7);
        System.out.println(sum("ca"));
    }

    static class Node {
        Node[] children = new Node[26];
        int score = 0;
    }

    static Node root = new Node();
    static HashMap<String, Integer> map = new HashMap<>();

    public static void insert(String word, int val) {
        int diff = val - map.getOrDefault(word, 0);
        map.put(word, val);

        Node curr = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);

            // alphabet exist nhi krta trie me to nae node bnaenge
            if (curr.children[ch - 'a'] == null) {
                curr.children[ch - 'a'] = new Node();

            }
            curr.children[ch - 'a'].score += diff;
            curr = curr.children[ch - 'a'];
        }

    }

    public static int sum(String prefix) {
        int sum = 0;
        Node curr = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            if (curr.children[ch - 'a'] == null)
                return 0;
            curr = curr.children[ch - 'a'];
        }

        return curr.score;
    }
}