Notes

https://notes.io/qFVvW (1,30)


1.Noise In The Library-->>
2.Challenges To Find First Occurrence-->>
3.Solve Challenges To Win The Game-->>
4.Students standing in a line-->>
5.Integer Square Root -->>
6.Search element in a rotated sorted array -->>
7.Count frequency of each character -->>
8.First Unique Character -->>
9.Longest Consecutive Subsequence-->>
10.Check if two arrays are equal or not-->>
11.Maximum Frequency in a sequence(c++)-->>
12.Find all pairs with K difference -->>
13.Insurance Agent with a target-->>
14.Find all pairs with sum K-->>
15.Find contiguous sub-array with given sum-->>
16.Sort an array using quick sort-->>
17.Gifts for everyone with no bias -->>
18.Kth largest number-->>
19.Sort an array using merge sort-->>
20.Queries for K largest-->>
21.Implement Priority Queue using Linked List -->>
22.Sort an array using heap sort-->>
23.Create a binary tree from array-->
24.Print binary tree with level order traversal-->>
25.Print nodes at odd levels of the binary tree -->>
26.Write iterative version of inorder traversal -->>
27.Complete the inorder(), preorder() and postorder()
functions for traversal with recursion-->>
28.Construct tree from given inorder and post order traversal-->>
29.Print all paths to leaves and their details of a binary tree-->>
30.Find the right node of a given node -->>
31.Given binary tree is binary search tree or not -->>
32.Find the kth smallest element in the binary search tree-->>
33.Find K largest elements in array -->>
34.Convert min Heap to max Heap -->>
35.Connect the sticks of different lengths with minimum cost-->>
36. Find the minimum number of edges in a path of a graph-->
37. Find path in a directed graph-->
38. number of islands-->
39. Shortest path in a binary maze -->
40. Depth first traversal of graph-->
41. Breadth first traversal of graph-->
42. Find the cycle in the undirected graph -->
43. Fractional Knapsack problem -->
44. Interval scheduling Problem -->
45. job scheduling with deadlines -->
46. activity selection problem -->
47. Count number of ways to cover a distance -->
48. Minimum Cost path to last element of matrix-->
49. Longest common subsequence-->
50. The Subset Sum problem-->
51. Matrix Chain multiplication problem-->
52. 0-1 knapsack problem -->
53. Tom And Permutations -->
54. Print all strings of n-bits -->
55. Solve N queen problem -->
56. Rat in a maze problem -->
57.Count the number of leaf and non-leaf nodes in a binary tree -->>
58.Convert Level Order Traversal to BST-->>
59.Check if a given tree is max-heap or not (c++)-->>
60.Count word in the board—>


1.Noise In The Library-->
class Result {
  static long totalNoise(int N, int book_IDs[], int K, int booksToFind[]) {
    // Write your code here
    long sum = 0;
    for(int i=0;i<K;i++){
      sum+=(long)bs(book_IDs,booksToFind[i]);
    }
    return sum;
  }
  static long bs(int[] bookId,int x){
    int n = bookId.length;
    int s = 0;
    int e = n-1;
    while(s<=e){
      int mid = s+(e-s)/2;
      if(bookId[mid]==x){
        return mid;
      }
      else if(bookId[mid]>x){
        s=mid+1;
      }
      else{
        e=mid-1;
      }
    }
    return n;
  }
}

2.Challenges To Find First Occurrence-->>
class Result {
  static long solveChallenges(int N, int arr[], int K, int challenges[]) {
    // Write your code here
    long ans = 0;
    for(int i=0;i<K;i++){
      int index = binSearch(arr,challenges[i],0,N-1);
      if(index==-1)
        ans+=-1;
      else{
        while(index-1>=0 && arr[index] == challenges[i] && arr[index-1] == challenges[i]){
          index = binSearch(arr,challenges[i],0,index-1);
        }
      ans+=index;
      }
    }
    return ans;
  }
  static int binSearch(int[] arr,int target,int s,int e){
    while(s<=e){
      int mid = s + (e-s)/2;
      if(arr[mid] > target)
        e = mid -1;
      else if(arr[mid] < target)
        s = mid + 1;
      else
        return mid;
    }
    return -1;
  }
}

3.Solve Challenges To Win The Game-->>
class Result {
  static long solveChallenges(int N, int arr[], int K, int challenges[]) {
    // Write your code here
    long ans=0;
for(int i=0;i<K;i++){
      int firstOcc = first(challenges[i],arr,0,N-1);
      int lastOcc = last(challenges[i],arr,0,N-1);
      if(firstOcc!=-1)
        ans+=lastOcc - firstOcc + 1;
    }
    return ans;
  }
  static int first(int target,int[] arr,int st,int en){
    if(st<=en){
    int mid = st+(en-st)/2;
    if((mid==0 || arr[mid-1]<target) && arr[mid]==target)
      return mid;
    else if(arr[mid]<target)
      return first(target,arr,mid+1,en);
    else
      return first(target,arr,st,mid-1);
    }
    return -1;
  }
  static int last(int target,int[] arr,int st,int en){
    if(st<=en){
    int mid = st+(en-st)/2;
    if((mid==arr.length-1 || arr[mid+1]>target) && arr[mid]==target)
      return mid;
    else if(arr[mid]>target)
      return last(target,arr,st,mid-1);
    else
      return last(target,arr,mid+1,en);
    }
    return -1;
  }
}

