Project 2

Ans1=>

int subArraySum(int arr[], int n, int sum)
{
int currentSum = arr[0], start = 0, i;

for (i = 1; i <= n; i++) {
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}

if (currentSum == sum) {
int p = i - 1;
System.out.println("Sum found between indexes " + start+ " and " + p);
return 1;
}

if (i < n)
currentSum = currentSum + arr[i];
}

System.out.println("No subarray found");
return 0;
}

public static void main(String[] args)
{
SubarraySum arraysum = new SubarraySum();
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = arr.length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}

An2=>

import java.util.*;

class permudation
{

static void swap(char[] str, int i, int j)
{
char t = str[i];
str[i] = str[j];
str[j] = t;
}

static void reverse(char str[], int l, int h)
{
while (l < h) {
swap(str, l, h);
l++;
h--;
}
}

static int findCeil(char str[], char first, int l,
int h)
{
int ceilIndex = l;

for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;

return ceilIndex;
}

static void sortedPermutations(char str[])
{

int size = str.length;

Arrays.sort(str);

boolean isFinished = false;
while (!isFinished) {

System.out.println(str);

int i;
for (i = size - 2; i >= 0; --i)
if (str[i] < str[i + 1])
break;

if (i == -1)
isFinished = true;
else {

int ceilIndex = findCeil(str, str[i], i + 1,
size - 1);

swap(str, i, ceilIndex);

reverse(str, i + 1, size - 1);
}
}
}

public static void main(String[] args)
{
char str[] = "ABCD".toCharArray();
sortedPermutations(str);
}
}

Ans3=>

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

public class identicalTree{

static class Node {
int data;
Node left, right;
public Node(int data) { this.data = data; }
}

public static void main(String[] args)
{
Node root1 = new Node(1);
root1.left = new Node(9);
root1.right = new Node(8);
root1.left.left = new Node(7);

Node root2 = new Node(1);
root2.left = new Node(9);
root2.right = new Node(8);
root2.left.left = new Node(7);

if (isIdentical(root1, root2)) {
System.out.println("Both the trees are identical.");
}
else {
System.out.println("Given trees are not identical.");
}
}

static boolean isIdentical(Node root1, Node root2)
{

ArrayList res1 = new ArrayList();
ArrayList res2 = new ArrayList();

inOrder(root1, res1);
inOrder(root2, res2);
if (!res1.equals(res2))
return false;

res1.clear();
res2.clear();
preOrder(root1, res1);
preOrder(root2, res2);
if (!res1.equals(res2))
return false;

res1.clear();
res2.clear();
postOrder(root1, res1);
postOrder(root2, res2);
if (!res1.equals(res2))
return false;

return true;
}

static void inOrder(Node root, ArrayList sol)
{
if (root == null)
return;
inOrder(root.left, sol);
sol.add(root.data);
inOrder(root.right, sol);
}

static void preOrder(Node root, ArrayList sol)
{

if (root == null)
return;
sol.add(root.data);
preOrder(root.left, sol);
preOrder(root.right, sol);
}

static void postOrder(Node root, ArrayList sol)
{

if (root == null)
return;
postOrder(root.left, sol);
postOrder(root.right, sol);
sol.add(root.data);
}
}

Ans4=>
class Node
{
int data;
Node left, right;

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

public class BinaryTree
{
Node root;

int getLeafCount()
{
return getLeafCount(root);
}

int getLeafCount(Node node)
{
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
else
return getLeafCount(node.left) + getLeafCount(node.right);
}

public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(5);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(1);

tree.root.left.left.right = new Node(8);
tree.root.left.right = new Node(4);

tree.root.left.left = new Node(7);

tree.root.left.left.right = new Node(6);

System.out.println("The leaf count of binary tree is : "+ tree.getLeafCount());
}
}

Ans5=>

class calLeaf
{

static int calcNodes(int N, int I)
{
int result = 0;

result = I * (N - 1) + 1;

return result;
}

public static void main(String[] args)
{
int N = 14, I = 7;

System.out.println("Leaf nodes = " +calcNodes(N, I));
}
}

Ans6=>
class Node
{
int data;
Node left, right;

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

public class BinaryTree
{
Node root;

Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}

Node findLCA(Node node, int n1, int n2)
{
if (node == null)
return null;

if (node.data == n1 || node.data == n2)
return node;

Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);

if (left_lca!=null && right_lca!=null)
return node;

return (left_lca != null) ? left_lca : right_lca;
}

