Challenge

Project 2

KKamini Bopche8 Mar 2025

SUBARRAY WITH GIVEN SUM :

Class Definition: public class SubarrayWithSum {

// This line defines a public class named `SubarrayWithSum`.

// Public classes can be accessed from other parts of the program.

Method Definition:

private static void FindSubArrayWithSumS(int[] arr, int s) {

// This line defines a private static method named `FindSubArrayWithSumS`.

// Private methods can only be accessed from within the `SubarrayWithSum` class.

// Static methods don't require an object of the class to be called.

// The method takes two arguments:

// - `arr`: An integer array containing the elements to search in.

// - `s`: The target sum that the subarray should add up to.

// The method's return type is `void`, meaning it doesn't return any value.

Variable Initialization:

int sum = 0;
int left, right;
left = right = 0;

sum: This integer variable is initialized to 0 to keep track of the current sum of elements in the considered subarray.

left and right: These integer variables are both initialized to 0. They will be used to keep track of the indices of the subarray. left points to the beginning of the subarray, and right points to the end (one element past the last included element).

Looping through the Array:
for(int i = 0; i<arr.length; i++){

// This for loop iterates through each element in the array `arr`.

// - `i`: This is the loop counter variable that starts at 0 and goes up to `arr.length - 1` (inclusive of the first index and exclusive of the last).

// - `arr.length`: This is the length of the array `arr`.

// edge case where sum = 0
if(s == 0){
break;
}

//This if statement checks if the target sum s is 0.

If it is, it means any subarray will satisfy the condition (an empty subarray sums to 0), so the loop is broken using break. This is an edge case to avoid unnecessary iterations.

Adding Elements and Shrinking the Subarray (While Loop)://

// keep adding elements to sum

sum += arr[i];

// while sum greater than s start subtracting from the beginning and moving the left moving to the right

while(sum > s){
sum -= arr[left];
left++;
}

//The current element arr[i] is added to the sum.

The while loop starts and continues as long as sum is greater than the target sum s. This adjusts the subarray to find a subarray with the exact sum by:

Subtracting the element at the left index from the sum: This effectively removes the leftmost element from the subarray.

Incrementing left by 1: This moves the left pointer one position to the right, representing the new start of the subarray.//

// when sum becomes equal to our target sum, we return the indices

if(sum == s){
System.out.println(left + " " + right);
break;
}

The indices left and right (which is still one element past the end) are printed to the console, indicating the starting and ending indices of the subarray.

The break statement exits the loop as the solution has been found.

right++;
}

This line increments the right pointer by 1. This expands the considered subarray by including the next element in the array.

// if no subarray sum equal to target sum was found
if(right == arr.length || left == arr.length){
System.out.println(-1);
}
}

public static void main(String[] args) {
int [] arr1 = {1,2,3,7,5};
int s1 = 12;
FindSubArrayWithSumS(arr1, s1);
int [] arr2 = {1,2,3,4,5,6,7,8,9,10};
int s2 = 15;
FindSubArrayWithSumS(arr2, s2);
}
}

Output :
1 3
0 4

PERMUTATIONS OF A GIVEN STRING :

public class PermutationsOfString {
static void permute(String str, int l, int r)
{
if (l == r){
System.out.print(str + " ");
}
else{
for (int i = l; i <= r; i++){
//Swapping the string by fixing a character
str = swap(str,l,i);
//Recursively calling function permute() for rest of the characters
permute(str, l+1, r);
//Backtracking and swapping the characters again.
str = swap(str,l,i);
}
}
}

// function to convert string to characters and then swap them and re convert to string
static String swap(String a, int i, int j){
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}

public static void main(String[] args){
String str1 = "ABC";
int n1 = str1.length();
permute(str1, 0, n1-1);

System.out.println();

String str2 = "ABSG";
int n2 = str2.length();
permute(str2, 0, n2-1);
}
}
Output :
ABC ACB BAC BCA CBA CAB

ABSG ABGS ASBG ASGB AGSB AGBS BASG BAGS BSAG BSGA BGSA BGAS SBAG SBGA SABG SAGB SGAB SGBA GBSA GBAS GSBA GSAB GASB GABS

Trees

DETERMINE IF TWO TREES ARE IDENTICAL:

public class IdenticalTrees {
Node root1, root2;
static boolean isIdentical(Node root1, Node root2){
if(root1 == null && root2 == null){
return true;
}
if(root1 != null && root2 != null){
return ( root1.key == root2.key && isIdentical(root1.left, root2.left) && isIdentical(root1.right, root2.right) );
}
return false;
}

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

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

boolean result = isIdentical(tree.root1, tree.root2);
String msg = result ? "Trees are identical" : "Trees are not identical";
System.out.println(msg);

}
}
Output :
Trees are identical

COUNT LEAVES IN BINARY TREE:

public class LCAOfBT {
Node root;

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

// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node findLCA(Node node, int n1, int n2)
{
// Base case
if (node == null)
return null;

// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (node.key == n1 || node.key == n2)
return node;

// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);

// If both of the above calls return Non-NULL, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca!=null && right_lca!=null)
return node;

// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null) ? left_lca : right_lca;
}

public static void main(String args[])
{
LCAOfBT tree = new LCAOfBT();
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).key);
System.out.println("LCA(4, 6) = " + tree.findLCA(4, 6).key);
System.out.println("LCA(3, 4) = " + tree.findLCA(3, 4).key);
System.out.println("LCA(2, 4) = " + tree.findLCA(2, 4).key);
}
}
Output :
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2

Sorting

LINKED LIST OF 0S, 1S AND 2S, SORT IT :

public class SortLLOf1s2s0s {
Node head;

public Node addToEnd(Node head, int data){
Node temp = head;
Node n = new Node(data);
if(head==null){
head = n;
return n;
}
while(head.next!=null){
head = head.next;
}
head.next = n;
return temp;
}

public Node sortList(Node head){
if(head==null || head.next==null){
return head;
}

// Create three dummy nodes to point to beginning of three linked lists. These dummy nodes are created to avoid many null checks.
Node head0 = new Node(0);
Node head1 = new Node(0);
Node head2 = new Node(0);

// Initialize current pointers for three lists and whole list.
Node List0 = head0, List1 = head1, List2 = head2;

// Traverse list
Node temp = head;
while (temp!=null)
{
if (temp.data == 0){
List0.next = temp;
List0 = List0.next;
temp = temp.next;
}
else if (temp.data == 1){
List1.next = temp;
List1 = List1.next;
temp = temp.next;
}
else{
List2.next = temp;
List2 = List2.next;
temp = temp.next;
}
}

// Attach three lists
List0.next = (head1.next!=null) ? (head1.next) : (head2.next);
List1.next = head2.next;
List2.next = null;

// Updated head
head = head0.next;
return head;
}

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

public static void main(String[] args) {
SortLLOf1s2s0s list = new SortLLOf1s2s0s();
Node head = null;
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 0);
head = list.addToEnd(head, 2);
head = list.addToEnd(head, 2);
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 2);
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 0);
head = list.addToEnd(head, 2);
list.printList(head);

head = list.sortList(head);

list.printList(head);

}
}
Output :
1 0 2 2 1 2 1 1 0 2
0 0 1 1 1 1 2 2 2 2

Searching

FIND FIRST REPEATED CHARACTER :

import java.util.HashMap;

public class FindFirstRepeatedChar {

void findFirstRepeatedChar(String s){
if(s.length() <= 0){
System.out.println("No string found");
}
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
for(int i = 0; i<s.length(); i++){
int counter = 0;
if(hM.containsKey(s.indexOf(s.charAt(i)))){
counter = hM.get(s.indexOf(s.charAt(i)));
}
hM.put(s.indexOf(s.charAt(i)), counter+1);
}
for(int i = 0; i<s.length();){
if(hM.get(s.indexOf(s.charAt(i))) > 1){
System.out.println(s.charAt(i));
break;
}
else if(hM.get(s.indexOf(s.charAt(i))) == 1){
i++;
if(i == s.length()){
System.out.println(-1);
}
}
}
}

public static void main(String[] args) {
FindFirstRepeatedChar str = new FindFirstRepeatedChar();
String s1 = "skilllync";
str.findFirstRepeatedChar(s1);
String s2 = "helloworld";
str.findFirstRepeatedChar(s2);
}
}
Output :
l

CHECK IF TWO ARRAYS ARE EQUAL OR NOT :

import java.util.HashMap;

public class CheckIf2ArraysAreEqual {
static boolean areEqual(int [] arr1, int [] arr2){
int n = arr1.length;
int m = arr2.length;

// If lengths of arrays are not equal
if (n != m){
return false;
}

// Store arr1[] elements and their counts in
// hash map
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
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);
}
}