4.Students standing in a line-->>
class Result {
  // Return the minimum number of students that were shifted to the end
  int studentShifted(int rollNo[], int N) {
    // Write your code here
    int st=0,en=N-1;
    while(st<en){
      int mid = st+(en-st)/2;
      if(rollNo[mid]<rollNo[en])
        st = mid+1;
      else
        en = mid;
    }
    if(en==0)
      return 0;
    return N-en;
  }
}

5 Integer Square Root -->>
class Result {
  static long sqrt(long n) {
    // Write your code here
long st=0,en=n,ans=0;
    while(st<=en){
      long mid = st+(en-st)/2;
      if(mid==0){
        if(mid*mid>n)
        en = mid-1;
      else if(mid*mid<n){
        ans=mid;
        st = mid+1;
      }
      else{
        ans=mid;
        break;
      }
      }
      else{
      if(mid>n/mid)
        en = mid-1;
      else if(mid<n/mid){
        ans=mid;
        st = mid+1;
      }
      else{
        ans=mid;
        break;
      }
      }
    }
    return ans;
  }
}

6 Search element in a rotated sorted array -->>
class Result {
  static int searchRotatedSortedArray(int arr[], int k) {
    // Write your code here
    int n=arr.length;
    int st=0,en=n-1;
    while(st<en){
      int mid = st + (en-st)/2;
      if(arr[mid]>arr[en])
        st = mid+1;
      else
        en = mid;
    }
    if(k<=arr[n-1] && k>=arr[en]){
      st = en;
      en = n-1;
  }
    else{
      st=0;
      en = en - 1;
    }
    while(st<=en){
      int mid = st+(en-st)/2;
      if(arr[mid]<k)
        st = mid+1;
      else if(arr[mid]>k)
        en = mid-1;
      else
        return mid;
    }
    return -1;
}
}

7 Count frequency of each character-->>
class Result {
    static void countFrequency(String str){
        // Write your code here
      int[] arr = new int[26];
  for(int i=0;i<str.length();i++){
    arr[str.charAt(i)-'a']++;
  }
  for(int i=0;i<str.length();i++){
    if(arr[str.charAt(i)-'a']==-1)
      continue;
    if(arr[str.charAt(i)-'a']>0){
      System.out.print(str.charAt(i)+""+arr[str.charAt(i)-'a']+" ");
      arr[str.charAt(i)-'a']=-1;
    }
  }
    }
}

8 First Unique Character-->>
import java.util.*;
class Result {
  static int firstUniqueChar(String str) {
    // Write your code here
    HashMap<Character,Integer> map = new HashMap<>();
    for(int i=0;i<str.length();i++){
      char ch = str.charAt(i);
      if(map.containsKey(ch)){
        map.put(ch,map.get(ch)+1);
      }
      else{
        map.put(ch,1);
      }
    }
    for(int i=0;i<str.length();i++){
      if(map.get(str.charAt(i))==1){
        return i;
      }
    }
      return -1;
  }
}

9 Longest Consecutive Subsequence-->>
class Result {
  static int LongestConsecutiveSubsequence(int a[], int n) {
// Write your code here
    int maximum = Integer.MIN_VALUE;
    HashSet<Integer> hashSet = new HashSet<>();
    for(int i=0;i<n;i++){
      maximum = Math.max(maximum,a[i]);
      hashSet.add(a[i]);
    }
    int[] vis = new int[maximum+1];
    int maxCount = 1;
    for(int i=0;i<n;i++){
      if(vis[a[i]]==1)
        continue;
      int val = a[i]+1;
      int count=1;
      while(hashSet.contains(val)){
        vis[val]=1;
        val++;
        count++;
      }
      maxCount = Math.max(maxCount,count);
    }
    return maxCount;
  }
}

10 Check if two arrays are equal or not-->>
class Result {
  static int arraysEqualorNot(int[] A, int[] B) {
    // Write your code here
    if(A.length!=B.length){
     return 0;
    }
    HashMap<Integer,Integer> hs = new HashMap<>();
    for(int i=0; i<A.length; i++){
      hs.put(A[i],hs.getOrDefault(A[i],0)+1);
      hs.put(B[i],hs.getOrDefault(B[i],0)-1);
    }
     for(int c: hs.values()){
          if(c!=0){
            return 0;
          }
     }
    return 1;
  }
}

11 Maximum Frequency in a sequence-->>
using namespace std;
int main()
{
   int t;
   cin>>t;
  while(t--){
    int n;
    cin>>n;
    unordered_map<int,int> map;
    int x;
    for(int i=0;i<n;i++){
      cin>>x;
      map[x]++;
    }
    int maximum = INT_MIN;
    for(auto it:map){
      maximum = max(maximum,it.second);
    }
    int min=INT_MAX;
    for(auto it:map){
      if(it.second==maximum){
        if(it.first<min)
          min = it.first;
      }
    }
    cout<<min<<endl;
  }
   return 0;
}

