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

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

Find middle element in a linkedlist

Please refer the Linked List code in the below GitHub repo.
https://github.com/dkbalachandar/custom-linkedlist

 

   private void findMiddleElement() {

        //Move by one node at a time
        Node firstPointer = head;
        //Move by two nodes at a time
        Node secondPointer = head;
        while (secondPointer!= null && secondPointer.getNext() != null &&
                secondPointer.getNext().getNext() != null) {
            firstPointer = firstPointer.getNext();
            secondPointer = secondPointer.getNext().getNext();
        }
        System.out.println("Middle Element is: "+ firstPointer.getData());

    }

 

Convert Sorted Array to BST

import org.apache.commons.lang3.builder.ToStringBuilder;

/**
 * Convert a sorted array into a Binary Search Tree
 *
 */
public class TreeUtils {

    static class Tree {
        int val;
        Tree left;
        Tree right;

        Tree(int x) {
            val = x;
        }
        @Override
        public String toString() {
            return ToStringBuilder.reflectionToString(this);
        }
    }

    public static void main(String[] args) {
        int num[] = {1, 2, 3, 4, 5, 6, 7};
        Tree tree = sortedArrayToBST(num, 0, num.length - 1);
        System.out.println(tree);
    }

    public static Tree sortedArrayToBST(int[] num, int start, int end) {
        if (start > end)
            return null;
        int middle= (start + end) / 2;
        Tree root = new Tree(num[middle]);
        root.left = sortedArrayToBST(num, start, middle - 1);
        root.right = sortedArrayToBST(num, middle + 1, end);
        return root;
    }
}

Doubly LinkedList implementation in Java

Please refer the below GitHub repository.

https://github.com/dkbalachandar/custom-doublylinkedlist