public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("LCA(4, 5) = " + tree.findLCA(4, 5).data);
System.out.println("LCA(4, 6) = " + tree.findLCA(4, 6).data);
System.out.println("LCA(3, 4) = " + tree.findLCA(3, 4).data);
System.out.println("LCA(2, 4) = " + tree.findLCA(2, 4).data);
}
}

Ans8=>

import java.util.*;

class Main
{
static char firstRepeating(char str[])
{
HashSet h = new HashSet<>();

for (int i=0; i<=str.length-1; i++)
{
char c = str[i];

if (h.contains(c))
return c;

else 
h.add(c);
}

return '\0';
}

public static void main (String[] args)
{
String str = "skilllync";
char[] arr = str.toCharArray();
System.out.println(firstRepeating(arr));
}
}

Ans9=>

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

class arrayEqual {

public static boolean areEqual(int arr1[], int arr2[])
{
int N = arr1.length;
int M = arr2.length;

if (N != M)
return false;

Map map= new HashMap();
int count = 0;
for (int i = 0; i < N; i++) {
if (map.get(arr1[i]) == null)
map.put(arr1[i], 1);
else {
count = map.get(arr1[i]);
count++;
map.put(arr1[i], count);
}
}

for (int i = 0; i < N; i++) {

if (!map.containsKey(arr2[i]))
return false;

if (map.get(arr2[i]) == 0)
return false;

count = map.get(arr2[i]);
--count;
map.put(arr2[i], count);
}

return true;
}

public static void main(String[] args)
{
int arr1[] = { 37, 75, 25, 45, 20 };
int arr2[] = { 12, 38, 45, 54, 72 };

if (areEqual(arr1, arr2))
System.out.println("Yes");
else
System.out.println("No");
}
}

Ans12=>

import java.util.ArrayList;
import java.util.List;

class circle {

static final int CHARS = 26;

int V;

List> adj;
int[] in;

circle(int V)
{
this.V = V;
in = new int[V];
adj = new ArrayList<>(CHARS);

for(int i = 0; i < CHARS; i++)
{
adj.add(i, new ArrayList<>());
}
}

void addEdge(int v, int w)
{
adj.get(v).add(w);
in[w]++;
}

boolean isEulerianCycle()
{

if (!isSC())
return false;

for(int i = 0; i < V; i++)
if (adj.get(i).size() != in[i])
return false;

return true;
}

boolean isSC()
{
boolean[] visited = new boolean[V];
for(int i = 0; i < V; i++)
visited[i] = false;

int n;
for(n = 0; n < V; n++)
if (adj.get(n).size() > 0)
break;

DFSUtil(n, visited);

for(int i = 0; i < V; i++)
if (adj.get(i).size() > 0 && !visited[i])
return false;

circle gr = getTranspose();

for(int i = 0; i < V; i++)
visited[i] = false;

gr.DFSUtil(n, visited);

for(int i = 0; i < V; i++)
if (adj.get(i).size() > 0 && !visited[i])
return false;

return true;
}

void DFSUtil(int v, boolean[] visited)
{
visited[v] = true;

for(Integer i : adj.get(v))
if (!visited[i])
{
DFSUtil(i, visited);
}
}

circle getTranspose()
{
circle g = new circle(V);
for(int v = 0; v < V; v++)
{

for(Integer i : adj.get(v))
{
g.adj.get(i).add(v);
g.in[v]++;
}
}
return g;
}

static boolean canBeChained(String[] arr, int n)
{
circle g = new circle(CHARS);

for(int i = 0; i < n; i++)
{
String s = arr[i];
g.addEdge(s.charAt(0) - 'a',
s.charAt(s.length() - 1) - 'a');
}

return g.isEulerianCycle();
}

public static void main(String[] args) throws Exception
{
String[] arr1 = { "abc", "bcd","cdf" };
int n1 = arr1.length;

System.out.println((canBeChained(arr1, n1) ?"Can be chained " :"Can't be chained "));

String[] arr2 = { "ab", "bc","cd","da" };
int n2 = arr2.length;

System.out.println((canBeChained(arr2, n2) ?"Can be chained " :"Can't be chained "));
}
}