12 Find all pairs with K difference -->>
class Result {
  static int getPairsCount(int arr[], int n, int k) {
// Write your code here
   HashMap<Integer,Integer> map = new HashMap<>();
    int count=0;
    for(int i=0;i<n;i++){
      if(map.containsKey(arr[i]-k)){
        count+=map.get(arr[i]-k);
      }
      if(map.containsKey(arr[i]+k)){
        count+=map.get(arr[i]+k);
      }
      if(map.containsKey(arr[i]))
        map.put(arr[i],map.get(arr[i])+1);
      else
        map.put(arr[i],1);
    }
    return count;
  }
}

13 Insurance Agent with a target-->>
class Result {
  static int totalWays(int members[], int n, int target) {
  // Write your code here  
    int sum=0,count=0;
    HashMap<Integer,Integer> map = new HashMap<>();
  for(int i=0;i<n;i++){
      sum+=members[i];
      if(map.containsKey(sum-target)){
        count+=map.get(sum-target);
      }
      else if(sum==target)
        count+=1;
      if(map.containsKey(sum))
        map.put(sum,map.get(sum)+1);
      else
        map.put(sum,1);
    }
    return count;
  }
}

14 Find all pairs with sum K-->>
class Result {
  static int getPairsCount(int arr[], int n, int k) {
// Write your code here
    int pair = 0;
    HashMap<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<n;i++){
      if(map.containsKey(k-arr[i])){
        pair += map.get(k-arr[i]);
      }
      if(map.containsKey(arr[i])){
        map.put(arr[i],map.get(arr[i])+1);
      }
      else{
        map.put(arr[i],1);
      }
    }
    return pair;
  }
}

15 Find contiguous sub-array with given sum-->>
class Result {
  static void findTheSubArray(int arr[], int n, int sum) {
    // Write your code here
    int[] prefix = new int[n];
    prefix[0] = arr[0];
    boolean done = false;
    for(int i=1;i<n;i++){
      prefix[i] = prefix[i-1] + arr[i];
    }
    HashMap<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<n;i++){
      if(map.containsKey(prefix[i]-sum)){
        System.out.print(map.get(prefix[i]-sum)+1 +" "+i);
        done=true;
        break;
      }
      else if(prefix[i]==sum){
        System.out.print(0 +" "+i);
        done=true;
        break;
      }
      map.put(prefix[i],i);
    }
    if(done==false)
      System.out.print("-1");
  }
}

16 Sort an array using quick sort-->>
class Result {
  /* This function picks an element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right of pivot */
  int partition (int array[], int low, int high) {
int pivot = array[high];
    int j,i=low-1;
    for(j=low;j<high;j++){
      if(array[j]<pivot){
        i++;
        swap(array,i,j);
      }
    }
    i++;
    swap(array,i,high);
    return i;
  }
  void swap(int[] array,int i,int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  /* low is for left index and high is right index of the sub-array of arr to be sorted */
  void quickSort(int array[], int low, int high){
    solve(array,low,high);
    /*for(int i=0;i<array.length;i++)
      System.out.print(array[i]+" ");*/
  }
  void solve(int array[], int low, int high) {
  if(low<high){
      int mid = partition(array,low,high);
      solve(array,low,mid-1);
      solve(array,mid+1,high);
    }
  }
}

17 Gifts for everyone with no bias -->>
public static int pickMGifts(int m, List<Integer> arr) {
    // Write your code here
    Collections.sort(arr);
    int a=0,b=m-1,diff=Integer.MAX_VALUE ;
    while(b<arr.size()){
      diff = Math.min(diff,arr.get(b)-arr.get(a));
      a++;
      b++;
    }
    return diff;
  }
}

18 Kth largest number-->>
static void swap(int[] arr,int i,int j){
  int temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
}
static int partition(int[] arr,int low,int high){
  int pivot=arr[high];
  int j=low;
  for(int i=low;i<high;i++){
    if(arr[i]<pivot){
      swap(arr,i,j);
      j++;
    }
  }
  swap(arr,j,high);
  return j;
}
static int kthLargest(int arr[], int l,int h, int k) {
  int pi=partition(arr,l,h);
  int n=arr.length;
  if(pi==n-k-1)return arr[pi];
  else if(pi>n-k-1){
    return kthLargest(arr,l,pi-1,k);
  }
  else{
    return kthLargest(arr,pi+1,h,k);
  }
}
static int kthLargest(int arr[], int size, int k) {
  return kthLargest(arr,0,arr.length-1,k);
}

19 Sort an array using merge sort -->>
class Result {
  // Merges two subarrays of arr[].
  // First subarray is arr[l..m] and Second subarray is arr[m+1..r]
  void merge(int array[], int l, int m, int r) {
int[] result = new int[r-l+1];
    int index1 = l,index2 = m+1;
    int index = 0;
    while(index1<=m && index2<=r){
      if(array[index1]<array[index2]){
        result[index]=array[index1];
        index1++;
      }
      else{
        result[index]=array[index2];
        index2++;
      }
      index++;
    }
    while(index1<=m){
      result[index]=array[index1];
      index++;
      index1++;
    }
    while(index2<=r){
      result[index]=array[index2];
      index++;
      index2++;
    }
    index=l;
    for(int ele:result){
      array[index++]=ele;
    }
  }
  /* l is for left index and r is right index of the sub-array of arr to be sorted */
  void mergeSort(int array[], int l, int r) {
     if(array.length==1)return;
     if(l<r){
       int mid = l + (r-l)/2;
       mergeSort(array,l,mid);
       mergeSort(array,mid+1,r);
       merge(array,l,mid,r);
     }
  }
}

