2️CoderByte

Tree Constructor

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

string TreeConstructor(string strArr[], int arrLength) {
  
   // code goes here
  unordered_map<int, int> parents;
  unordered_map<int, int> children;

  int cnt_no_parent = 0;

  for(int i=0; i<arrLength; i++){
    string str = strArr[i];
    int child = str[1]-'0', parent = str[3]-'0';

    if(parents.find(child) == parents.end()){
      parents[child] = 1;
    } else {
      parents[child] += 1;
    }
    
    if(children.find(parent) == children.end()){
      children[parent] = 1;
    } else {
      children[parent] += 1;
    }
  }


    for(auto item : parents){
      if(item.second>1) return "false";
    }
    
    for(auto item : children){
      if(item.second>2) return "false";
      if(parents[item.first] == 0) cnt_no_parent += 1;

      if(cnt_no_parent>1) return "false";
    }

  // code goes here  
  return "true";

}

int main(void) { 
   
  // keep this function call here
  string A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << TreeConstructor(A, arrLength);
  return 0;
    
}

Maximum Subarray

#include <iostream>
#include <string>
using namespace std;

int MaxSubarray(int arr[], int arrLength) {
  int maxSum = arr[0];
  int curSum = 0;
  for(int i=0; i<arrLength; i++){
    if(curSum < 0) curSum = 0;
    curSum += arr[i];
    maxSum = max(maxSum, curSum);
  }
  // code goes here  
  return maxSum;

}

int main(void) { 
   
  // keep this function call here
  int A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << MaxSubarray(A, arrLength);
  return 0;
    
}

Powers of Two

#include <iostream>
#include <string>
using namespace std;

string PowersofTwo(int num) {
  
  // code goes here  
  return num > 0 && (num & (num - 1)) ==0? "true" : "false";

}

int main(void) { 
   
  // keep this function call here
  cout << PowersofTwo(coderbyteInternalStdinFunction(stdin));
  return 0;
    
}

Additive Persistence

#include <iostream>
#include <string>
using namespace std;

int AdditivePersistence(int num) {
  int cnt = 0;
  int sum = 0;
  // code goes here  
  if(num < 10) return 0;

while(1){

  while(num>=10){
    sum += num%10;
    num /= 10;
  }
  sum += num;
  cnt += 1;
  if(sum<10) break;
  
  num = sum;
  sum = 0;
}

  return cnt;

}

int main(void) { 
   
  // keep this function call here
  cout << AdditivePersistence(coderbyteInternalStdinFunction(stdin));
  return 0;
    
}

Other Products

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string OtherProducts(int arr[], int arrLength) {
  vector<int> prefix(arrLength, 1);
  vector<int> suffix(arrLength, 1);
  string ans="";

  for(int i=1; i< arrLength; i++){
    prefix[i] = prefix[i-1]*arr[i-1];
    suffix[arrLength-i-1] = arr[arrLength-i]*suffix[arrLength-i];
    
  }

  for(int i=0; i< arrLength-1; i++){
    ans += to_string(prefix[i]*suffix[i]);
    ans +="-"; 
  }
  ans += to_string(prefix[arrLength-1]*suffix[arrLength-1]);

  // code goes here  
  return ans;

}

int main(void) { 
   
  // keep this function call here
  int A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << OtherProducts(A, arrLength);
  return 0;
    
}

Wave Sorting

string  WaveSorting(int arr[], int arrLength) {
  vector<int> v;

  for (int i = 0; i<arrLength; i++) v.push_back(arr[i]);

  sort(v.begin(), v.end());

  int mid = arrLength / 2;

  for (int i = 0; i<mid; i++)
    if (v[i] >= v[mid + i]) return "false";

  return "true";

}

Two Sum

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

string TwoSum(int arr[], int arrLength) {
  unordered_set<int> record;
  string str="";
  int target = arr[0];

  for(int i=1; i<arrLength; i++){
    int diff = target - arr[i];
    if(record.find(arr[i]) == record.end()){
      record.insert(diff);
    } else {
      str += to_string(diff) + "," + to_string(arr[i]) + " ";
    }
  }

  if(str.empty()){
    return "-1";
  } else{
    str.erase(str.end()-1);
    return str;
  }
  
  // code goes here  

}

int main(void) { 
   
  // keep this function call here
  int A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << TwoSum(A, arrLength);
  return 0;
    
}

Correct Path

#include <iostream>
#include <string>
using namespace std;

