Project 2
A set of 20 problems to solve in an optimised way with the given restrictions of time and space complexity
Arrays and Strings
SUBARRAY WITH GIVEN SUM
Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to a given number S.
Implement a method subArraySum(a[], s), where A is array of size n and s is the sum.
And return the starting and ending positions (0 indexing) of FIRST such occurring subarray from the left if sum equals to subarray, else print -1.
Code knowing that-
1 <= N <= 107">107107
1 <= Ai <= 1010">10101010
public class Permutation
{
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
Permutation permutation = new Permutation();
permutation.permute(str, 0, n-1);
}
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}
public 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);
}
}
PERMUTATIONS OF A GIVEN STRING
Given a string S. The task is to print all permutations of a given string. Implement perm(s) method where s is a string in capital letter. Print all permutations of a given string S with single space and all permutations should be in lexicographically increasing order.
Constraints:
1 ≤ size of string ≤ 5
#include
#include
using namespace std;
void permute(string s , string answer)
{
if(s.length() == 0)
{
cout<
}
for(int i=0 ; i
char ch = s[i];
string left_substr = s.substr(0,i);
string right_substr = s.substr(i+1);
string rest = left_substr + right_substr;
permute(rest , answer+ch);
}
}
int main()
{
string s;
string answer="";
cout<<"Enter the string : ";
cin>>s;
cout<<"\nAll possible strings are : ";
permute(s , answer);
return 0;
}
Output :
Enter the string : ABC All possible strings are : ABC ACB BAC BCA CAB CBA
DETERMINE IF TWO TREES ARE IDENTICAL
Given two binary trees, the task is to find if both of them are identical or not.
Complete the function isIdentical() that takes two roots as parameters and returns true or false.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 1000
1 <=Data of a node <= 1000
#include
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
int identicalTrees(node* a, node* b)
{
if (a == NULL && b == NULL)
return 1;
if (a != NULL && b != NULL) {
return (a->data == b->data
&& identicalTrees(a->left, b->left)
&& identicalTrees(a->right, b->right));
}
return 0;
}
int main()
{
node* root1 = newNode(1);
node* root2 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root2->left = newNode(2);
root2->right = newNode(3);
root2->left->left = newNode(4);
root2->left->right = newNode(5);
if (identicalTrees(root1, root2))
cout << "Both trees are identical.";
else
cout << "Trees are not identical.";
return 0;
}
Output :
Both trees are identical
COUNT LEAVES IN BINARY TREE
Given a Binary Tree of size N , You have to count leaves in it. For example, there are two leaves in following tree
1
/ \
10 39
/
5
Argument is a string representing the tree as described below:
The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.
#include
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
unsigned int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Leaf count of the tree is : "<<
getLeafCount(root) << endl;
return 0;
}
Output :
The leaf count of binary tree is : 3
LOWEST COMMON ANCESTOR IN A BINARY TREE
Given a Binary Tree with all unique values and two nodes value n1 and n2. The task is to find the lowest common ancestor of the given two nodes. We may assume that either both n1 and n2 are present in the tree or none of them is present.
Complete the function lca() that takes nodes, n1, and n2 as parameters and returns LCA node as output.
Expected Time Complexity: O(N).
Expected Space Complexity : O(H).
H is the height of the tree.
Constraints:
1 <= Number of nodes <= 100
1 <= Data of a node <= 1000
import java.util.ArrayList;
import java.util.List;
class Node {
int data;
Node left, right;
Node(int value)
{
data = value;
left = right = null;
}
}
public class BT_NoParentPtr_Solution1 {
Node root;
private List path1 = new ArrayList<>();
private List path2 = new ArrayList<>();
int findLCA(int n1, int n2)
{
path1.clear();
path2.clear();
return findLCAInternal(root, n1, n2);
}
private int findLCAInternal(Node root, int n1, int n2)
{
if (!findPath(root, n1, path1)
|| !findPath(root, n2, path2)) {
System.out.println((path1.size() > 0)
? "n1 is present"
: "n1 is missing");
System.out.println((path2.size() > 0)
? "n2 is present"
: "n2 is missing");
return -1;
}
int i;
for (i = 0; i < path1.size() && i < path2.size();
i++) {
if (!path1.get(i).equals(path2.get(i)))
break;
}
return path1.get(i - 1);
}
private boolean findPath(Node root, int n,
List path)
{
if (root == null) {
return false;
}
path.add(root.data);
if (root.data == n) {
return true;
}
if (root.left != null
&& findPath(root.left, n, path)) {
return true;
}
if (root.right != null
&& findPath(root.right, n, path)) {
return true;
}
path.remove(path.size() - 1);
return false;
}
public static void main(String[] args)
{
BT_NoParentPtr_Solution1 tree
= new BT_NoParentPtr_Solution1();
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));
System.out.println("LCA(4, 6) = "
+ tree.findLCA(4, 6));
System.out.println("LCA(3, 4) = "
+ tree.findLCA(3, 4));
System.out.println("LCA(2, 4) = "
+ tree.findLCA(2, 4));
}
}
Output
LCA(4, 5) = 2 LCA(4, 6) = 1 LCA(3, 4) = 1 LCA(2, 4) = 2
LINKED LIST OF 0S, 1S AND 2S, SORT IT.
Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.
complete the function segregate() which segregates the nodes in the linked list as asked in the problem statement and returns the head of the modified linked list. The printing is done automatically by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 103">103103
class LinkedList
{
Node head;
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
void sortList()
{
int count[] = {0, 0, 0};
Node ptr = head;
while (ptr != null)
{
count[ptr.data]++;
ptr = ptr.next;
}
int i = 0;
ptr = head;
while (ptr != null)
{
if (count[i] == 0)
i++;
else
{
ptr.data= i;
--count[i];
ptr = ptr.next;
}
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
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[])
{
LinkedList llist = new LinkedList();
llist.push(0);
llist.push(1);
llist.push(0);
llist.push(2);
llist.push(1);
llist.push(1);
llist.push(2);
llist.push(1);
llist.push(2);
System.out.println("Linked List before sorting");
llist.printList();
llist.sortList();
System.out.println("Linked List after sorting");
llist.printList();
}
}
Output
Linked List before Sorting 2 1 2 1 1 2 0 1 0 Linked List after Sorting 0 0 1 1 1 1 2 2 2
FIND FIRST REPEATED CHARACTER
Given a string S. The task is to find the first repeated character in it. We need to find the character that occurs more than once and whose index of second occurrence is smallest.
S contains only lowercase letters.
Argument is a string S.
print the first repeating character in the string. If no such character exist print -1.
Constraints:
1 <= |S| <=104">104104
1.
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));
}
}
Output :
l
2.
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 = "helloWorld";
char[] arr = str.toCharArray();
System.out.println(firstRepeating(arr));
}
}
Output :
l
RELATIVE SORTING
Given two arrays A1[] and A2[] of size N and M respectively. The task is to sort A1 in such a way that the relative order among the elements will be same as those in A2. For the elements not present in A2, append them at last in sorted order. It is also given that the number of elements in A2[] are smaller than or equal to number of elements in A1[] andA2[] has all distinct elements.
Expected time complexity is O(N log(N)).
Length of arrays N and M and next two line contains N and M elements respectively.
Output:
Print the relatively sorted array.
Constraints:
1 ≤ A1[], A2[] <= 106">106106
import java.io.*;
import java.util.Arrays;
class GFG {
static int first(int arr[], int low, int high, int x,
int n)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if ((mid == 0 || x > arr[mid - 1])
&& arr[mid] == x)
return mid;
if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
return first(arr, low, (mid - 1), x, n);
}
return -1;
}
static void sortAccording(int A1[], int A2[], int m,
int n)
{
int temp[] = new int[m], visited[] = new int[m];
for (int i = 0; i < m; i++) {
temp[i] = A1[i];
visited[i] = 0;
}
Arrays.sort(temp);
int ind = 0;
for (int i = 0; i < n; i++) {
int f = first(temp, 0, m - 1, A2[i], m);
if (f == -1)
continue;
for (int j = f; (j < m && temp[j] == A2[i]);
j++) {
A1[ind++] = temp[j];
visited[j] = 1;
}
}
for (int i = 0; i < m; i++)
if (visited[i] == 0)
A1[ind++] = temp[i];
}
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };
int A2[] = { 2, 1, 8, 3 };
int m = A1.length;
int n = A2.length;
System.out.println("Sorted array is ");
sortAccording(A1, A2, m, n);
printArray(A1, m);
}
}
Output
Sorted array is 2 2 1 1 8 8 3 5 6 7 9
FIRST NON-REPEATING CHARACTER IN A STREAM
Given an input stream of N characters consisting only of lower case alphabets. The task is to find the first non repeating character, each time a character is inserted to the stream.
If no non repeating element is found print -1.
Argument is x character array which are inserted to the stream.
Output:
For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1.
Constraints:
1 <= N <= 500
1.import java.util.LinkedList;
import java.util.Queue;
public class NonReapatingCQueue {
final static int MAX_CHAR = 26;
static void firstNonRepeating(String str)
{
int[] charCount = new int[MAX_CHAR];
Queue q = new LinkedList();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
q.add(ch);
charCount[ch - 'a']++;
while (!q.isEmpty()) {
if (charCount[q.peek() - 'a'] > 1)
q.remove();
else {
System.out.print(q.peek() + " ");
break;
}
}
if (q.isEmpty())
System.out.print(-1 + " ");
}
System.out.println();
}
public static void main(String[] args)
{
String str = "aabc";
firstNonRepeating(str);
}
}
Output:
a -1 b b
import java.util.LinkedList;
import java.util.Queue;
public class NonReapatingCQueue {
final static int MAX_CHAR = 26;
static void firstNonRepeating(String str)
{
int[] charCount = new int[MAX_CHAR];
Queue q = new LinkedList();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
q.add(ch);
charCount[ch - 'a']++;
while (!q.isEmpty()) {
if (charCount[q.peek() - 'a'] > 1)
q.remove();
else {
System.out.print(q.peek() + " ");
break;
}
}
if (q.isEmpty())
System.out.print(-1 + " ");
}
System.out.println();
}
public static void main(String[] args)
{
String str = "aac";
firstNonRepeating(str);
}
}
Output:
a -1 c
MAXIMUM SUM OF INCREASING SUBSEQUENCES
Given an array A of N positive integers. Find the sum of maximum sum increasing subsequence of the given array.
Complete the function which takes the array and prints the required answer.
Constraints:
1 ≤ N ≤ 106
1 ≤ Ai ≤ 106
Testcase 1: All the increasing subsequences are : (1,101); (1,2,3,100); (1,2,3,4,5). Out of these (1, 2, 3, 100) has maximum sum,i.e., 106.
class GFG
{
static int LCSubStr(String s,String t,
int n,int m)
{
int dp[][]=new int[2][m+1];
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s.charAt(i-1)==t.charAt(j-1))
{
dp[i%2][j]=dp[(i-1)%2][j-1]+1;
if(dp[i%2][j]>res)
res=dp[i%2][j];
}
else dp[i%2][j]=0;
}
}
return res;
}
public static void main (String[] args)
{
String X="OldSite:GeeksforGeeks.org";
String Y="NewSite:GeeksQuiz.com";
int m=X.length();
int n=Y.length();
System.out.println(LCSubStr(X,Y,m,n));
}
}
Output
10
LONGEST COMMON SUBSEQUENCE
Given two strings: string X of length m and string Y of length n find the longest common subsequence
The longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.
For example, if X = “ABCBDAB” and Y = “BDCABA”, the LCS(X, Y) = {“BCBA”, “BDAB”, “BCAB”}.
public class LongestCommonSubsequence
{
int lcs( char[] X, char[] Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, 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 ) );
}
}
Output
Length of LCS is 4
COUNT NUMBER OF HOPS
A frog jumps either 1, 2 or 3 steps to go to top. In how many ways can it reach the top.
Complete the function which takes input N denoting the total number of steps and prints the number of ways to reach the top.
Constraints:
1 ≤ N ≤ 50
import java.io.*;
class GFG
{
static int printCountRec(int dist)
{
if (dist<0)
return 0;
if (dist==0)
return 1;
return printCountRec(dist-1) +
printCountRec(dist-2) +
printCountRec(dist-3);
}
public static void main (String[] args)
{
int dist = 1;
System.out.println(printCountRec(dist));
}
}
Output :
1
2.
import java.io.*;
class GFG
{
static int printCountRec(int dist)
{
if (dist<0)
return 0;
if (dist==0)
return 1;
return printCountRec(dist-1) +
printCountRec(dist-2) +
printCountRec(dist-3);
}
public static void main (String[] args)
{
int dist = 5;
System.out.println(printCountRec(dist));
}
}
Output : 13
N MEETINGS IN ONE ROOM
There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is start time of meeting i and F[i] is finish time of meeting i.
What is the maximum number of meetings that can be accommodated in the meeting room?
Complete the function which takes the array containing the starting time of all the meetings S [ i ] and the array containing the finishing time of all the meetings F [ i ].
Print the order in which the meetings take place separated by a space.
Constraints:
1 ≤ N ≤ 100
1 ≤ S[ i ], F[ i ] ≤ 100000
import java.util.*;
class mycomparator implements Comparator {
@Override public int compare(meeting o1, meeting o2)
{
if (o1.end < o2.end) {
return -1;
}
else if (o1.end > o2.end)
return 1;
return 0;
}
}
class meeting {
int start;
int end;
int pos;
meeting(int start, int end, int pos)
{
this.start = start;
this.end = end;
this.pos = pos;
}
}
class GFG {
public static void maxMeeting(ArrayList al,
int s)
{
ArrayList m = new ArrayList<>();
int time_limit = 0;
mycomparator mc = new mycomparator();
Collections.sort(al, mc);
m.add(al.get(0).pos);
time_limit = al.get(0).end;
for (int i = 1; i < al.size(); i++) {
if (al.get(i).start > time_limit) {
m.add(al.get(i).pos);
time_limit = al.get(i).end;
}
}
for (int i = 0; i < m.size(); i++)
System.out.print(m.get(i) + 1 + " ");
}
public static void main(String[] args)
{
int s[] = { 1, 3, 0, 5, 8, 5 };
int f[] = { 2, 4, 6, 7, 9, 9 };
ArrayList meet = new ArrayList<>();
for (int i = 0; i < s.length; i++)
meet.add(new meeting(s[i], f[i], i));
maxMeeting(meet, meet.size());
}
}
Output:
1 2 4 5
MINIMISE THE SUM OF PRODUCT
You are given two arrays, A and B, of equal size N. The task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[N-1] * B[N-1], where shuffling of elements of arrays A and B is allowed.
Argument is the array A[] and array B[] and print the minimum sum.
Constraints:
1 <= Size of Arrays <= 107">107107
1 <= A[], B[] <= 1018">10181018
import java.io.*;
import java.util.*;
class GFG {
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));
}
}
Output
23
LARGEST NUMBER POSSIBLE
Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'.
Input: integers N and S, where N is the number of digits and S is the sum.
Print the largest number that is possible. If their is no such number, then print -1
Constraints:
1 <= N <= 50
0 <= S <= 500
Expected Time Complexity: O(n)
1.
class GFG
{
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
}
public static void main (String[] args)
{
int s = 9, m = 2;
findLargest(m, s);
}
}
Output
Largest number is 90
2.
class GFG
{
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
}
public static void main (String[] args)
{
int s = 20, m = 3;
findLargest(m, s);
}
}
Output
Largest number is 992
SMALLEST WINDOW IN A STRING CONTAINING ALL THE CHARACTERS OF ANOTHER STRING
Given a string S and text T. Output the smallest window in the string S having all characters of the text T. Both the string S and text T contains lowercase english alphabets.
Input: a string S and text T.
Output the smallest window of the string containing all the characters of the text. If such window doesn`t exist or this task can not be done then print -1.
Constraints:
1 <= |N|, |X| <= 1000
1.
public class GFG {
static final int no_of_chars = 256;
static String findSubString(String str, String pat)
{
int len1 = str.length();
int len2 = pat.length();
if (len1 < len2) {
System.out.println("No such window exists");
return "";
}
int hash_pat[] = new int[no_of_chars];
int hash_str[] = new int[no_of_chars];
for (int i = 0; i < len2; i++)
hash_pat[pat.charAt(i)]++;
int start = 0, start_index = -1,
min_len = Integer.MAX_VALUE;
int count = 0;
for (int j = 0; j < len1; j++) {
hash_str[str.charAt(j)]++;
if (hash_str[str.charAt(j)]
<= hash_pat[str.charAt(j)])
count++;
if (count == len2) {
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++;
}
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
if (start_index == -1) {
System.out.println("No such window exists");
return "";
}
return str.substring(start_index,
start_index + min_len);
}
public static void main(String[] args)
{
String str = "Timetopractice,toc";
String pat = "tist";
System.out.print(findSubString(str, pat));
}
}
Output :
toprac
2.
public class GFG {
static final int no_of_chars = 256;
static String findSubString(String str, String pat)
{
int len1 = str.length();
int len2 = pat.length();
if (len1 < len2) {
System.out.println("No such window exists");
return "";
}
int hash_pat[] = new int[no_of_chars];
int hash_str[] = new int[no_of_chars];
for (int i = 0; i < len2; i++)
hash_pat[pat.charAt(i)]++;
int start = 0, start_index = -1,
min_len = Integer.MAX_VALUE;
int count = 0;
for (int j = 0; j < len1; j++) {
hash_str[str.charAt(j)]++;
if (hash_str[str.charAt(j)]
<= hash_pat[str.charAt(j)])
count++;
if (count == len2) {
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++;
}
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
if (start_index == -1) {
System.out.println("No such window exists");
return "";
}
return str.substring(start_index,
start_index + min_len);
}
public static void main(String[] args)
{
String str = "zoomlazapzo,oza";
String pat = "tist";
System.out.print(findSubString(str, pat));
}
}
Output :
apzo
POWER OF 2
Given a positive integer N. The task is to check if N is a power of 2. That is N is 2x for some x.
Input: a single positive integer N.
Output: Print YES if it is a power of 2 else NO
Constraints:
1 <= T <= 100
0 <= N <=
import java.lang.Math;
class GFG {
static boolean isPowerOfTwo(int n)
{
if (n == 0)
return false;
return (int)(Math.ceil((Math.log(n) / Math.log(2))))
== (int)(Math.floor(
((Math.log(n) / Math.log(2)))));
}
public static void main(String[] args)
{
if (isPowerOfTwo(1))
System.out.println("Yes");
else
System.out.println("No");
if (isPowerOfTwo(98))
System.out.println("Yes");
else
System.out.println("No");
}
}
Output
Yes
No