20 Queries for K largest-->>
class Result {
  static long solveQueries(int N, int arr[], int Q, int queries[]) {
    // Write your code here
Arrays.sort(arr);
    int ans = 0;
    for(int i=0;i<Q;i++){
      ans+=arr[N-queries[i]];
    }
    return ans;
  }
}


21 Implement Priority Queue using Linked List-->>
class PQueueLL
{
  public QueueNode front, rear;
  public void EnQueue(int data, int priority)
  {
    QueueNode node=new QueueNode(data,priority);
    if(front==null){
      front=rear=node;
    }
    else{
      QueueNode temp=front;
      if(priority<temp.priority){
        node.next=front;
        front=node;
      }
      else if(priority>rear.priority){
        rear.next=node;
        rear=node;
      }
      else{
        while(temp.next!=null && temp.next.priority<priority){
          temp=temp.next;
        }
        QueueNode next=temp.next;
        temp.next=node;
        node.next=next;
      }
    }
  }    
  public int DeQueue()
  {
    if(front==null)return -1;
    int data=front.data;
    front=front.next;
    return data;
  }    
}

22 Sort an array using heap sort-->>
import java.util.*;
class Result {
  static void heapify (int array[], int n, int i) {
    if(i>=n)return;
    int lc=2*i+1;
    int rc=2*i+2;
    int largest=i;
    if(lc<n && array[lc]>array[largest]){
      largest=lc;
    }
    if(rc<n && array[rc]>array[largest]){
      largest=rc;
    }
    if(largest!=i){
      swap(array,i,largest);
      heapify(array,n,largest);
    }
  }
  static void swap(int[] arr,int i,int j){
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
  }
  static void heapSort(int array[], int n) {
    //build heap
    for(int i=n/2-1;i>=0;i--){
      heapify(array,n,i);
    }
    //System.out.println(Arrays.toString(array));
    // now one by one pick the element and swap it
    for(int i=n-1;i>=0;i--){
      swap(array,0,i);
      heapify(array,i,0);
    }
  }
}

23. Create a binary tree from array-->>
static Node buildTree(int arr[], int n,int i) {
  if(i>=n)return null;
  Node root=new Node(arr[i]);
  root.leftChild=buildTree(arr,n,(2*i+1));
  root.rightChild=buildTree(arr,n,(2*i+2));
  return root;
}
static Node buildTree(int arr[], int n) {
  Node node = buildTree(arr,n,0);
  return node;
}

24.Print binary tree with level order traversal-->>
static void printLevelWise(Node root) {
  if(root==null)return;
  ArrayDeque<Node> q=new ArrayDeque<>();
  q.add(root);
  while(q.size()>0){
    int size=q.size();
    while(size-->0){
      Node node=q.removeFirst();
      if(size==0) System.out.print(node.data);
      else System.out.print(node.data+" ");
      if(node.left!=null)q.add(node.left);
      if(node.right!=null)q.add(node.right);
    }
    System.out.println();
  }
}

25.Print nodes at odd levels of the binary tree -->>
class Result {
  static void printOdd(Node root) {
if(root==null)return;
    ArrayDeque<Node> q=new ArrayDeque<>();
    q.add(root);
    int lvl=1;
    while(q.size()>0){
      int size=q.size();
      while(size-->0){
        Node node=q.removeFirst();
        if(lvl%2!=0)System.out.print(node.data+" ");
        if(node.left!=null)q.add(node.left);
        if(node.right!=null)q.add(node.right);
      }
      lvl++;
  }
  }
}

26.Write iterative version of inorder traversal -->>
static void printInorder(Node root){
  Stack<Node> st=new Stack<>();
  Node curr=root;
  while(curr!=null || st.size()>0){    
    while(curr!=null){
      st.push(curr);
      curr=curr.leftChild;
    }
    curr=st.pop();
    System.out.print(curr.data+" ");
    curr=curr.rightChild;
  }
}

27. Complete the inorder(), preorder() and postorder()
functions for traversal with recursion -->>

static void inorder(Node root)
{
if(root==null)return;
  inorder(root.leftChild);
  System.out.print(root.data+" ");
  inorder(root.rightChild);
}
static void preorder(Node root)
{
if(root==null)return;
  System.out.print(root.data+" ");
  preorder(root.leftChild);
  preorder(root.rightChild);
}
static void postorder(Node root)
{
if(root==null)return;
  postorder(root.leftChild);
  postorder(root.rightChild);
  System.out.print(root.data+" ");
}