Ans13=>

import java.util.ArrayList;
import java.util.List;

public class NonReapeatingC {
final static int MAX_CHAR = 256;

static void findFirstNonRepeating()
{
List inDLL = new ArrayList();

boolean[] repeated = new boolean[MAX_CHAR];

String stream = "skilllync";
for (int i = 0; i < stream.length(); i++) {
char x = stream.charAt(i);
System.out.println("Reading " + x+ " from stream \n");

if (!repeated[x]) {
if (!(inDLL.contains(x))) {
inDLL.add(x);
}
else 
{
inDLL.remove((Character)x);
repeated[x]= true;
}
}

if (inDLL.size() != 0) {
System.out.print("First non-repeating character so far is ");
System.out.println(inDLL.get(0));
}
}
}

public static void main(String[] args)
{
findFirstNonRepeating();
}
}
Ans15=>

public class LongestCommonSubsequence
{

int lcs( char[] X, char[] Y, int m, int n )
{
int L[][] = new int[m+1][n+1];

for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}

int max(int a, int b)
{
return (a > b)? a : b;
}

public static void main(String[] args)
{
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
String s1 = "AGGTAB";
String s2 = "GXTXAYB";

char[] X=s1.toCharArray();
char[] Y=s2.toCharArray();
int m = X.length;
int n = Y.length;

System.out.println("Length of LCS is" + " " +
lcs.lcs( X, Y, m, n ) );
}

}

Ans16=>

class maxiSum
{
static int maxSumIS(int arr[], int n)
{
int i, j, max = 0;
int msis[] = new int[n];

for (i = 0; i < n; i++)
msis[i] = arr[i];

for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];

for (i = 0; i < n; i++)
if (max < msis[i])
max = msis[i];

return max;
}

public static void main(String args[])
{
int arr[] = new int[]{1, 101, 2, 3, 100, 4, 5};
int n = arr.length;
System.out.println("Sum of maximum sum "+"increasing subsequence is "+maxSumIS(arr, n));
}
}

Ans19=>

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

class miniSum {

static long minValue(int A[], int B[], int n)
{
Arrays.sort(A);
Arrays.sort(B);

long result = 0;
for (int i = 0; i < n; i++)
result += (A[i] * B[n - i - 1]);

return result;
}

public static void main(String[] args)
{
int A[] = { 3, 1, 1 };
int B[] = { 6, 5, 4 };
int n = A.length;
;
System.out.println(minValue(A, B, n));
}
}

Ans20=>

class larNumPos
{
static void findLargest(int m, int s)
{
if (s == 0)
{
System.out.print(m == 1 ? "Largest number is 0" : "Not possible");

return ;
}

if (s > 9*m)
{
System.out.println("Not possible");
return ;
}

int[] res = new int[m];

for (int i=0; i {

if (s >= 9)
{
res[i] = 9;
s -= 9;
}

else
{
res[i] = s;
s = 0;
}
}

System.out.print("Largest number is ");
for (int i=0; i System.out.print(res[i]);
}

public static void main (String[] args)
{
int s = 12, m = 2;
findLargest(m, s);
}
}

Ans21=>

import java.util.HashSet;

class distinct
{

public static int countTotalDistinct(String str)
{
int cnt = 0;

HashSet items = new HashSet<>();

for (int i = 0; i < str.length(); ++i)
{

String temp = "";

HashSet ans = new HashSet<>();
for (int j = i; j < str.length(); ++j)
{
temp = temp + str.charAt(j);
ans.add(str.charAt(j));

if (!items.contains(temp))
{ items.add(temp);

cnt += ans.size();
}
}
}

return cnt;
}

public static void main(String[] args)
{
String str = "ABCA";
System.out.println(countTotalDistinct(str));
}
}

Ans22=>

import java.io.*;

class powOfTwo {

static boolean isPowerofTwo(int n)
{
int cnt = 0;
while (n > 0) {
if ((n & 1) == 1) {
cnt++; 
}
n = n >> 1; 
}
if (cnt == 1) {
return true;
}
return false;
}

public static void main(String[] args)
{
if (isPowerofTwo(30) == true)
System.out.println("Yes");
else
System.out.println("No");

if (isPowerofTwo(128) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}