Day 25 Running Time And Complexity Hackerrank Solution in C++

Day 25 Running Time And Complexity Hackerrank Solution In C++. This problem is a subset of Hackerrank's 30 Days of Code. If a number (n) isn't divisible by all the numbers in the inclusive range from 2 to the integer square root of that number (n ** 0.5) then that number is prime.

Objective

Today we will learn about running time, also known as time complexity. Check out the Tutorial tab for learning materials and an instructional video.

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 is Prime or Not prime.

Note: If possible, try to come up with an O(√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.

Constraints

• 1 <= T <= 30
• 1 <= n <= 2 * 10^9

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 by 1 and itself, so we print Prime on a new line.
Test Case 2: n = 7.
7 is only divisible by 1 and itself, so we print Prime on a new line.

Submit this solution: Click Here

Running Time And Complexity Hackerrank Solution in C++

#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;

}

The Output of Day 25 Running Time And Complexity Solution

Similar to 30 Days of Code

• Day 26 Nested Logic Hackerrank Solution in C++
• Day 27 Testing Hackerrank Solution In C++
• Day 28 RegEx, Patterns, and Intro to Databases Hackerrank Solution
• Day 29 Bitwise AND Operators in C Hackerrank Solution
• Day 0 Hello World in C Hackerrank Solution

Day 22 Binary Search Tree Hackerrank Solution In C++ | 30 Days

Day 22 Binary Search Tree Hackerrank Solution In C++. This problem statement comes under the Hackerrank 30 days of code. Binary Search Tree(BST):- I have explained everything about BST in the next tutorial you can find a link to the next tutorial at the end of this tutorial.

Task: The height of a binary search tree is the number of edges between the tree's root and its furthest leaf. You are given a pointer, root, pointing to the root of a binary search tree. Complete the getHeight function provided in your editor so that it returns the height of the binary search tree.

Input Format

1. The locked stub code in your editor reads the following inputs and assembles them into a binary search tree:
2. The first line contains an integer, n, denoting the number of nodes in the tree.
3. Each of the n subsequent lines contains an integer, data, denoting the value of an element that must be added to the BST.

Output Format

The locked stub code in your editor will print the integer returned by your getHeight function denoting the height of the BST.

Sample Input

7
3
5
2
1
4
6
7

Sample Output

3

Copy the code and paste it into Hacker rank editor and click to submit button, but before this process, you have to click the below link.

Submit this Solution: Click Here

Day 22 Binary Search Tree Hackerrank Solution In C++

#include <iostream>
#include <cstddef>

using namespace std;

class Node {
  public: int data;
  Node * left;
  Node * right;
  Node(int d) {
    data = d;
    left = NULL;
    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;
    }
  }

  int getHeight(Node * root) {
    //Write your code here
    if (!root) {
      return -1;
    }
    int leftDepth = getHeight(root -> left);
    int rightDepth = getHeight(root -> right);

    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
  }

}; //End of Solution
int main() {
  Solution myTree;
  Node * root = NULL;
  int t;
  int data;

  cin >> t;

  while (t--> 0) {
    cin >> data;
    root = myTree.insert(root, data);
  }
  int height = myTree.getHeight(root);
  cout << height;

  return 0;
}

Binary Search Tree Time and Space Complexity

Binary Search Tree Complexity	Average Case	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)

Day 22 Binary Search Tree Hackerrank Output

Similar to 30 Days of Code

• Day 23 BST Level Order Traversal HackerRank Solution In C++
• Day 24 More Linked Lists Hackerrank Solution In C++
• Day 25 Running Time And Complexity Hackerrank Solution in C++
• Day 26 Nested Logic Hackerrank Solution in C++
• Day 27 Testing Hackerrank Solution In C++

Day 24 More Linked Lists Hackerrank Solution In C++ | 30 Days

Day 24 More Linked Lists Hackerrank Solution In C++. Under the 30 Days of Code, this is a Day 24 programming problem. Below is the hackerrank linked list problem statement.

Task: A Node class is provided for you in the editor. A Node object has an integer data field, data, and a Node instance pointer, next, pointing to another node (i.e.: the next node in a list).

A removeDuplicates function is declared in your editor, which takes a pointer to the head node of a linked list as a parameter. Complete removeDuplicates so that it deletes any duplicate nodes from the list and returns the head of the updated list.

Note: The head pointer may be null, indicating that the list is empty. Be sure to reset your next pointer when performing deletions to avoid breaking the list.

Input Format

1. You do not need to read any input from stdin. The following input is handled by the locked stub code and passed to the removeDuplicates function:
2. The first line contains an integer, N, the number of nodes to be inserted.
3. The N subsequent lines each contain an integer describing the data value of a node being inserted at the list's tail.

Constraints

The data elements of the linked list argument will always be in non-decreasing order.

Output Format

Your removeDuplicates function should return the head of the updated linked list. The locked stub code in your editor will print the returned list to stdout.

Sample Input

6
1
2
2
3
3
4

Sample Output

1 2 3 4

Explanation

N = 6, and our non-decreasing list is {1, 2, 2, 3, 3, 4}. The values 2 and 3 both occur twice in the list, so we remove the two duplicate nodes. We then return our updated (ascending) list, which is {1, 2, 3, 4}.

Copy the code and paste it into HackerRank Editor.

Submit this solution: Click Here

Day 24 More Linked Lists Hackerrank Solution In C++

#include <cstddef>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
class Node {
  public: int data;
  Node * next;
  Node(int d) {
    data = d;
    next = NULL;
  }
};
class Solution {
  public: Node * removeDuplicates(Node * head) {
    if (!head)
      return head;

    Node * node = head;
    while (node -> next) {
      if (node -> data == node -> next -> data)
        node -> next = node -> next -> next;
      else
        node = node -> next;
    }

    return head;
  }
  Node * insert(Node * head, int data) {
    Node * p = new Node(data);
    if (head == NULL) {
      head = p;

    } else if (head -> next == NULL) {
      head -> next = p;

    } else {
      Node * start = head;
      while (start -> next != NULL) {
        start = start -> next;
      }
      start -> next = p;

    }
    return head;

  }
  void display(Node * head) {
    Node * start = head;
    while (start) {
      cout << start -> data << " ";
      start = start -> next;
    }
  }
};

int main() {
  Node * head = NULL;
  Solution mylist;
  int T, data;
  cin >> T;
  while (T--> 0) {
    cin >> data;
    head = mylist.insert(head, data);
  }
  head = mylist.removeDuplicates(head);

  mylist.display(head);

}

More Linked Lists Hackerrank Solution Output

Similar to 30 Days of Code

• Day 25 Running Time And Complexity Hackerrank Solution in C++
• Day 26 Nested Logic Hackerrank Solution in C++
• Day 27 Testing Hackerrank Solution In C++
• Day 28 RegEx, Patterns, and Intro to Databases Hackerrank Solution
• Day 29 Bitwise AND Operators in C Hackerrank Solution