28.Construct tree from given inorder and post order traversal-->>
class Result {
  static Node buildTree(int in[], int post[], int N,int ins,int ine,int ps,int pe) {
if(ins>ine || ps>pe)return null;
    Node root=new Node(post[pe]);
    int idx=-1;
    int count=0;
    for(int i=ins;i<=ine;i++){
      if(post[pe]==in[i]){
        idx=i;
        break;
      }
      count++;
    }
    root.leftChild=buildTree(in,post,N,ins,idx-1,ps,ps+count-1);
    root.rightChild=buildTree(in,post,N,idx+1,ine,ps+count,pe-1);
    return root;
  }
  static Node buildTree(int in[], int post[], int N) {
return buildTree(in,post,N,0,N-1,0,N-1);
  }
}



29 Print all paths to leaves and their details of a binary tree-->>
static int printAllPaths(Node root,int count,String str) {
      if(root==null)return 0;
      if(root.left==null && root.right==null){
        System.out.println(str+root.data+" "+count);
        return 1;
      }
      return printAllPaths(root.left,count+1,str+root.data+" ")+printAllPaths(root.right,count+1,str+root.data+" ");
    }
static void printAllPaths(Node root) {
      if(root==null)return;
      System.out.println(printAllPaths(root,0,""));
    }

30 Find the right node of a given node -->>
class Result {
  static int findRightSibling(Node root, int key) {
    ArrayDeque<Node> q=new ArrayDeque<>();
    q.add(root);
    while(q.size()>0){
      int size=q.size();
      while(size-->0){
        Node node=q.remove();
        if(node.data==key){
          if(size==0)return -1;
          else return q.peek().data;
        }
        if(node.left!=null)q.add(node.left);
        if(node.right!=null)q.add(node.right);
      }
    }
    return -1;
  }
}

31 Given binary tree is binary search tree or not -->>
class Result {
  static boolean flag=true;
  static int[] isBinarySearchTree_(Node root) {
    if(root==null)return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
    int[] arr=new int[2];
    int[] left=isBinarySearchTree_(root.left);
    int[] right=isBinarySearchTree_(root.right);
    if(left[1]<root.data && root.data<right[0]){
      arr[0]=Math.min(Math.min(left[0],right[0]),root.data);
      arr[1]=Math.max(Math.max(left[1],right[1]),root.data);
    }
    else{
      flag=false;
    }
    return arr;
  }
  static int isBinarySearchTree(Node root) {
    isBinarySearchTree_(root);
    return (flag)?1:0;
  }
}

32 Find the kth smallest element in the binary search tree-->>
static int kSmallest(Node root, int k,int[] arr) {
      if(root==null)return -1;
      if(arr[0]==k)return root.data;
      int ans1=kSmallest(root.left,k,arr);
      if(ans1!=-1)return ans1;
      arr[0]++;
      if(arr[0]==k)return root.data;
      int ans2=kSmallest(root.right,k,arr);
      return ans2;
  }
static int kSmallest(Node root, int k) {
      if(root==null)return 0;
      return kSmallest(root,k,new int[1]);
  }


33. Find K largest elements in array -->>
static void printKLargest(int arr[], int n, int k){
// Write your code here
  PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);
  for(int ele : arr){
     pq.add(ele);
  }
  String ans = "";
  for(int i =0;i<k;i++){
    ans += pq.poll()+" ";
  }
  System.out.print(ans.trim());
}

34 Convert min Heap to max Heap -->>
static void modifyMintoMax(int array[], int n)
{
for(int i=(n-2)/2;i>=0;i--)
      maxHeapify(array,i,n);
}
static void maxHeapify(int[] arr,int i,int n){
    int l = 2*i+1;
  int r = 2*i+2;
    int largest = i;
  if(l<n && arr[l]>arr[i])
      largest = l;
  if(r<n && arr[r]>arr[largest])
      largest = r;
  if(largest!=i){
      int temp = arr[i];
      arr[i] = arr[largest];
      arr[largest] = temp;
      maxHeapify(arr,largest,n);
    }
}


35 Connect the sticks of different lengths with minimum cost-->>>
class Result
{
  static int connectCost(int lengths[], int n){
// Write your code here
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int ele : lengths){
      pq.add(ele);
    }
    int cost =0;
    while(!pq.isEmpty()){
      int len1=pq.poll();
      if(pq.isEmpty()){
        return cost;
      }
      int len2 = pq.poll();
      int len3 = len1+len2;
      cost += len3;
      pq.add(len3);
    }
    return cost;
  }
}

36 Find the minimum number of edges in a path of a graph-->
clasFind the minimum number of edges in a path of a graph-->
class Result{
  static int number_of_edges(int n){
    // Write your code here
    if(n==1)
      return 0;
    if(n%3==0)
      return number_of_edges(n/3)+1;
    return number_of_edges(n-1)+1;
  }
}


