Untitled

import 'dart:collection';
import 'dart:io';
import 'dart:math';

// // declaring the node, this is the basic building block of linked list
// class Node<T>{
//   T data;
//   Node<T>? next;
//
//   Node(this.data);
// }
//
// class LinkedList<T>{
//   Node<T>? head;
//
//   //add at end
//
//   void add(T data){
//     final newNode = Node<T>(data);
//
//     if(head == null){
//       head = newNode;
//       return;
//     }
//
//     Node<T>? current = head;
//       while(current!.next != null){
//         current = current.next;
//       }
//
//   }
//
//
//
// }

bool palindrome(int num) {
  int x = num;
  int result = 0;
  while (num > 0) {
    int last = num % 10; // 123 => rem 3
    result = result * 10 + last;
    num = (num ~/ 10);
  }
  print(result);
  if (x == result) {
    return true;
  }
  return false;
}

// bool palindrome(int num) {
//   String x = num.toString();
//   String result = '';
//   for (int i = x.length - 1; i >= 0; i--) {
//     result = result + x[i];
//   }
//   int y = int.parse(result);
//   print(y);
//   if (num == y) {
//     return true;
//   } else {
//     return false;
//   }
// }

void stringSwap(String a, String b) {
  String extra = a;
  a = b;
  b = extra;
  print(a);
  print(b);
}

void starPattern1(int n) {
  for (int i = 0; i < n; i++) {
    for (int k = n - 2; k >= i; k--) {
      stdout.write(' ');
    }
    for (int j = 0; j <= i; j++) {
      stdout.write(' *');
    }
    for (int l = n - 1; l > i; l--) {
      stdout.write(' ');
    }
    for (int k = n - 1; k > i; k--) {
      stdout.write(' ');
    }
    for (int m = 0; m <= i; m++) {
      stdout.write(' *');
    }
    print('');
  }
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= i; j++) {
      stdout.write(' ');
    }
    for (int k = n; k > i; k--) {
      stdout.write(' *');
    }
    for (int l = 1; l <= i; l++) {
      stdout.write('  ');
    }
    for (int m = n; m > i; m--) {
      stdout.write(' *');
    }
    print('');
  }
}

Future<void> starPatternB(int n) async {
  for (int i = 1; i <= n; i++) {
    stdout.write('*');
    for (int k = 2; k <= 2 * i; k++) {
      stdout.write(' ');
    }
    stdout.write('*');

    print('');
    await Future.delayed(Duration(milliseconds: 500));
  }
  for (int i = 1; i <= n; i++) {
    stdout.write('*');
    for (int k = 2 * n; k >= 2 * i; k--) {
      stdout.write(' ');
    }
    stdout.write('*');

    print('');
    await Future.delayed(Duration(milliseconds: 500));
  }
  for (int i = 1; i <= n; i++) {
    stdout.write('*');
    for (int k = 2; k <= 2 * i; k++) {
      stdout.write(' ');
    }
    stdout.write('*');

    print('');
    await Future.delayed(Duration(milliseconds: 500));
  }
  for (int i = 1; i <= n; i++) {
    stdout.write('*');
    for (int k = 2 * n; k >= 2 * i; k--) {
      stdout.write(' ');
    }
    stdout.write('*');

    print('');
    await Future.delayed(Duration(milliseconds: 50));
  }
}

int fib(int n) {
  if (n == 0) {
    return 0;
  } else if (n == 1) {
    // print()
    return 1;
  }
  return fib(n - 2) + fib(n - 1);
}

int fact(int n) {
  if (n < 1) {
    return 1;
  }
  return n * fact(n - 1);
}

bool primeNum(int num) {
  int count = 0;
  for (int i = 2; i * i <= num; i++) {
    if (num % i == 0) {
      return false;
    }
    count = count + 1;
  }
  print(count);

  return true;
}

// void subSet(String str){
//   num seq = pow(2, str.length);
//   List<String> result = [];
//   print(seq);
//   for(int i = 1; i<=seq; i++){
//     result.add(str.char)
//   }
// }

// List<String> findSubsets(String str) {
//   int n = str.length;
//   int totalSubsets = 1 << n; // 2^n
//   List<String> result = [];
//
//   for (int mask = 0; mask < totalSubsets; mask++) { // 0, 1, 2, 3, 4, 5
//     String subset = "";
//
//     for (int i = 0; i < n; i++) { // 0 1 2
//       if ((mask & (1 << i)) != 0) {
//         subset += str[i];
//       }
//
//     }
//
//     result.add(subset.isEmpty ? "0" : subset);
//   }
//
//   return result;
// }

