Project 1

1:

package Project_1;

//Java program to find equilibrium
//index of an array
public class EquilibriumIndex {
int equilibrium(int arr[], int n) {
int i, j;
int leftsum, rightsum;
for (i = 0; i < n; ++i) {
leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];

rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];
if (leftsum == rightsum)
return i;
}
return -1;
}

public static void main(String[] args) {
EquilibriumIndex equi = new EquilibriumIndex();
int arr[] = { 1, 3, 5, 2, 2 };
int arr_size = arr.length;

// Function call
System.out.println(equi.equilibrium(arr, arr_size));
}
}

2:

package Project_1;

import java.io.*;
public class LeadersInArray{
/*Java Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
int j;
for (j = i + 1; j < size; j++)
{
if (arr[i] <=arr[j])
break;
}
if (j == size)
System.out.print(arr[i] + " ");
}
}
public static void main(String[] args)
{
LeadersInArray lead = new LeadersInArray();
int arr[] = new int[]{16, 17, 4, 3, 5, 2};
int n = arr.length;
lead.printLeaders(arr, n);
}
}

3:

package Project_1;
// reverse string word wise
import java.util.*;
public class str {

// Reverse the letters
// of the word
static void reverse(char str[], int start, int end)
{
char temp;

while (start <= end) {
// Swapping the first
// and last character
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
// Function to reverse words
static char[] reverseWords(char[] s)
{
int start = 0;
for (int end = 0; end < s.length; end++) {
if (s[end] == '.') {
reverse(s, start, end);
start = end + 1;
}
}
reverse(s, start, s.length - 1);
reverse(s, 0, s.length - 1);
return s;
}

public static void main(String[] args)
{
String s = "i.like.this.program.very.much. ";

// Function call
char[] p = reverseWords(s.toCharArray());
System.out.print(p);
}
}

4:

package Project_1;
//Java program to remove duplicate character
import java.util.*;

public class Remove{
static String removeDuplicate(char str[], int n)
{
int index = 0;
for (int i = 0; i < n; i++)
{

// Check if str[i] is present before it
int j;
for (j = 0; j < i; j++)
{
if (str[i] == str[j])
{
break;
}
}

// If not present, then add it to
// result.
if (j == i)
{
str[index++] = str[i];
}
}
return String.valueOf(Arrays.copyOf(str, index));
}
public static void main(String[] args)
{
char str[] = "skilllync".toCharArray();
int n = str.length;
System.out.println(removeDuplicate(str, n));
}
}

5:

package Project_1;
import java.io.*;
public class Middle {

Node head;

// Creating a new Node
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}

public void pushNode(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
public void printNode()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "->");
temp = temp.next;
}
System.out.print("Null" + "\n");
}

// Finding the length of the list.
public int getLen()
{
int length = 0;
Node temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}

public void printMiddle()
{
if (head != null) {
int length = getLen();
Node temp = head;
int middleLength = length / 2;
while (middleLength != 0) {
temp = temp.next;
middleLength--;
}
System.out.print("The middle element is [" + temp.data + "]");
System.out.print("\n\n");
}
}

public static void main(String[] args)
{
Middle list = new Middle();
for (int i = 5; i >= 1; i--) {
list.pushNode(i);
list.printNode();
list.printMiddle();
}
}
}

6:

package Project_1;

//Java program for reversing the linked list

public class RevLinkedList {

static Node head;

static class Node {

int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

/* Function to reverse the linked list */
Node reverse(Node node) {
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}

void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}

public static void main(String[] args) {
RevLinkedList list = new RevLinkedList();
list.head = new Node(85);
list.head.next = new Node(15);
list.head.next.next = new Node(4);
list.head.next.next.next = new Node(20);

System.out.println("Given Linked list");
list.printList(head);
head = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(head);
}
}

7..

package Project_1;

//Java program to pairwise swap
//elements of a linked list
public class SortLinkedList {
// Head of list
Node head;

// Linked list Node
class Node {
int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

void pairWiseSwap() {
Node temp = head;

while (temp != null && temp.next != null) {
// Swap the data
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
}

public void push(int new_data) {
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}

// Function to print linked list
void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

public static void main(String args[]) {
SortLinkedList llist = new SortLinkedList();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

System.out.println("Linked List before calling pairWiseSwap() ");
llist.printList();

llist.pairWiseSwap();

System.out.println("Linked List after calling pairWiseSwap() ");
llist.printList();
}
}

8..

package Project_1;
//Java program to add two numbers
//represented by linked list
public class AddLinkedList {

static Node head1, head2;

static class Node {

int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

/* Adds contents of two linked lists and prints it */
void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;

addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
printList(result.next);
}

/* Adds lists and returns the carry */
private int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}

/* Appends preceding zeros in case a list is having lesser nodes than the other one*/
private void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}

/* Utility function to print a linked list */
void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}

// Driver Code
public static void main(String[] args) {
AddLinkedList list = new AddLinkedList();

// creating first list
list.head1 = new Node(7);
list.head1.next = new Node(5);
System.out.print("First list is ");
list.printList(head1);

// creating second list
list.head2 = new Node(2);
System.out.print("Second list is ");
list.printList(head2);

System.out.print("Resultant list is ");
// add the two lists and see the result
list.addTwoLists(head1, head2);
}