37 Find path in a directed graph-->
import java.util.*;
class Main{
  public static boolean pathExists(List<List<Integer>> adj,int source,int dest,boolean[] visited){
      Queue<Integer> que = new LinkedList<>();
      que.add(source);
      visited[source] = true;
      while(!que.isEmpty()){
        int v = que.remove();
        for(int i=0;i<adj.get(v).size();i++){
          if(adj.get(v).get(i)==dest)
            return true;
          if(!visited[adj.get(v).get(i)]){
          que.add(adj.get(v).get(i));
          visited[adj.get(v).get(i)]=true;
        }
      }
     }  
      return false;
    }
    public static void main(String[] args)
    {
        // Write your code here
      Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
      int e = sc.nextInt();
      List<List<Integer>> adj_list = new ArrayList<>();
      for(int i=0;i<v;i++)
          adj_list.add(new ArrayList<Integer>());
        for(int i=0;i<e;i++){
          int u=sc.nextInt();
          int ve=sc.nextInt();
          adj_list.get(u).add(ve);
        }
        boolean[] visited = new boolean[v];
      int source = sc.nextInt();
      int dest = sc.nextInt();
      if(source==dest){
          System.out.println("YES");
       return;
        }
      if(pathExists(adj_list,source,dest,visited))
          System.out.println("YES");
      else
          System.out.println("NO");
    }
}


38 number of islands-->
class Result {
  static void dfs(int[][] mat,int m,int n,int i,int j){
    if(i<0 || j<0 || i>=m || j>=n || mat[i][j]==0 || mat[i][j]==-1)
      return;
    mat[i][j] = -1;
    dfs(mat,m,n,i+1,j);
    dfs(mat,m,n,i-1,j);
    dfs(mat,m,n,i,j+1);
    dfs(mat,m,n,i,j-1);
  }
  static int countIslands(int mat[][], int m, int n){
    // Write your code here
    int count=0;
    for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
        if(mat[i][j]!=0 && mat[i][j]!=-1){
          count++;
          dfs(mat,m,n,i,j);
        }
      }
    }
    return count;
  }  
}


39 Shortest path in a binary maze -->
class Result {    
    static int shortestPath(int mat[][], int srcR, int srcC, int destR, int destC, int m, int n){
      // Write your code here
      if(srcR == destR && srcC == destC) return 0;
      if(mat[srcR][srcC] == 0) return -1;
      int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
      int dist = 0;
      mat[srcR][srcC] = -1 ;
      Queue<int[]> qu = new LinkedList<>();
      qu.add(new int[]{srcR, srcC});
      while(!qu.isEmpty()){
        dist++;
        for(int x = qu.size(); x > 0; x--)
        {
          int[] ar = qu.remove();
          for(int[] dir : dirs)
          {
            int i = dir[0] + ar[0], j = dir[1] + ar[1];
            if(i >= 0 && j >= 0 && i < m && j < n && mat[i][j] == 1)
            {
              mat[i][j] = -1;
              if(i == destR && j == destC)
                return dist;
              qu.add(new int[]{i, j});
            }
          }
        }
      }
      return -1;
    }
}


40 Depth first traversal of graph-->
/* The class is defined with below variables
  class Graph
{
  private Map<Integer, List<Integer>> adjVertices;
  public Graph() {
    this.adjVertices = new HashMap<Integer, List<Integer>>();
  }
  public void addVertex(int vertex) {
    adjVertices.putIfAbsent(vertex, new ArrayList<>());
  }
  public void addEdge(int src, int dest) {
    adjVertices.get(src).add(dest);
  } */
void DFSUtil(int v, boolean visited[])
{
visited[v]=true;
    System.out.print(v+" ");
  for(int i=0;i<adjVertices.get(v).size();i++){
      if(!visited[adjVertices.get(v).get(i)]){
        DFSUtil(adjVertices.get(v).get(i),visited);
      }
    }
}
void DFS(int v)
{
boolean[] visited = new boolean[adjVertices.size()];
    DFSUtil(v,visited);
}


41 Breadth first traversal of graph-->
/* The class is defined with below variables
class Graph {
  private int V;
  private Map<Integer, List<Integer>> adjVertices;
  public Graph(int V) {
      this.V = V;
    this.adjVertices = new HashMap<Integer, List<Integer>>();
  }
  public void addVertex(int vertex) {
    adjVertices.putIfAbsent(vertex, new ArrayList<>());
  }
  public void addEdge(int src, int dest) {
    adjVertices.get(src).add(dest);
  } */
void BFS(int v)
{
Queue<Integer> que = new LinkedList<>();
    boolean[] visited = new boolean[adjVertices.size()];
  que.add(v);
  visited[v]=true;
  while(!que.isEmpty()){
      int n = que.remove();
      System.out.print(n+" ");
      for(int i=0;i<adjVertices.get(n).size();i++){
        if(!visited[adjVertices.get(n).get(i)]){
          visited[adjVertices.get(n).get(i)]=true;
          que.add(adjVertices.get(n).get(i));
        }
      }
    }
}


42 Find the cycle in the undirected graph -->
import java.util.*;
class Main{
  public static boolean DFS(int u , ArrayList<ArrayList<Integer>> adj , boolean [] visited,int parent){
        visited[u]=true;
        for(int i=0;i<adj.get(u).size();i++){
            if(!visited[adj.get(u).get(i)]){
                if(DFS(adj.get(u).get(i),adj,visited,u))
                return true;
            }
            else if(adj.get(u).get(i)!=parent)
            return true;
        }
        return false;
    }
    public static boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        // Code here
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
        for (int u = 0; u < V; u++)
        {
            if (!visited[u])
                if (DFS(u, adj,visited, -1))
                    return true;
        }
        return false;
    }
    public static void main(String[] args)
    {
        // Write your code here
      Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
      int e = sc.nextInt();
      ArrayList<ArrayList<Integer>> adj_list = new ArrayList<>();
      for(int i=0;i<v;i++)
          adj_list.add(new ArrayList<Integer>());
        for(int i=0;i<e;i++){
          int u=sc.nextInt();
          int ve=sc.nextInt();
          adj_list.get(u).add(ve);
        }
        boolean[] visited = new boolean[v];
      if(isCycle(v,adj_list)==true){
        System.out.print("Yes");
      }
      else
        System.out.print("No");
    }
}