List<String> findSubsetsRecursive(String str) {
  List<String> result = [];

  void helper(int index, String current) {
    if (index == str.length) {
      result.add(current.isEmpty ? "0" : current);
      return;
    }
    helper(index + 1, current);
    helper(index + 1, current + str[index]);
  }

  helper(0, '');
  return result;
}

int fact2(int num) {
  int sum = 1;
  for (int i = num; i >= 1; i--) {
    sum = sum * i;
  }
  return sum;
}

int findGCD(int n1, int n2) {
  int x = n1 < n2 ? n1 : n2;
  int gcd = 1;
  for (int i = 1; i <= x; i++) {
    if (n1 % i == 0 && n2 % i == 0) {
      gcd = i;
    }
  }
  return gcd;
}

int octalToDecimal(int num) {
  int x = num ~/ 10;
  return num - (x * 2);
}

int octalToDecimal2(int oct) {
  int x = oct;
  num result = 0;
  int i = 0;
  while (x > 0) {
    int rem = x % 10;
    result = result + rem * (pow(8, i));
    x = x ~/ 10;
    i++;
  }
  return result.toInt();
}

List<int> largestKNums(List<int> arr, int k) {
  List<int> result = [];
  for (int i = 1; i <= k; i++) {
    int x = helperFindLargest(arr);
    result.add(x);
    arr.remove(x);
  }
  result.sort((a, b) => a < b ? 1 : -1);
  return result;
}

int helperFindLargest(List<int> arr) {
  int largest = 0;
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] > largest) {
      largest = arr[i];
    }
  }
  return largest;
}

String helperCommonPrefixBTW(String str1, String str2) {
  String result = '';
  int index = 0;
  int min = str1.length > str2.length ? str2.length : str1.length;
  while (index < min) {
    if (str1[index] == str2[index]) {
      result = result + str1[index];
    } else {
      result = '';
    }
    index++;
  }
  return result;
}

//
// String longestSubstring(List<String> arr){ //['flower', 'flow', 'flee']
//   List<String> result = [];
//
//   for(int i= 0; i< arr.length; i++) {
//     if(i==0){
//       result.addAll(helperCommonBTW(arr[i], arr[i + 1]));
//     }else{
//       List<String> temp = [];
//       for(int j = 0 ; j < result.length ; j++){
//         temp.addAll(helperCommonBTW(arr[i], result[j]));
//       }
//       result = result.where((element) => temp.contains(element)).toList();
//     }
//   }
//   result.sort((a, b) => b.length.compareTo(a.length));
//   return result.isEmpty ? 'No one matched' : result.first;
// }
//
// List<String> helperCommonBTW(String str1, String str2){ //['flowering', 'floaaer', 'floer','fasloer']
//   List<String> result =[];
//   int a = 0;
//   for(int i = 0; i<str1.length; i++){
//     int b = 0;
//     for(int j =0; j< str2.length; j++){
//       if(str1[a] == str2[b]){
//         int pointer1 = a;
//         int pointer2 = b;
//
//         String common = '';
//
//         while(pointer1 < str1.length && pointer2 < str2.length && str1[pointer1] == str2[pointer2]){
//           common += str1[pointer1];
//           pointer1++;
//           pointer2++;
//         }
//         result.add(common);
//       }
//       b++;
//     }
//     a++;
//   }
//   return result.toSet().toList();
// }

class Node {
  int data;
  Node? left;
  Node? right;

  Node(this.data);
}

void inOrder(Node? root) {
  if (root == null) return;

  inOrder(root.left);
  print(root.data);
  inOrder(root.right);
}

void preOrder(Node? root) {
  if (root == null) {
    return;
  }
  print(root.data);
  preOrder(root.left);
  preOrder(root.right);
}

void postOrder(Node? root) {
  if (root == null) return;
  postOrder(root.left);
  postOrder(root.right);
  print(root.data);
}

int climbStairs(int n) {
if(n==0) return 1;
if(n==1) return 1;
return climbStairs(n-1) + climbStairs(n-2);
}

int climbStairs2(int n) {
  if(n==1) return 1;
  if(n==2) return 2;
int first = 1;
int second = 2;
int sum  = 0;
for(int i =3; i<=n; i++){
  sum = first + second;
  first = second;
  second = sum;
}
return sum;
}

