3/02/2018

Day 23 BST Level Order Traversal HackerRank Solution In C++

Problem:- Day 23 BST Level-Order Traversal hackerRank or Hackerrank: Day 23: BST Level-Order Traversal or binary search tree insertion hackerrank solution or Day 23 BST(binary search tree) Level order traversal hackerrank solution or hackerrank Day 23 BST(binary search tree) Level order traversal solution or hackerrank solution Day 23 BST(binary search tree) Level order traversal solution or hackerrank Day 23 BST Level order traversal solution or hackerrank solution BST Level order traversal solution or hackerrank solution binary search tree Level order traversal solution or (bst) binary search tree Level order traversal solution or hackerrank binary search tree Level order traversal solution.

1. What is a binary search tree(BST)?
2. Binary search tree time complexity

Now explain both queries with a full explanation. so let's see what is Binary Search Tree(BST).

1. What is a Binary Search Tree(BST)

Binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.).

binary search tree
credit: Wikipedia

Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, on the basis of the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree.

2. Binary search tree time complexity

Algorithm Average     Worst case
Space O(n)         O(n)
Search O(log n)         O(n)
Insert O(log n)         O(n)
Delete O(log n)         O(n)

Read complete article on Wikipedia

Task:- A level-order traversal, also known as a breadth-first search, visits each level of a tree's nodes from left to right, top to bottom. You are given a pointer root pointing to the root of a binary search tree. Complete the levelOrder function provided in your editor so that it prints the level-order traversal of the binary search tree.

Hint: You'll find a queue helpful in completing this challenge.

Input Format

  • The locked stub code in your editor reads the following inputs and assembles them into a BST:
  • The first line contains an integer, T (the number of test cases). 
  • The T subsequent lines each contain an integer, data, denoting the value of an element that must be added to the BST.


Output Format

Print the data value of each node in the tree's level-order traversal as a single line of N space-separated integers.

Sample Input

6
3
5
4
7
2
1

Sample Output

3 2 5 1 4 7

Explanation

The input forms the following binary search tree:

Binary search tree example
image Credit:- HackerRank

We traverse each level of the tree from the root downward, and we process the nodes at each level from left to right. The resulting level-order traversal is 3-->2-->5-->1-->4-->7, and we print these data values as a single line of space-separated integers.

Copy the colored code and paste it into Hacker rank editor and click to submit button, but before this process, you have to click the below link, this link takes to you same problem Now you have to just Login if you are already not log in and done. 

Submit this solution:- Click Here

Solution:-

#include <iostream>
#include <cstddef>
#include <queue>
#include <string>
#include <cstdlib>

using namespace std;
class Node{
    public:
        int data;
        Node *left,*right;
        Node(int d){
            data=d;
            left=right=NULL;
        }
};
class Solution{
    public:
  Node* insert(Node* root, int data){
            if(root==NULL){
                return new Node(data);
            }
            else{
                Node* cur;
                if(data<=root->data){
                    cur=insert(root->left,data);
                    root->left=cur;
                }
                else{
                   cur=insert(root->right,data);
                   root->right=cur;
                 }           
           return root;
           }
        }
       
    
  void levelOrder(Node * root){
    queue<Node *> q;
    Node* n = root;
   
    while(n != NULL){
        cout << n->data << ' ';
        
        if( n->left  != NULL ) q.push(n->left);
        if( n->right != NULL ) q.push(n->right);

        if( !q.empty() ) {
        n = q.front();
        q.pop();
        } else {
        n = NULL;
        }
    }
}


};//End of Solution
int main(){
    Solution myTree;
    Node* root=NULL;
    int T,data;
    cin>>T;
    while(T-->0){
        cin>>data;
        root= myTree.insert(root,data);
    }
    myTree.levelOrder(root);
    return 0;
}

Output:-

Binary search Tree Level Order Traversal HackerRank Solution Output


You May Also Check

1. Day 24: More Linked Lists

2. Day 25: Running Time and Complexity

3. Day 26: Nested Logic

4. Day 27: Testing

5. Day 28: RegEx, Patterns, and Intro to Databases
Read More »

3/01/2018

Day 21 Generics HackerRank Solution In C++

