Wilson’s Theorem to find prime number

Wilson’s Theorem states that a natural number is p > 1 is a prime number if only if the below condition is met.

  (p - 1) ! ≡  -1   mod p 
 OR  (p - 1) ! ≡  (p-1) mod p

For example, Take p as 4
(4 – 1)! = 3 ! => 3 * 2 * 1 = 6
(6 % 4) != 3 => 6 not equals to 3
So p is not a prime number.

Take p as 5
(5-1)! = 4 ! => 4*3*2*1 = 24
24%5 == 4
4 == 4
So p is a prime number.

Refer the below code to know how to do with a java program.

import java.util.Scanner;

public class PrimeFInder {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();
        System.out.println("The entered number is "+number);

        //  (p - 1) ! ≡  (p-1) mod p
        int lhs = getFactorialValue(number- 1) % number;
        int rhs = number - 1;
        if(lhs == rhs){
            System.out.println("Its a prime number");
        }else{
           System.out.println("Its an non prime number");
        }
    }

    private static int getFactorialValue(int n) {
        int value = 1;
        for (int i = 1; i <= n; i++) {
            value *= i;
        }
        return value;
    }
}

The output is given below,

12
The entered number is 12
Its an non prime number

Advertisements

Finding the majority Element with Moore’s Voting Algorithm

Leetcode problem:

https://leetcode.com/problems/majority-element/description/

Problem Description:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exists in the array.

Algorithm Link:

https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Solution:

public class Main {

    public static int majorityElement(int[] nums) {

        int currentElement = 0;
        int counter = 0;
        for (int num : nums) {
            if (counter == 0) {
                currentElement = num;
                counter = 1;
            }
            else {
                if (num == currentElement) {
                    counter++;
                }
                else {
                    counter--;
                }
            }
        }
        return currentElement;
    }

    public static void main(String[] args) {

        int[] nums = new int[] { 1, 3, 4, 5, 5, 1, 1 };
        System.out.println(majorityElement(nums));
    }
}

Counting sort implementation in Java

Please refer the below Github repo to know the counting sort implementation in Java

https://github.com/dkbalachandar/bucketsorting.git

Time complexity is O(n+m), here m is the number of elements in the array.

Binary Tree, Binary Search Tree, Heap, Min-Heap and Max-Heap

Binary Tree is a tree representation of data which satisfy the below condition
1. Each node in a tree contains at most two nodes.

Binary Search Tree is a tree representation of data which satisfy the below condition
1. Each node in a tree contains at most two nodes.
2. The value of the root node is greater than the value of the left node
3. The value of the right node is greater than the value of the root node

Heap is a tree based data structure which satisfies the below conditions

1. Its a complete Binary Tree which means all the levels are completely filled

2. All nodes are greater than/Smaller than its children. If the parent node is greater than its children, then that heap is called as Max Heap. If the parent node is less than its children then that is called as Min Heap

Bucket Sorting In Java

This algorithm works by distributing the element into a buckets, then sorting the bucket contents, finally combining the all the buckets one by one

Best case and Average case Time complexity is O(n+m), where m is the largest number in the data set

Worst case time complexity is O(n^2)

Please refer the below GitHub repository

https://github.com/dkbalachandar/bucketsorting

Algorithm Time Complexity

O(1) – Completes the operation/process in a single step. Best example is the number to search in an array is present in the first index itself
O(n) – Completes the operation/process in n steps. So the time gets increased linearly. Best example is the number to find in an array is present in the last index only
O(log n) – Completes the operation/process in n/2 steps. Best example, do a binary search in a sorted array.
O(n^2) – Completes the operation n^2 steps. Best example is sorting an array by bubble sort.
O(n log n) – Completes the operation n*n/2 steps. Best example is sorting an array by quick sort.

Binary Search in Java

Please refer the below GitHub Repo

https://github.com/dkbalachandar/binarysearch

import java.util.Arrays;
import java.util.Scanner;


public class BinarySearch {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("Number of elements:");
        int n = scanner.nextInt();
        System.out.println("Number to Search:");
        int element = scanner.nextInt();
        if (n == 0 || element == 0) {
            System.out.println("Invalid Number");
            System.exit(0);
        }
        int[] array = new int[n];
        for (int i = 1; i <= n; i++) {
            array[i - 1] = i;
        }
        System.out.println(Arrays.toString(array));
        System.out.println("Position is " + binarySearch(array, 0, array.length, element));
    }

    private static int binarySearch(int[] array, int start, int last, int element) {

        if (start  element) {
                return binarySearch(array, start, middle, element);
            } else if (array[middle] < element) {
                return binarySearch(array, middle + 1, last, element);
            }
        }
        return -1;
    }
}