43 Fractional Knapsack problem -->
class Result
{
    static class Item {
    int weight, value;
    double valuePerUnitWeight;
    Item(int weight, int value) {
      this.weight = weight;
      this.value = value;
      valuePerUnitWeight = (double) (value) / (weight);
    }}
  static double fractionalKnapsack(int val[], int weight[], int n, int capacity)
  {
    List<Item> l= new ArrayList<>();
    for(int i=0; i<n; i++){
      l.add(new Item(weight[i],val[i]));
    }
    Collections.sort(l, new Comparator<Item>() {
        public int compare(Item i1, Item i2) {
          if (i1.valuePerUnitWeight > i2.valuePerUnitWeight) return -1;
          return 1;
        }
      });
    double ans = 0;
    for (int i = 0; i < n; i++) {
      int wt = l.get(i).weight;
      int vl = l.get(i).value;
      double valuePerUnitWeight = l.get(i).valuePerUnitWeight;
      if (capacity >= wt) {
        ans += vl;
        capacity -= wt;
      }
      else {
        ans += valuePerUnitWeight * capacity;
        capacity = 0;
        break;
      }
    }
    return ans;        
  }
}

44 Interval scheduling problem-->
class Result {
  static class Item{
    int start;
    int end;
    Item(int start, int end)
    {
      this.start = start;
      this.end = end;
    }
  }
  static int intervalScheduling(int[] start, int[] end) {
    // Write your code here
    int len = start.length;
    Item arr[] = new Item[len];
    for(int i = 0;i<len;i++)
    {
      arr[i] = new Item(start[i], end[i]);
    }
    Arrays.sort(arr, new Comparator<Item>(){
      @Override
      public int compare(Item ele1, Item ele2)
      {
          return ele1.end - ele2.end;
      }
    });
    int idx = 0;
    int NoOfInterval = 1;
    for(int i = 0;i<len;i++)
    {
      if(arr[idx].end <= arr[i].start)
      {
        NoOfInterval++;
        idx = i;
      }
    }
    return NoOfInterval;
}
}  


45 job Scheduling with deadlines -->
class Result {
  static class Job{
    int profit;
    int deadline;
    Job(int x, int y){
      profit=x;
      deadline=y;
    }
  }
  static int jobScheduling(int[] deadlines, int[] profits) {
 // Write your code here
    List<Job> l = new ArrayList<>();
    for(int i=0; i<deadlines.length; i++){
      l.add(new Job(profits[i],deadlines[i]));
    }
    Collections.sort(l, new Comparator<Job>(){
      public int compare(Job j1, Job j2){
        if(j1.profit>j2.profit) return -1;
        return 1;
      }
    });
    int maxDeadline=0;
   for(int i=0; i<deadlines.length; i++){
  maxDeadline=Math.max(deadlines[i],maxDeadline); }
    int arr[]=new int[maxDeadline];
    Arrays.fill(arr,-1);
    int ans=0;
    for(int i=0; i<l.size(); i++){
      for(int j=l.get(i).deadline-1; j>=0; j--){
        if(arr[j]==-1){
          ans+=l.get(i).profit;
          arr[j]=0;
          break;
        }
      }
    }  
    return ans;
  }
}


46 Activity Selection problem -->
class Result {
    static class act{
    int start, finish;
    act(int start, int finish) {
      this.start = start;
      this.finish = finish;
    }}
  static void activitySelection(int[] start, int[] finish) {
    List<act> l= new ArrayList<>();
    // array list of objects of act class
    for(int i=0; i<start.length; i++){
      l.add(new act(start[i],finish[i]));
    }
    // sorting the list on basis of finish time
    Collections.sort(l, new Comparator<act>(){
      public int compare(act a1, act a2){
        if(a1.finish<a2.finish) return -1;
        return 1;
      }
    });
   // for(int i=0; i<l.size(); i++){
      //System.out.println(l.get(i).start+" "+l.get(i).finish);
    //}
    System.out.print(l.get(0).start+" ");
    int last=l.get(0).finish;
    for(int i=1; i<l.size(); i++){
     if(l.get(i).start>=last){
       System.out.print(l.get(i).start+" ");
       last=l.get(i).finish;
     }
    }
  }
}

47 Count number of ways to cover a distance -->
class Result
{
  static int totalWaysToDistance(int d, int k){
    // Write your code here
    if(d==0)return 1;
    int count = 0;
    for(int j=1;j<=k;j++){
      if(j<=d)
        count+=totalWaysToDistance(d-j,k);
    }
    return count;
  }
}

