HackerRank Day 25: Running Time and Complexity 30 days of code solution

Today we are going to solve HackerRank Day 25: Running Time and Complexity 30 days of code solution 30 days of code solution in C++, Java & Python.

Objective

Today we will learn about running time, also known as time complexity.

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 a O(n^1/2) primality algorithm, or see what sort of optimizations you come up with for an 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 x 10⁹

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, 4, 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.

HackerRank Day 25: Running Time and Complexity 30 days of code solution

Running Time and Complexity HackerRank Solution in C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int isPrime(int n) {
    int i;
    int res = 1;
    if (n < 2) {
        return 0;
    }
    
    for (i = 2; i < sqrt(n); i++) {
        if (n % i == 0) {
            res = 0;
            break;
        }
    }
    
    return res;
}
int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int i;
    int t;
    int n;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d", &n);
        if (isPrime(n)) {
            printf("Prime\n");
        } else {
            printf("Not prime\n");
        }
    }

    return 0;
}

Running Time and Complexity HackerRank Solution in C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        int n;
        cin >> n;
        if(n == 1){
            printf("Not prime\n");
            continue;
        }
        if(n <= 3){
            printf("Prime\n");
            continue;
        }
        if(n % 2 == 0 || n % 3 == 0){
            printf("Not prime\n");
            continue;
        }
        
        bool prime = true;
        int sqRoot = sqrt(n);
        for(int i = 3; i <= sqRoot; i+=2){
            if(n % i == 0){
                prime = false;
                break;
            }
        }
        if(prime){
            printf("Prime\n");
        } else {
            printf("Not prime\n");
        }
        
    }
    return 0;
}

Running Time and Complexity HackerRank Solution in Java

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        final int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            if (isPrime(sc.nextInt()))
                System.out.println("Prime");
            else
                System.out.println("Not prime");
        }
    }
    
    private static boolean isPrime(int num) {
        if (num == 1) return false;
        for (int i = 2; i < Math.sqrt(num); i++)
            if (num % i == 0) return false;
        return true;
    }
}

Running Time and Complexity HackerRank Solution in Python 3

from math import sqrt

T = int(input())


def isPrime(n):
    for i in range(2, int(sqrt(n)+1)):
        if n % i is 0:
            return False
    return True


for _ in range(T):
    n = int(input())
    
    if n >= 2 and isPrime(n):
        print("Prime")
    else:
        print("Not prime")

Running Time and Complexity HackerRank Solution in Python 2

# Enter your code here. Read input from STDIN. Print output to STDOUT
import math

N = int(raw_input().strip())

def isPrime(n):
    if n < 2:
        return False
    elif n < 4:
        return True
    else:
        prime = True
        for i in xrange(2, int(math.sqrt(n))):
            if (n % i == 0):
                prime = False
                break
        return prime

for i in xrange(N):
    num = int(raw_input().strip())
    if isPrime(num):
        print "Prime"
    else:
        print "Not prime"

Running Time and Complexity HackerRank Solution in Javascript

function processData(input) {
  var arr = input.split('\n');
  for (var i = 1; i < arr.length; i++){
    var n = arr[i];
    if(isPrime(n)){
        console.log("Prime");
    } else {
        console.log("Not prime");
    }
  }
}

function isPrime(n){
  if (n <= 1)  {
    return false;
  }
  if (n <= 3) {
    return true;
  }

  // This is checked so that we can skip
  // middle five numbers in below loop
  if (n%2 == 0 || n%3 == 0){
    return false;
  }

  for (var index=5; index*index<=n; index=index+6){
    if (n%index == 0 || n%(index+2) == 0) {
      return false;
    }
  }
  return true;
}


process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

NEXT: HackerRank Day 26: Nested Logic 30 days of code solution

30 Days of Code HackerRank Solutions List – Day 0 to Day 29