// this code is contributed by *Saurabh321Gupta*
}

9.

package Project_1;
//Java program to convert binary tree to double linked list

class Node {
int data;
Node left, right;

Node(int item) {
data = item;
left = right = null;
}
}

public class BinaryTreetoLL {
Node root;

Node bintree2listUtil(Node node) {
// Base case
if (node == null)
return node;
if (node.left != null) {
Node left = bintree2listUtil(node.left);

for (; left.right != null; left = left.right)
;

left.right = node;

node.left = left;
}

if (node.right != null) {
// Convert the right subtree
Node right = bintree2listUtil(node.right);

for (; right.left != null; right = right.left)
;
right.left = node;

// Make successor as next of root
node.right = right;
}

return node;
}

// The main function that first calls bintree2listUtil(), then follows
// step 3 of the above algorithm

Node bintree2list(Node node) {
// Base case
if (node == null)
return node;
node = bintree2listUtil(node);

while (node.left != null)
node = node.left;

return node;
}

/* Function to print nodes in a given doubly linked list */
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.right;
}
}

public static void main(String[] args) {
BinaryTreetoLL tree = new BinaryTreetoLL();

// Let us create the tree shown in above diagram
tree.root = new Node(10);
tree.root.left = new Node(12);
tree.root.right = new Node(15);
tree.root.left.left = new Node(25);
tree.root.left.right = new Node(30);
tree.root.right.left = new Node(36);

// Convert to DLL
Node head = tree.bintree2list(tree.root);

// Print the converted list
tree.printList(head);
}
}

10..

package Project_1;
//A Java program for Bellman-Ford's single source shortest
//path algorithm.

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

//A class to represent a connected, directed and weighted
//graph
public class Graph {

// A class to represent a weighted edge in graph
class Edge {
int src, dest, weight;
Edge() { src = dest = weight = 0; }
};

int V, E;
Edge edge[];

// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
void BellmanFord(Graph graph, int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];

// Step 1: Initialize distances from src to all
// other vertices as INFINITE
for (int i = 0; i < V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
for (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE
&& dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE
&& dist[u] + weight < dist[v]) {
System.out.println(
"Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}

// A utility function used to print the solution
void printArr(int dist[], int V)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
System.out.println(i + "\t\t" + dist[i]);
}

// Driver's code
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph

Graph graph = new Graph(V, E);

graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;

graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;

graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;

graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;

graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;

graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;

graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;

graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;

// Function call
graph.BellmanFord(graph, 0);
}
}

11.

package Project_1;

//Java program for the above approach

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

public class sort {
public static int minSwaps(int[] nums)
{
int len = nums.length;
HashMap map = new HashMap<>();
for (int i = 0; i < len; i++)
map.put(nums[i], i);

Arrays.sort(nums);
boolean[] visited = new boolean[len];
Arrays.fill(visited, false);
int ans = 0;
for (int i = 0; i < len; i++) {
if (visited[i] || map.get(nums[i]) == i)
continue;

int j = i, cycle_size = 0;
while (!visited[j]) {
visited[j] = true;

// move to next node
j = map.get(nums[j]);
cycle_size++;
}
if (cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}

public static void main(String[] args)
{
int[] a = { 1, 5, 4, 3, 2 };
sort g = new sort();
System.out.println(sort.minSwaps(a));
}
}

12...

package Project_1;

//Java program to implement a stack that supports
import java.util.*;

class MyStack {
Stack s;
Integer minEle;

// Constructor
MyStack() {
s = new Stack();
}

// Prints minimum element of MyStack
void getMin() {
// Get the minimum number in the entire stack
if (s.isEmpty())
System.out.println("Stack is empty");

// variable minEle stores the minimum element
// in the stack.
else
System.out.println("Minimum Element in the " + " stack is: " + minEle);
}

// prints top element of MyStack
void peek() {
if (s.isEmpty()) {
System.out.println("Stack is empty ");
return;
}

Integer t = s.peek(); // Top element.

System.out.print("Top Most Element is: ");
if (t < minEle)
System.out.println(minEle);
else
System.out.println(t);
}

// Removes the top element from MyStack
void pop() {
if (s.isEmpty()) {
System.out.println("Stack is empty");
return;
}

System.out.print("Top Most Element Removed: ");
Integer t = s.pop();
if (t < minEle) {
System.out.println(minEle);
minEle = 2 * minEle - t;
}

else
System.out.println(t);
}

void push(Integer x) {
if (s.isEmpty()) {
minEle = x;
s.push(x);
System.out.println("Number Inserted: " + x);
return;
}

if (x < minEle) {
s.push(2 * x - minEle);
minEle = x;
}

else
s.push(x);

System.out.println("Number Inserted: " + x);
}
};

public class Main {
public static void main(String[] args) {
MyStack s = new MyStack();

// Function calls
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
}
}