// Traverse arr2[] elements and check if all elements of arr2[] are present same number of times or not.
for (int i = 0; i < n; i++) {
// If there is an element in arr2[], but not in arr1[]
if (!map.containsKey(arr2[i])){
return false;
}
// If an element of arr2[] appears more times than it appears in arr1[]
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 = {1,2,5,4,0};
int [] arr2 = {2,4,5,0,1};
if(areEqual(arr1, arr2)){
System.out.println(1);
}else{
System.out.println(0);
}

int [] arr3 = {1,2,5};
int [] arr4 = {2,4,15};
if(areEqual(arr3, arr4)){
System.out.println(1);
}else{
System.out.println(0);
}
}
}
Output :
1

Hashing

RELATIVE SORTING :

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class RelativeSorting {

void sortRelatively(int [] arr1, int [] arr2){

// first sort the array
Arrays.sort(arr1); //O(nLogn)

// create hashmap and put keys as elements of the array and values as their counts
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
for(int i = 0; i<arr1.length; i++){ // O(n)
int counter = 0;
// we check if value already present, if it is we increment counter else we put the new value
if(hM.containsKey(arr1[i])){
counter = hM.get(arr1[i]);
}
hM.put(arr1[i], counter+1);
}

// create an output array
ArrayList output = new ArrayList();

// for each element in arr2, if it is present in arr1 add it to the output list, its value (count) number of times. Remove elements from the hashmap once added
for(int j = 0; j<arr2.length; j++){ //O(n)
if(hM.containsKey(arr2[j])){
output.addAll(Collections.nCopies(hM.get(arr2[j]), arr2[j]));
hM.remove(arr2[j]);
}
}

// loop through elements in arr1 and check if present in hashmap, and similarly add them to the output array
for(int n = 0; n
Output :
2 2 1 1 8 8 3 5 6 7 9
2 2 6 6 4 5 7 8

Graph

SHORTEST SOURCE TO DESTINATION PATH :

import java.util.ArrayDeque;
import java.util.Queue;

class Node
{
// (x, y) represents matrix cell coordinates, and dist represents their minimum distance from the source
int x, y, dist;

Node(int x, int y, int dist)
{
this.x = x;
this.y = y;
this.dist = dist;
}
}

public class ShortestSourceToDestinationPath {
// M × N matrix
private static final int M = 3;
private static final int N = 4;

// Below arrays detail all four possible movements from a cell(left, up, right, down)
private static final int[] row = { -1, 0, 0, 1 };
private static final int[] col = { 0, -1, 1, 0 };

// Function to check if it is possible to go to position (row, col) from the current position. The function returns false if (row, col) is not a valid position or has a value 0 or already visited.
private static boolean isValid(int mat[][], boolean visited[][], int row, int col)
{
return (row >= 0) && (row < M) && (col >= 0) && (col < N) && mat[row][col] == 1 && !visited[row][col];
}

// Find the shortest possible route in a matrix mat from source cell (i, j) to destination cell (x, y)
private static void BFS(int mat[][], int i, int j, int x, int y)
{
// construct a matrix to keep track of visited cells
boolean[][] visited = new boolean[M][N];

// create an empty queue
Queue q = new ArrayDeque<>();

// mark the source cell as visited and enqueue the source node
visited[i][j] = true;
q.add(new Node(i, j, 0));

// stores length of the longest path from source to destination
int min_dist = Integer.MAX_VALUE;

// loop till queue is empty
while (!q.isEmpty())
{
// dequeue front node and process it
Node node = q.poll();

// (i, j) represents a current cell, and dist stores its minimum distance from the source
i = node.x;
j = node.y;
int dist = node.dist;

// if the destination is found, update min_dist and stop
if (i == x && j == y)
{
min_dist = dist;
break;
}

// check for all four possible movements from the current cell and enqueue each valid movement
for (int k = 0; k < 4; k++)
{
// check if it is possible to go to position (i + row[k], j + col[k]) from current position
if (isValid(mat, visited, i + row[k], j + col[k]))
{
// mark next cell as visited and enqueue it
visited[i + row[k]][j + col[k]] = true;
q.add(new Node(i + row[k], j + col[k], dist + 1));
}
}
}

if (min_dist != Integer.MAX_VALUE)
{
System.out.println(min_dist);
}
else {
System.out.print(-1);
}
}

public static void main(String[] args)
{
// input maze
int[][] mat =
{
{ 1, 0, 0, 0},
{ 1, 1, 0, 1},
{ 0, 1, 1, 1}
};

// Find the shortest path from source (0, 0) to destination (7, 5)
BFS(mat, 0, 0, 2, 3);
}
}
Output :
5

MINIMUM COST PATH:

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

public class MinimumCostPath {
// Below arrays detail all four possible movements from a cell (left, top, right, bottom)
static int[] row = { -1, 0, 1, 0 };
static int[] col = { 0, 1, 0, -1 };

static class Node
{
int x;
int y;
int distance;

Node(int x, int y, int distance)
{
this.x = x;
this.y = y;
this.distance = distance;
}
}

// Custom comparator for inserting cells into Priority Queue
static class distanceComparator implements Comparator
{
public int compare(Node a, Node b)
{
if (a.distance < b.distance)
{
return -1;
}
else if (a.distance > b.distance)
{
return 1;
}
else {
return 0;
}
}
}

// Utility method to check whether current cell isValid or not
static boolean isValid(int i, int j, int M, int N)
{
return (i >= 0 && i < M && j >= 0 && j < N);
}

// Method to return shortest path from top-corner to bottom-corner in 2D grid
static int shortestPath(int[][] grid, int M, int N)
{
int[][] dist = new int[M][N];

// Initializing distance array by INT_MAX
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
dist[i][j] = Integer.MAX_VALUE;
}
}

// Initialized source distance as initial grid position value
dist[0][0] = grid[0][0];

PriorityQueue pq = new PriorityQueue(M * N, new distanceComparator());

// Insert source cell to priority queue
pq.add(new Node(0, 0, dist[0][0]));
while (!pq.isEmpty()){

Node curr = pq.poll();
for(int i = 0; i < 4; i++){

int R = curr.x + row[i];
int C = curr.y + col[i];

if (isValid(R, C, M, N)){

if (dist[R][C] > dist[curr.x][curr.y] + grid[R][C]){

// If Node is already been reached once, remove it from priority queue
if (dist[R][C] != Integer.MAX_VALUE)
{
Node adj = new Node(R, C, dist[R][C]);
pq.remove(adj);
}

// Insert cell with updated distance
dist[R][C] = dist[curr.x][curr.y] + grid[R][C];

pq.add(new Node(R, C, dist[R][C]));
}
}
}
}
return dist[M - 1][N - 1];
}

public static void main(String[] args) throws IOException{
int[][] grid = { { 31, 100, 65, 12, 18 },
{ 10, 13, 47, 157, 6 },
{ 100, 113, 174, 11, 33 },
{ 88, 124, 41, 20, 140 },
{ 99, 32, 111, 41, 20 } };

System.out.println(shortestPath(grid, 5, 5));

int[][] grid2 = {{ 42, 93},
{ 7, 14}};

System.out.println(shortestPath(grid2, 2, 2));
}
}
Output :
327

CIRCLE OF STRINGS :

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class RelativeSorting {

void sortRelatively(int [] arr1, int [] arr2){

// first sort the array
Arrays.sort(arr1); //O(nLogn)

// create an output array
ArrayList output = new ArrayList();

// loop through elements in arr1 and check if present in hashmap, and similarly add them to the output array
for(int n = 0; n
Output :
2 2 1 1 8 8 3 5 6 7 9
2 2 6 6 4 5 7 8

Stacks queues

FIRST NON-REPEATING CHARACTER IN A STREAM :

import java.util.ArrayDeque;
import java.util.Queue;

Heap

REARRANGE CHARACTERS :

import java.util.Comparator;
import java.util.PriorityQueue;

class Key {
int freq; // store frequency of character
char ch;
Key(int val, char c)
{
freq = val;
ch = c;
}
}

class KeyComparator implements Comparator {

// Overriding compare()method of Comparator
public int compare(Key k1, Key k2)
{
if (k1.freq < k2.freq)
return 1;
else if (k1.freq > k2.freq)
return -1;
return 0;
}
}

public class RearrangeChars {
static int MAX_CHAR = 26;

// Function to rearrange character of a string so that no char repeat twice
static void rearrangeString(String str)
{
int n = str.length();

// Store frequencies of all characters in string
int[] count = new int[MAX_CHAR];

for (int i = 0; i < n; i++)
count[str.charAt(i) - 'a']++;

// Insert all characters with their frequencies into a priority_queue
PriorityQueue pq
= new PriorityQueue<>(new KeyComparator());
for (char c = 'a'; c <= 'z'; c++) {
int val = c - 'a';
if (count[val] > 0)
pq.add(new Key(count[val], c));
}

// 'str' that will store resultant value
str = "";

// works as the previous visited element
// initial previous element be. ( '#' and
// it's frequency '-1' )
Key prev = new Key(-1, '#');

// traverse queue
while (pq.size() != 0) {

// pop top element from queue and add it to string.
Key k = pq.peek();
pq.poll();
str = str + k.ch;

// If frequency of previous character is less than zero that means it is useless, we need not to push it
if (prev.freq > 0)
pq.add(prev);

// make current character as the previous 'char' decrease frequency by 'one'
(k.freq)--;
prev = k;
}

// If length of the resultant string and original string is not same then string is not valid
if (n != str.length())
System.out.println(0);
else
System.out.println(1);
}

public static void main(String args[])
{
String str = "bbbabaaacd";
rearrangeString(str);
String str2 = "bbbbb";
rearrangeString(str2);
}
}
Output :
1
0

Dynamic programming

LONGEST COMMON SUBSEQUENCE :

import java.util.HashMap;
import java.util.Map;

public class LongestCommonSubSeq {
public static int findLCS(String X, String Y, int m, int n, Map<String, Integer> lookup)
{
// return if the end of either string is reached
if (m == 0 || n == 0) {
return 0;
}

// construct a unique map key from dynamic elements of the input
String key = m + "|" + n;

// if the subproblem is seen for the first time, solve it and store its result in a map
if (!lookup.containsKey(key))
{
// if the last character of `X` and `Y` matches
if (X.charAt(m - 1) == Y.charAt(n - 1)) {
lookup.put(key, findLCS(X, Y, m - 1, n - 1, lookup) + 1);
}
else {
// otherwise, if the last character of `X` and `Y` don't match
lookup.put(key, Integer.max(findLCS(X, Y, m, n-1, lookup), findLCS(X, Y, m - 1, n, lookup)));
}
}

// return the subproblem solution from the map
return lookup.get(key);
}

public static void main(String[] args)
{
String X = "ABCBDAB", Y = "BDCABA";

// create a map to store solutions to subproblems
Map<String, Integer> lookup = new HashMap<>();

System.out.println("The length of the LCS is " + findLCS(X, Y, X.length(), Y.length(), lookup));
}
}
Output :
The length of LCS is 4

COUNT NUMBER OF HOPS :

public class CountNumberOfHops {

static int printCountDP(int steps){
// Create the array of size 3.
int [] ways = new int[3];
int n = steps;

// Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;

// Run a loop from 3 to n
// Bottom up approach to fill the array
for(int i=3 ; i<=n ; i++){
ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3];
}

return ways[n%3];
}

public static void main(String arg[]){
int steps1 = 1;
System.out.println(printCountDP(steps1));
int steps2 = 5;
System.out.println(printCountDP(steps2));
}
}
Output :
1
13

Greedy

N MEETINGS IN ONE ROOM :

import java.util.Arrays;
import java.util.Comparator;

class Comparison {
static void compare(Integer arr[], int n)
{
Arrays.sort(arr, new Comparator()
{
@Override
public int compare(Integer s1, Integer s2)
{
return s1 - s2;
}
});
}
}

public class NMeetingsINOneRoom {

static void findMaxMeetings(Integer [] start, Integer [] finish, int n){
Comparison.compare(finish, n);
Integer i, j;
i = 0;
System.out.println("Following meetings are possible :");
System.out.print(i+1 + " ");

for(j = 1; j<n; j++){
if(start[j] >= finish[i]){
System.out.print(j+1 + " ");
i = j;
}
}
}

public static void main(String[] args) {
Integer [] start = {1,3,0,5,8,5};
Integer [] finish = {2,4,6,7,9,9};
Integer n = finish.length;
findMaxMeetings(start, finish, n);
}
}
Output :
1 2 4 5

MINIMISE THE SUM OF PRODUCT :

import java.util.Arrays;

public class MinimiseSumOfProducts {

static long minimiseSum(int [] arr1, int [] arr2, int n){
Arrays.sort(arr1);
Arrays.sort(arr2);

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

return result;
}

public static void main(String[] args)
{
int arr1[] = {3,1,1 };
int arr2[] = {6,5,4};
int n1 = arr1.length;

System.out.println(minimiseSum(arr1, arr2, n1));

int arr3[] = {6,1,9,5,4 };
int arr4[] = {3,4,8,2,4};
int n2 = arr3.length;

System.out.println(minimiseSum(arr3, arr4, n2));
}
}
Output :
23
80

LARGEST NUMBER POSSIBLE :

public class LargestNumberPossible {

static void largestNum(int N, int S){
// if sum is 0
if (S == 0)
{
System.out.print(N == 1 ? 0 : -1);
return ;
}

// Sum greater than the maximum possible sum
if (S > 9*N)
{
System.out.println(-1);
return ;
}

// create result array
int [] res = new int [N];
for(int i = 0; i<N; i++){
if(S >= 9){
res[i] = 9;
S -= 9;
}
else{
res[i] = S;
S = 0;
}
}
for (int i=0; i<N; i++)
System.out.print(res[i] + "");
System.out.println();
}

public static void main(String[] args) {
largestNum(2, 9);
largestNum(3, 20);
}
}
Output :
90
992

Two pointer & sliding window

LONGEST DISTINCT CHARACTERS IN STRING :

import java.util.HashMap;

public class LongestDistinctCharacters {

private static int findLongestDistinctCharacters(String s) {

// Creating a set to store the last positions of occurrence
HashMap<Character, Integer> seen = new HashMap<>();
int maximum_length = 0;

// starting the initial point of window to index 0
int start = 0;

for(int end = 0; end < s.length(); end++){
// Checking if we have already seen the element or not
if(seen.containsKey(s.charAt(end))){
// If we have seen the number, move the start pointer to position after the last occurrence
start = Math.max(start, seen.get(s.charAt(end)) + 1);
}

// Updating the last seen value of the character
seen.put(s.charAt(end), end);

maximum_length = Math.max(maximum_length, end-start + 1);
}
return maximum_length;
}

public static void main(String[] args) {
String s = "abababcdefababcdab";
System.out.println(findLongestDistinctCharacters(s));
}
}
Output :
6

SMALLEST WINDOW IN A STRING CONTAINING ALL THE CHARACTERS OF ANOTHER STRING :

public class SmallestWindowWithCharsInString {
static final int no_of_chars = 256;

static String findSmallestWindowContainingT(String str, String pat){
int len1 = str.length();
int len2 = pat.length();

// Check if string's length is less than pattern's length. If yes then no such window can exist
if (len1 < len2) {
System.out.println(-1);
return "";
}

int hash_pat[] = new int[no_of_chars];
int hash_str[] = new int[no_of_chars];

// Store occurrence of characters of pattern
for (int i = 0; i < len2; i++){
hash_pat[pat.charAt(i)]++;
}

int start = 0, start_index = -1, min_len = Integer.MAX_VALUE;

// Start traversing the string. Count of characters
int count = 0;
for (int j = 0; j < len1; j++) {

// Count occurrence of characters of string
hash_str[str.charAt(j)]++;

// If string's char matches with pattern's char then increment count
if (hash_str[str.charAt(j)] <= hash_pat[str.charAt(j)]){
count++;
}

// If all the characters are matched
if (count == len2) {

// Try to minimize the window
while (hash_str[str.charAt(start)] > hash_pat[str.charAt(start)] || hash_pat[str.charAt(start)] == 0) {
if (hash_str[str.charAt(start)] > hash_pat[str.charAt(start)]){
hash_str[str.charAt(start)]--;
start++;
}
}

// update window size
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}

// If no window found
if (start_index == -1) {
System.out.println(-1);
return "";
}

// Return substring starting from start_index and length min_len
return str.substring(start_index, start_index + min_len);
}

public static void main(String[] args)
{
String str1 = "timetopractise";
String pat1 = "toc";
System.out.print(findSmallestWindowContainingT(str1, pat1));

System.out.println();

String str2 = "zoomlazapzo";
String pat2 = "oza";
System.out.print(findSmallestWindowContainingT(str2, pat2));
}
}
Output :
toprac
apzo

Bit Manipulation

POWER OF 2 :

public class PowerOfTwo {
static boolean isPowerOfTwo (int x){

/* First x in the below expression is for the case when x is 0 */
return x!=0 && ((x&(x-1)) == 0);

}

public static void main(String[] args)
{
System.out.println(isPowerOfTwo(1) ? "Yes" : "No");
System.out.println(isPowerOfTwo(98) ? "Yes" : "No");
}
}
Output :
Yes
No

Project 2

Ship work like this
in your own course.

Talk to a career counsellor

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.