Problem:- Day 21 Generics hacker rank solution or HackerRank-30-Days-of-Code/Day 21 Generics or Day 21 Generics/HackerRank-30-Days-of-Code or Day 21 Generics 30 Days of Code solution or Generics HackerRank solution in c or HackerRank Generics solution in c or Generics solution hacker rank or Generics solution hacker rank in c++ or Generics solution in c++ hacker rank or Day 21: Generics | HACKER RANK SOLUTIONS or Hackerrank Day 21: Generics.

Task:- Write a single generic function named printArray; this function must take an array of generic elements as a parameter (the exception to this is C++, which takes a vector). The locked Solution class in your editor tests your function.

Note: You must use generics to solve this challenge. Do not write overloaded functions.

Input Format

The locked Solution class in your editor will pass different types of arrays to your printArray function.

Constraints

You must have exactly 1 function named printArray.

Output Format

Your printArray function should print each element of its generic array parameter on a new line.

Explanation:- We have to just print the generic array, we can do this by using the AUTO keyword in our program. I didn't understand why people don't use AUTO Keyword in C++. as you can see that generic array means all type of data type in an array so for that this is a best practice to use the AUTO keyword in the problem.

Copy the colored code and paste it into Hacker rank editor and click to submit button, but before this process, you have to click the below link, this link takes to you same problem Now you have to just Login if you are already not log in and done. 

Submit this solution:- Click Here

Solution:-

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

using namespace std;

template <class T> 
    void printArray(vector<T> i) 

    for(int j=0;j<i.size();j++) 
        cout<<i[j]<<endl;



void printArray(vector<auto> a)
{
    for(auto i:a)
        cout<<i<<endl;
}


int main() {
int n;

cin >> n;
vector<int> int_vector(n);
for (int i = 0; i < n; i++) {
int value;
cin >> value;
int_vector[i] = value;
}

cin >> n;
vector<string> string_vector(n);
for (int i = 0; i < n; i++) {
string value;
cin >> value;
string_vector[i] = value;
}

printArray<int>(int_vector);
printArray<string>(string_vector);

return 0;
}

Output:-

Day 21 Generics HackerRank Solution output


You May Also See

1. Day 22: Binary Search Trees

2. Day 23: BST Level-Order Traversal

3. Day 24: More Linked Lists

4. Day 25: Running Time and Complexity

5. Day 26: Nested Logic
Read More »

2/28/2018

Day 25 Running Time and Complexity Hacker Rank Solution In C++

Problem:- Day 25 Running Time and Complexity hackerrank or HR-30-days-of-code/day25-Running Time and Complexity or running time and complexity hackerrank solution in c++ or running time and complexity solution or day 25 hackerrank solution or day 25 solution in c++ or hackerrank day 25 solution in c or hackerrank Day 25 Running Time and Complexity solution or hackerrank Running Time and Complexity solution

Task:- A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given a number,n, determine and print whether it's Prime or Not Prime.

Note: If possible, try to come up with a 0(square root(n)) primality algorithm, or see what sort of optimizations you come up with for an O(n) algorithm. Be sure to check out the Editorial after submitting your code!

Input Format

The first line contains an integer, T, the number of test cases. 
Each of the T subsequent lines contains an integer,n, to be tested for primality.

Output Format

For each test case, print whether n is Prime or Not Prime on a new line.

Sample Input

3
12
5
7

Sample Output

Not prime
Prime
Prime
Explanation

Test Case 0: n = 12.

12 is divisible by numbers other than 1 and itself (i.e.: 2, 3, 6 ), so we print Not Prime on a new line.

Test Case 1: n = 5.

5 is only divisible 1 and itself, so we print Prime on a new line.

Test Case 2: n = 7.

7 is only divisible 1 and itself, so we print Prime on a new line.

Submit this solution:- Click Here

Solution:-

#include <bits/stdc++.h>
using namespace std;

bool primeornot(int );

int main() 
{
    int n, i;
    bool f;
    cin >> n;
    
    vector<int> arr(n);
    for(i = 0; i < n; ++i)
    {
        cin >> arr[i];
        bool f = primeornot(arr[i]);
        
        if(f)
        {
            cout<<"Prime"<<endl;
        }
        else
        {
            cout<<"Not prime"<<endl;
        }
    }    
    return 0;
}