string CorrectPath(string str, bool traveled[5][5], int startx, int starty, int move) {
    //cout<<"Path: "<< str << " length: " << str.length() << " x: " << startx << " y: "<< starty << " move: " << move <<endl;
    if(startx==4&&starty==4&&move==(str.length())){
        //cout<<"found it"<<endl;
        return str;
    }
    if(move>=str.length()||startx>4||starty>4||startx<0||starty<0){
        //cout<<"Out of bounds"<<endl;
        return "";
    }
    /*if(traveled[startx][starty]){
        cout<<"Already visited"<<endl;
        return "";
    }*/
    traveled[startx][starty] = true;
    if(str[move]=='?'){
        string str1 = str;
        string str2 = str;
        string str3 = str;
        string str4 = str;
        str1[move]='r';
        str2[move]='d';
        str3[move]='u';
        str4[move]='l';
        str1=CorrectPath(str1,traveled,startx+1,starty,move+1);
        str2=CorrectPath(str2,traveled,startx,starty+1,move+1);
        str3=CorrectPath(str3,traveled,startx,starty-1,move+1);
        str4=CorrectPath(str4,traveled,startx-1,starty,move+1);
        if(str1!=""){
            //cout<<"Right move worked"<<endl;
            return str1;
        }else if(str2!=""){
            //cout<<"down move worked"<<endl;
            return str2;
        }else if(str3!=""){
            //cout<<"up move worked"<<endl;
            return str3;
        }else if(str4!=""){
            //cout<<"left move worked"<<endl;
            return str4;
        }else{
            //cout<<"no move worked"<<endl;
            return "";
        }
    }else{
        if(str[move]=='r'){
            //cout<<"Move right"<<endl;
             return CorrectPath(str,traveled,startx+1,starty,move+1);
        }else if(str[move]=='l'){
            //cout<<"Move left"<<endl;
            return CorrectPath(str,traveled,startx-1,starty,move+1);
        }else if(str[move]=='u'){
            //cout<<"Move up"<<endl;
            return CorrectPath(str,traveled,startx,starty-1,move+1);
        }else{
            //cout<<"Move down"<<endl;
            return CorrectPath(str,traveled,startx,starty+1,move+1);
        }
    }
}

int main() { 
    bool traveled[5][5] = { {false} };
  
  // keep this function call here
  cout << CorrectPath(gets(stdin),traveled,0,0,0);
  return 0;
    
}

Array Addition

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

string ArrayAddition(int arr[], int arrLength) {
  vector<int> v;
  for(int i=0; i<arrLength; i++){
    v.push_back(arr[i]);
  }  
  sort(v.begin(), v.end());
  int target = v.back();
  v.pop_back();
  int N = v.size(); //number of elements remaining

  unordered_set<int> record;

  for(int mask=0; mask < (1<<N); mask++){
    int val = 0;

     for(int j=0; j < N; j++){
       // check each number
       if(mask & (1<<j)) {
         val += v[j];
       }

     }

     if(record.find(val) == record.end()){
       record.insert(val);
     }
  }


  // code goes here  
  return (record.find(target) != record.end())? "true": "false";

}

int main(void) { 
   
  // keep this function call here
  int A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << ArrayAddition(A, arrLength);
  return 0;
    
}

K Unique Characters

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

int checkUniqueChar(string str){
  int cnt =0;
  unordered_set<char> set;

  for(char ch : str){
    if (set.find(ch) == set.end()){
      set.insert(ch);
      cnt ++;
    }
  }
  return cnt;
}

string KUniqueCharacters(string str) {
  
  int N = str[0] - '0';
  str = str.substr(1);
  
  //cout<< "str: " << str << " window: "<< N << endl;

  unordered_map<int, string> record;
  int maxLen = 0;

  for(int i=0; i<str.length(); i++){
    for(int j=str.length()-1; j>=i+1; j--){

      if(checkUniqueChar(str.substr(i, j -i +1)) == N){
        int len = j - i + 1;
        if(record.find(len) == record.end()){
          record[len] = str.substr(i, j - i +1);
        }
        maxLen = max(maxLen, len);
        //cout<< "N: " << checkUniqueChar(str.substr(i, j - i+1)) << " maxLen: " << maxLen << " len: "<< len << " i: "<< i << " j: " << j << endl;
        break;
      }
    }
  }
  // code goes here  
  return record[maxLen];

}

int main(void) { 
   
  // keep this function call here
  cout << KUniqueCharacters(coderbyteInternalStdinFunction(stdin));
  return 0;
    
}

Symmetric Tree

#include <iostream>
#include <string>
using namespace std;

#define LEFT(x) (x+1)*2-1
#define RIGHT(x) (x+1)*2
#define PARENT(x) (x-1)/2

bool dfs(string tree[], int size, int il, int ir){
    if(il >= size && ir >= size) return true;

    string l = (il < size)? tree[il]: "#";
    string r = (ir < size)? tree[ir]: "#";

    if(l != r) return false;
    
    return dfs(tree, size, LEFT(il), RIGHT(ir)) && dfs(tree, size, RIGHT(il), LEFT(ir));
}

string SymmetricTree(string strArr[], int arrLength) {
  if(arrLength < 2) return "true";

  return dfs(strArr, arrLength, 1, 2)? "true" : "false";

}

int main(void) { 
   
  // keep this function call here
  string A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << SymmetricTree(A, arrLength);
  return 0;
    
}

Binary Search Tree LCA

#include <iostream>
#include <string.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

struct Node {
    int value;
    Node *parent = nullptr;
    Node *leftChild = nullptr;
    Node *rightChild = nullptr;
};