48 Minimum Cost path to last element of matrix-->
class Result
{
  static int minCostPath(int cost[][], int m, int n){
    // Write your code here
    int[][] dp = new int[m][n];
    for(int i=0;i<m;i++)
      for(int j=0;j<n;j++)
        dp[i][j] = -1;
    return solve(cost,m-1,n-1,m,n,dp);
  }
  static int solve(int[][] cost,int i,int j,int m,int n,int[][] dp){
    if(i<0 || i>=m || j<0 || j>=n)return (int)(1e9);
    if(i==0 && j==0)return cost[0][0];
    if(dp[i][j]!=-1)return dp[i][j];
    int top=0,left=0,diag=0;
    top = solve(cost,i-1,j,m,n,dp);
    left = solve(cost,i,j-1,m,n,dp);
    diag = solve(cost,i-1,j-1,m,n,dp);
    return dp[i][j] = cost[i][j] + Math.min(top,Math.min(left,diag));
  }
}


49 Longest common subsequence-->
class Result
{
  static int lcs(String str1,String str2,int i,int j,int[][] dp){
    if(i==str1.length() || j==str2.length())return 0;
  if(dp[i][j]!=-1)return dp[i][j];
  if(str1.charAt(i)==str2.charAt(j))
    return dp[i][j]=1+lcs(str1,str2,i+1,j+1,dp);
  return dp[i][j] = Math.max(lcs(str1,str2,i,j+1,dp),lcs(str1,str2,i+1,j,dp));
  }
  static int longestCommonSubsequence(String str1, String str2){
    // Write your code here
    int n=str1.length(),m=str2.length();
  int[][] dp = new int[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      dp[i][j]=-1;
    }
  }
  return lcs(str1,str2,0,0,dp);
  }
}


50 The Subset Sum problem-->
class Result
{
  static int subsetSum(int a[], int n, int sum){
// Write your code here
    return isSubsetSum(a,n,sum)==true?1:0;
  }
  static boolean isSubsetSum(int[] a,int n,int sum){
    if(sum==0)
      return true;
    if(n==0)
      return false;
    if(a[n-1]>sum)
      return isSubsetSum(a,n-1,sum);
    return isSubsetSum(a,n-1,sum) || isSubsetSum(a,n-1,sum-a[n-1]);
  }
}


51 Matrix Chain multiplication problem-->
class Result
{
  static int findAns(int i, int j, int arr[], int dp[][])
  {
      //base condition
      if(i == j)
      {
        return 0;
      }
      if(dp[i][j] != 0)
      {
        return dp[i][j];
      }
      int min = Integer.MAX_VALUE;
      for(int k = i; k < j; k++)
      {
          int step = arr[i-1]*arr[k]*arr[j]+findAns(i, k, arr, dp)+findAns(k+1, j, arr, dp);
          min = Math.min(min, step);
      }
      return dp[i][j] = min;
  }
  // Matrix A[i] has dimension p[i-1] x p[i]  for i = 1..n
  static int matrixChainMultiplication(int p[], int n){
    // Write your code here
    int dp[][] = new int[n+1][n+1];
    return findAns(1, n, p, dp);
  }
}

52 0-1 knapsack problem -->
class Result
{
  static int zeroOneKnapsack(int val[], int weight[], int n, int capacity){
    // Write your code here
    int[][] dp = new int[n][capacity+1];
    for(int i=0;i<n;i++){
      for(int j=0;j<=capacity;j++)
        dp[i][j] = -1;
    }
    return solve(val,weight,n,capacity,dp);
  }
  static int solve(int val[], int weight[], int n, int capacity,int[][] dp){
    if(n==0 || capacity==0)return 0;
    if(dp[n-1][capacity]!=-1)
      return dp[n-1][capacity];
    if(weight[n-1]>capacity)
      return solve(val,weight,n-1,capacity,dp);
    return dp[n-1][capacity] = Math.max(val[n-1]+solve(val,weight,n-1,capacity-weight[n-1],dp),solve(val,weight,n-1,capacity,dp));
  }
}

53 Tom And Permutations -->
class Solve {
  ArrayList<String> permute(String str) {
    // Write your code here
    int n = str.length();
    char[] arr = str.toCharArray();
    ArrayList<String> ans = new ArrayList<>();
    computePermutations(arr,0,n,ans);
    return ans;
  }
  void computePermutations(char[] arr,int index,int n,ArrayList<String> ans){
    if(index==n){
      String s="";
      for(char c:arr)
        s+=c;
      ans.add(s);
      return;
    }
    for(int i=index;i<n;i++){
      swap(arr,index,i);
      computePermutations(arr,index+1,n,ans);
      swap(arr,i,index);
    }
  }
  void swap(char[] arr,int i,int j){
    char c = arr[i];
    arr[i] = arr[j];
    arr[j] = c;
  }
}

54 Print all strings of n-bits -->
class Solve
{
    void generateAllStrings(int n, int i, char currStr[], ArrayList<String> strs){
      // Write your code here
      if(i==n){
        String str = new String(currStr);
        strs.add(str);
        return;
      }
      currStr[i]='0';
      generateAllStrings(n,i+1,currStr,strs);
      currStr[i]='1';
      generateAllStrings(n,i+1,currStr,strs);
}
}