bool primeornot(int n)
{
    int i ,sqr;
    if(n == 1)
    {
        return false;
    }
    if(n == 2)
    {
        return true;
    }
    sqr = sqrt(n);
    for(i = 2; i <= sqr; ++i )
    {
        if(n % i == 0)
        {
            return false;
        }
    }
    return true;
        
}

Output:-

Running Time and Complexity Solution In C++

You May Also See

1. Day 26: Nested Logic

2. Day 27: Testing

3. Day 28: RegEx, Patterns, and Intro to Databases

4. Day 29: Bitwise AND

5. Day 0: Hello, World.
Read More »

2/27/2018

Day 27: Testing Hacker Rank Solution In C++

Problem:- day 27: testing java or day 27: testing c++ or day 27: testing c++ or hacker-rank-30-days-of-code/Day27.java or day 27: testing hacker rank solutions or day 27: testing hacker rank solutions in c++ or hacker rank day 27: testing solutions or hacker rank day 27: solutions or Hackerrank 30 Days of Code Challenges solutions or day 27: solutions in C.

Explanation:- A Discrete Mathematics professor has a class of n students. Frustrated with their lack of discipline, the professor decides to cancel class if fewer than k students are present when class starts. Given the arrival time of each student, determine if the class is canceled.

Input Format

The first line of input contains t, the number of lectures.

The information for each lecture spans two lines. The first line has two space-separated integers, n (the number of students in the class) and k (the cancelation threshold). The second line contains n space-separated integers describing the array of students' arrival times (A = a0, a1, a2, . . . ,a(n-1)). 


Note: Non-positive arrival times (a(i)<=0) indicate the student arrived early or on time; positive arrival times (a(i)>0) indicate the student arrived a(i) minutes late. If a student arrives exactly on time ( a(i) = 0), the student is considered to have entered before the class started.

Output Format

For each test case, print the word YES if the class is canceled or NO if it is not.

Example

When properly solved, this 

input:

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

Produces this 

Output:

YES
NO

For the first test case, k = 3. The professor wants at least 3 students in attendance, but only 2 arrive on time (-3 and -1). Thus, the class is canceled.


For the second test case, k = 2. The professor wants at least 2 students in attendance, and 2 to arrive on time (0 and 1). Thus, the class is not canceled.

Now there is contradiction according to this problem my first solution should work but I don't know why HackerRank is not accepting my solution and I tried much time but didn't succeed after a time I decide to read discussion section then I found a solution so for submitting solution you need to submit solution 2 and remember one thing there are no test cases for this question so you have to put custom test cases. The custom test case is below.

Custom Test Cases.

5
5 3
-1 90 999 100 0
4 2
0 -1 2 1
3 3
-1 0 1
6 1
-1 0 1 -1 2 3
7 3
-1 0 1 2 3 4 5

Submit this solution:- Click Here

Solution:-

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int T,i,n,k,count;
    int arr[200];
    cin>>T;
    while(T--)
    {
        count=0;
        cin>>n>>k;
        
        for(i = 0; i < n; i++)
        {
            cin>>arr[i];
        }
        for(i = 0; i < n; i++)
        {
            if(arr[i]>=0)
            {
                count++;
            }
        }
        if(count>=k)
        {
            cout<<"No"<<endl;
        }
        else
        {
            cout<<"Yes"<<endl;
        }
    }
}


Solution 2 (Submit This Solution)

#include<bits/stdc++.h>
using namespace std;

int main()
{
    cout<<"5"<<endl; 
    cout<<"5 3"<<endl; 
    cout<<"-1 90 999 100 0"<<endl;
    cout<<"4 2"<<endl; 
    cout<<"0 -1 2 1"<<endl;
    cout<<"3 3"<<endl; 
    cout<<"-1 0 1"<<endl;
    cout<<"6 1"<<endl; 
    cout<<"-1 0 1 -1 2 3"<<endl;
    cout<<"7 3"<<endl; 
    cout<<"-1 0 1 2 3 4 5"<<endl;   
}

Output:-

Day 27 Hacker Rank Solutions

Day 27 Testing Solution In C++


You May Also See

1. Day 28: RegEx, Patterns, and Intro to Databases

2. Day 29: Bitwise AND

3. Day 0: Hello, World.

4. Day 1: Data Types

5. Day 2: Operators
Read More »