Node* findClosestParentOf(Node* n1, Node* n2) {
    vector<int> ancestVals;
    for (n1 = n1; n1 != nullptr; n1 = n1->parent) {
        ancestVals.push_back(n1->value);
    }

    for (n2 = n2; n2 != nullptr; n2 = n2->parent) {
        if (find(ancestVals.begin(), ancestVals.end(), n2->value) != ancestVals.end()) return n2;
    }

    cout << "Cannot Find Parent";
    return nullptr;
}

Node* searchNodeOf(Node* tree, int val) {
    static Node* nodeFound = nullptr;
    if(tree->value == val) {
        nodeFound = tree;
        return nodeFound;
    }
    else {
        if (nodeFound == nullptr && tree->leftChild != nullptr) searchNodeOf(tree->leftChild, val);
        if (nodeFound == nullptr && tree->rightChild != nullptr) searchNodeOf(tree->rightChild, val);
        
        if (nodeFound != nullptr) {
            if (tree->parent == nullptr) {
                tree = nodeFound;
                nodeFound = nullptr;
                return tree;
            }
            return nodeFound;
        }
        else return tree;
    }
    
    cout << "Failed to find Node";
    return nullptr;
}

Node* createNode (Node *_parent, int _value) {
    Node *node = new Node;
    node->parent = _parent;
    node->value = _value;

    return node;
}

Node* buildTree(Node *&parent, vector<int> &values) {
    static int pos = 1;
    for (pos = pos; pos < values.size(); pos++) {
        if (values[pos] < parent->value) {
            if (parent->leftChild == nullptr) parent->leftChild = createNode(parent, values[pos]);
            else buildTree(parent->leftChild, values);
        }
        else {
            if (parent->rightChild == nullptr) parent->rightChild = createNode(parent, values[pos]);
            else buildTree(parent->rightChild, values);
        }
        if (parent->parent != nullptr) return parent;
    }
    return parent;
}

Node* buildTree(vector<int> values) {   //Build Base
    Node *base = createNode(nullptr, values[0]);

    return buildTree(base, values);
}

vector<int> stringToInt(string &str) {
    vector<int> vec;
    for (char* pch = strtok((char*)str.c_str(), "[ ,]"); pch != NULL; pch = strtok(NULL, "[ ,]")) {
        vec.push_back(stoi(pch));
    }
    

    return vec;
}

int BinarySearchTreeLCA(string strArr[], int length) { 
    vector<int> values = stringToInt(strArr[0]);
    Node *tree = buildTree(values);

    Node* n1 = searchNodeOf(tree, stoi(strArr[1]));
    Node* n2 = searchNodeOf(tree, stoi(strArr[2]));
    return findClosestParentOf(n1, n2)->value;
}

int main(void) { 
   
  // keep this function call here
  string A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << BinarySearchTreeLCA(A, arrLength);
  return 0;
    
}

LRU Cache

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string LRUCache(string strArr[], int arrLength) {
  vector<char> cache;
  string ans="";
  for(int i=0; i<arrLength; i++){
    char ch = strArr[i][0];

    auto it = find(cache.begin(), cache.end(), ch);
    if(it!=cache.end()){
      rotate(it, it+1, cache.end());
    } else {
        if(cache.size() == 5) cache.erase(cache.begin());
        cache.push_back(ch);
    }
  }

  for(char ch: cache){
    ans += ch;
    ans += '-';
  }
   ans.pop_back();

  // code goes here  
  return ans;

}

int main(void) { 
   
  // keep this function call here
  string A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << LRUCache(A, arrLength);
  return 0;
    
}

Min Window Substring

#include <iostream>
#include <string>
#include <unordered_map>
#include <limits.h>

using namespace std;

string MinWindowSubstring(string strArr[], int arrLength) {
  string s = strArr[0], t = strArr[1];

  unordered_map<char, int> map;
  for(int i=0; i<t.size(); i++){
    map[t[i]] ++;
  }

  int counter = t.size();
  int left = 0, right = 0;
  int minStart = 0;
  int minLength = INT_MAX;

  while (right < s.size()){
    if(map[s[right]] > 0){
      counter --;
    }

    map[s[right]] --;
    right ++;

    while(counter ==0){
      if(right - left < minLength) {
        minStart = left;
        minLength = right - left;
      }

      map[s[left]] ++;
      if(map[s[left]] > 0) {
        counter ++;
      }

      left ++;
    }

  }

  return minLength < INT_MAX? s.substr(minStart, minLength) : "";

}

int main(void) { 
   
  // keep this function call here
  string A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << MinWindowSubstring(A, arrLength);
  return 0;
    
}

Longest Increasing Sequence

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int LongestIncreasingSequence(int arr[], int arrLength) {
  vector<int> dp(arrLength, 1);
  int result = 1;
  for(int i=1; i<arrLength; i ++) {
    for (int j=0; j < i; j++) {
      if(arr[j] < arr[i]) {
        dp[i] = max(dp[i], dp[j] + 1);
      }
      result = max(result, dp[i]);
    }
  }
  // code goes here  
  return result;

}

int main(void) { 
   
  // keep this function call here
  int A[] = coderbyteInternalStdinFunction(stdin);
  int arrLength = sizeof(A) / sizeof(*A);
  cout << LongestIncreasingSequence(A, arrLength);
  return 0;
    
}