int height(Node? root){
if(root == null) return 0;

int leftHeight = height(root.left);
int rightHeight = height(root.right);
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

Node insert(Node? root, int value) {
  if (root == null) {
    return Node(value);
  }
  if (value < root.data) {
    root.left = insert(root.left, value);
  } else {
    root.right = insert(root.right, value);
  }
  return root;
}

bool search(Node? root, int key) {
  if (root == null) {
    return false;
  }
  if (root.data == key) {
    return true;
  }
  if (key < root.data) {
    return search(root.left, key);
  } else {
    return search(root.right, key);
  }
}

void deleteTree(Node? root) {
  if (root == null) return;
  deleteTree(root.left);
  deleteTree(root.right);
  print('deleting ${root.data}');
  root = null;
}

String longestSubstring(List<String> arr) {
  if (arr.length < 2) return 'No one matched';

  Set<String> common = helperCommonBTW(arr[0], arr[1]).toSet();

  for (int i = 2; i < arr.length; i++) {
    Set<String> nextCommon = {};

    for (String sub in common) {
      if (arr[i].contains(sub)) {
        nextCommon.add(sub);
      }
    }

    common = nextCommon;

    if (common.isEmpty) break;
  }

  if (common.isEmpty) return 'No one matched';

  List<String> sorted = common.toList()
    ..sort((a, b) => b.length.compareTo(a.length));

  return sorted.first;
}

Set<String> helperCommonBTW(String s1, String s2) {
  Set<String> res = {};

  for (int i = 0; i < s1.length; i++) {
    for (int j = 0; j < s2.length; j++) {
      int p1 = i, p2 = j;
      String temp = '';

      while (p1 < s1.length && p2 < s2.length && s1[p1] == s2[p2]) {
        temp += s1[p1];
        p1++;
        p2++;
      }

      if (temp.isNotEmpty) {
        res.add(temp);
      }
    }
  }
  return res;
}

int test(List<int> arr) {
  //for in

  // for(var e in arr){
  //   if(e == 2){
  //     return 1;
  //   }else {
  //     return 0;
  //   }
  // }

  arr.forEach(stdout.writeln);

  return -1;
}

bool palinString(String str) {
  String rev = "";
  for (int i = str.length - 1; i >= 0; i--) {
    rev = rev + str[i];
  }
  return (str == rev);
}

void main() {
  // print(palindrome(-12321));
  // stringSwap('Amit', 'Rahul');
  // String a = 'Amit';
  // String b = 'Rahul';
  // (a, b) = (b,a);
  // print(a);
  // print(b);
  //   starPattern1(5);
  //   starPatternB(5);
  // for(int i =0; i<10; i++){
  //   print(fib(i));
  // }
  // print(fact(5));
  // int first = 0;
  // int second = 1;
  //
  // print(first);
  // print(second);
  // for(int i =2; i<10; i++){
  //   int result = first + second;
  //   print(result);
  //   first = second;
  //   second = result;
  // }
  // print( fact2(5));

  // List<int>

  // print(findSubsetsRecursive('abc'));
  // print(octalToDecimal(17));
  // longestSubstringPrefix(['flower', 'flow', 'float', 'flea']); //, 'flight'

  // print(longestSubstring(['flowerset', 'flow', 'flower', 'fl']));
  // print(largestKNums([2,56,7,91,28,37], 3));
  // print(helperCommonBTW('selmon', 'selow'));
  // print(test([2,3,4,5]));
  // starPattern1(10);

  // Node root = Node(10);
  // root.left = Node(20);
  // root.right = Node(30);
  // root.left!.left = Node(40);
  // root.left!.right = Node(50);

  // inOrder(root);
  //
  // Node? root;
  // root = insert(root, 20);
  // root = insert(root, 10);
  // root = insert(root, 30);
  //
  // inOrder(root);

  // Node? root;
  // List<int> values = [20, 10, 30, 5, 15];
  //
  // for (int v in values) {
  //   root = insert(root, v);
  // }
  //
  // print('InOrder --->');
  // inOrder(root);
  // print('PreOrder --->');
  // preOrder(root);
  // print('PostOrder --->');
  // postOrder(root);
  //
  // print(search(root, 6));
  // print(search(root, 15));
  // deleteTree(root);

  // print(climbStairs2(1));
  //Input: root = [3,9,20,null,null,15,7]
  // Output: 3

  // Node root = [3,9,20,15,7] ;

  Queue<int> s = Queue();

  List<dynamic> names = <dynamic>[];
  names.addAll(['Seth', 'Kathy', 'Lars']);
  names.add(42);

  Node root = Node(3);
  root.left = Node(9);
  root.right = Node(20);
  root.right!.left = Node(15);
  root.right!.right = Node(7);
  root.right!.right!.right = Node(10);
  root.right!.right!.left = Node(6);

  print(height(root));
}