Project 2
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 <= 107107
1 <= Ai <= 1010
ANS:-
package DS;
public class SubArraySum {
public static int[] subArraySum(int[] a, int s) {
int start =0, end = 0, currSum = a[0];
while (end < a.length) {
if (currSum == s) {
return new int[] {start,end};
}
if (currSum > s) {
currSum -= a[start++];
}else {
end++;
if(end >= a.length) {
break;
}
currSum += a[end];
}
}
return new int[]{-1};
}
}
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
ANS:-
package DS;
import java.util.Scanner;
public class PermutationGivenString {
static void permutation(String prefix,String str) {
int n = str.length();
if (n == 0) {
System.out.println(prefix);
}else {
for(int i=0; i<n; i++) {
permutation(prefix + str.charAt(i), str.substring(9,i) + str.substring(i + 1,n));
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
permutation("",s);
}
}
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
ANS:-
package DS;
public class TreeNode {
int data;
TreeNode right;
TreeNode(int data){
this.data = data;
left = null;
right = null;
}
}
class Solution{
public boolean isIdentical(TreeNode root1,TreeNode root2) {
if(root1 == null && root2 == null)
return true;
if (root1 == null || root2 == null)
return false;
if(root1.data != root2.data)
return false;
return isIdentical(root1.left,root2.left) && isIdentical(root1.right,root2.right);
}
}
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.
ANS:-
package DS;
public class Node{
int data;
Node left,right;
Node(int item)
{
data=item;
left=right=null;
}
}
class BinaryTree{
static int index =0;
Node constructTree(String s)
{
if(index == s.length() || s.charAt(index) == 'N')
{
index++;
return null;
}
Node root = new Node(Character.getNumericValue(s.charAt(index)));
index++;
root.left = constructTree(s);
root.right = constructTree(s);
return root;
}
int countLeaves(Node node)
{
if(node == null)
return 0;
if(node.left == null && node.right == null)
return -1;
else
return countLeaves(node.left)+ countLeaves(node.right);
}
}
public class Main{
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
String s = "1 10 5 39 N N N";
Node root = tree.constructTree(s);
System.out.println("The number of Leaves is:" + tree.countLeaves(root));
}
}
COUNT LEAVES IN BINARY TREE
For the above tree, the string will be: 5 2 3 1 N 7 4 N 8 N 6 N N Complete the function countLeaves() that takes the tree string as parameter and returns the count of leaves in tree.
Constraints:
1<= N <= 104
ANS:-
package DS;
import java.util.Queue;
public class Node {
int val;
Node left;
Node right;
public int countLeaves(String tree) {
if (tree == null || tree.lenght() == 0) {
return 0;
}
String[] nodes = tree.split( " ");
Queue<Node> queue = new LinkedList<>();
int index =0;
Node root = new Node(Integer.parseInt(nodes[index++]));
queue.offer(root);
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (nodes[index].equals("N")) {
curr.left = null;
}else {
curr.left = new Node(Integer.parseInt(nodes[index]));
queue.offer(curr.left);
}
index++;
if(nodes[index].equals("N")) {
curr.right = null;
}else {
curr.right = new Node(Integer.parseInt(nodes[index]));
queue.offer(curr.right);
}
index++;
}
return countLeaves(root);
}
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
ANS:-
package DS;
public class Node{
int data;
Node left,right;
Node(int data){
this.data = data;
left = right = null;
}
}
class BinaryTree{
Node root;
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;
}
}
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
ANS:-
package DS;
public class Node {
int data;
Node next;
Node(int data){
this.data = data;
this.next = null;
}
}
class LinkedList{
static Node segregate(Node head) {
int count0 = 0,count1 = 0, count2 = 0;
Node ptr = head;
while (ptr != null) {
if(ptr.data == 0) {
count0++;
}else if (ptr.data ==1) {
count1++;
}else {
count2++;
}
ptr = ptr.next;
}
ptr = head;
while(count0 > 0) {
ptr.data =0;
ptr = ptr.next;
count0--;
}
}
}
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
ANS:-
package DS;
import java.util.HashMap;
public class FirstRepeatedCharacter {
public static char firstRepeatedCharacter(String s) {
HashMap<Character,Integer> map = new HashMap<>();
for(int i=0; i<s.length();i++){
char c = s.charAt(i);
if(map.containsKey(c)) {
return c;
}
map.put(c, i);
}
return '-1';
}
}
CHECK IF TWO ARRAYS ARE EQUAL OR NOT
Complete the function which takes two arrays A and B of equal size. Find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though. If there are repetitions, then counts of repeated elements must also be same for two array to be equal.
Print 1 if the arrays are equal else print 0.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 107107
1 <= A[],B[] <= 1018
ANS:-
package DS;
public class Main2 {
public static void main(String[] args) {
int[] array1 = {1,2,3};
int[] array2 = {1,2,3};
int n = array1.length;
boolean equal = true;
for(int i =0;i<n; i++) {
if (array1[i] != array2[i]) {
equal = false;
break;
}
}
if (equal) {
System.out.println(1);
}else {
System.out.println(0);
}
}
}
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
ANS:-
package DS;
import java.util.*;
public class Main3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m=sc.nextInt();
int[] a1 = new int[n];
int[] a2 = new int[m];
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<n;i++) {
a1[i] = sc.nextInt();
}
for(int i=0; i<m; i++) {
a2[i] = sc.nextInt();
map.put(a2[i],i);
}
Arrays.sort(a1,(x,y) -> {
if(map.containsKey(x) && map.containsKey(y)) {
return map.get(x) - map.get(y);
}else if (map.containsKey(x)) {
return -1;
}else if (map.containsKey(y)) {
return 1;
}else {
return x-y;
}
});
SHORTEST SOURCE TO DESTINATION PATH
Given a boolean 2D matrix (0-based index), find whether there is path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. You may move in only four direction ie up, down, left and right. The path can only be created out of a cell if its value is 1.
Complete the function for implementing this. Arguments are two integers n and m denoting the size of the matrix, an n*m matrix and two integers x and y denoting the index of the destination. Print the min no of steps needed to reach the destination.
Constraints:
1<=n,m<=20
ANS:-
package DS;
import java.util.*;
public class Pair {
int x;
int y;
int steps;
Pair(int x, int y, int steps){
this.x=x;
this.y=y;
this.steps = steps;
}
}
class Main{
static int n,m;
static int[][] matrix;
static boolean[][] visited;
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
static boolean isValid(int x,int y) {
return x >=0 && x < n && y >= 0 && y < m && matrix[x][y] == 1 && !visited[x][y];
}
static int shortestPath(int n, int m, int[][] matrix, int x, int y) {
Main.n = n;
Main.m = m;
Main.matrix = matrix;
visited = new boolean[n][m];
Queue<Pair> q = new LinkedList <>();
q.offer(new Pair(0,0,0));
visited[0][0] = true;
while (!q.isEmpty()) {
Pair p = q.poll();
if (p.x == x && p.y == y) {
return p.steps;
}
for (int i=0; i<4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (isValid(nx,ny)) {
q.offer(new Pair(nx,ny,p.steps + 1));
visited[nx][ny] = true;
}
}
}
return -1;
}
MINIMUM COST PATH
Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum. You can move in 4 directions : up, down, left an right. It is assumed that negative cost cycles do not exist in input matrix.
N denoting the size of the grid N*N integer matrix depicting the cost of respective cell from (0,0) to (N,N).
output a single integer depicting the minimum cost to reach the destination.
Constraints:
1 <= N <= 100
1 <= grid[i][j] <= 104
ANS:-
package DS;
public class MinCost {
public int minCost(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][]dp = new int[n][m];
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (i==0 && j == 0) {
dp[i][j] = grid[i][j];
}else if (i == 0) {
dp[i][j] = dp[i][j-1] + grid[i][j];
}else if (j == 0) {
dp[i][j] = dp[i-1][j] + grid[i][j];
}else {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
}
}
}
return dp[n-1][m-1];
}
}
CIRCLE OF STRINGS
Given an array of strings A[], determine if the strings can be chained together to form a circle. A string X can be chained together with another string Y if the last character of X is same as first character of Y. If every string of the array can be chained, it will form a circle.
For eg for the array arr[] = {“great", “skill", “trains", “lync"} the answer will be Yes as the given strings can be chained as “great", “trains", “skill" and “lync"
Input: array A[].
Output: If chain can be formed, then print 1, else print 0.
Constraints
0 <= size of A <= 30
0 <= A[i] <= 10
ANS:-
package DS;
public class GRAPH {
private int V;
private List<Integer>[] adjList;
GRAPH(int v){
V = v;
adjList = new ArrayList[V];
for(int i=0; i< V; i++)
adjList[i] = new ArrayList<>();
}
void addEdge(int u, int v) {
adjList[u].add(v);
}
private boolean DFS(int v, boolean[] visited,int parent) {
visited[v] = true;
for(int i : adjList[v]) {
if (!visited[i]) {
if(DFS(i,visited,v))
return true;
}
else if(i != parent)
return true;
}
return false;
}
boolean isCyclic() {
boolean[] visited = new boolean[V];
for(int i =0; i<V; i++)
if (!visited[i])
if (DFS(i,visited,-1))
return true;
return false;
}
class Main{
static int index(String[] arr,String s) {
for (int i=0; i<arr.length; i++)
if (arr[i].equals(s))
return i;
return -1;
}
static int chain(String[] arr) {
int n = arr.length;
GRAPH g = new GRAPH(n);
for(int i=0; i<n; i++) {
for(int j=1+1; j<n; j++) {
if(arr[i].charAt(arr[i].length()-1)== arr[j].charAt(0)){
g.addEdge(i,j);
g.addEdge(j, i);;
}
}
}
return g.isCyclic() ? 1 :0;
}
public static void main(String[] args) {
String[] arr= {"great","skill","trains","lync"};
System.out.println(chain(arr));
}
}
}
Stacks queues
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
ANS:-
package DS;
import java.util.HashMap;
import java.util.Stack;
public class FirstNonRepeatingCharacter {
public static void findFirstNonRepeatingCharacter(char[] stream) {
Stack<Character> stack = new Stack<>();
HashMap<Character,Integer> count = new HashMap<>();
for(char c: stream) {
if(count.containsKey(c)) {
count.put(c, count.get(c)+1);
stack.remove(c);
}else {
count.put(c, 1);
stack.push(c);
}
if(stack.isEmpty()) {
System.out.println(-1);
}else {
System.out.println(stack.peek());
}
}
}
public static void main(String[] args) {
char[] stream = {'a','b','c','d','a','c','e'};
findFirstNonRepeatingCharacter(stream);
}
}
REARRANGE CHARACTERS
Given a string S with repeated characters (only lowercase). The task is to rearrange characters in a string such that no two adjacent characters are same. It may be assumed that the string has only lowercase English alphabets.
Complete the function which takes the argument as a string of lowercase English alphabets and prints 1 if the generated string doesn't contain any same adjacent characters, else if no such string is possible to be made print 0
Constraints:
1 <= length of string <= 104
ANS:-
package DS;
import java.util.HashMap;
public class RearrangeCharacter {
static boolean canRearrange(String str) {
int n = str.length();
int[] count = new int[26];
for(int i=0; i<n; i++)
count[str.charAt(i) - 'a']++;
int maxCount =0;
for(int i=0; i<26; i++)
maxCount = Math.max(maxCount, count[i]);
return maxCount <= (n+1)/2;
}
public static void main(String[] args) {
String str = "abbbc";
if (canRearrange(str))
System.out.println("1");
else
System.out.println("0");
}
}
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”}.
ANS:-
package DS;
public class LCSdynamic {
public static String LCS(String X, String Y) {
int m = X.length();
int n = Y.length();
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m; i++) {
for (int j = 1; j<= n; j++) {
if(X.charAt(i-1) == Y.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1]+1;
}else {
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
int i = m, j=n;
StringBuilder sb = new StringBuilder();
while (i>0&& j>0) {
if(X.charAt(i-1)== Y.charAt(j-1)) {
sb.append(X.charAt(i-1));
i--;
j--;
}else if (dp[i-1][j] > dp[i][j-1]) {
i--;
}else {
j--;
}
}
return sb.reverse().toString();
}
}
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.
ANS:-
package DS;
public class MaxSumIS {
public static int maxSumIS(int arr[],int n)
{
int dp[] = new int[n];
int max = 0;
for (int i=0; i<n; i++)
dp[i] = arr[i];
for(int i=1; i<n; i++)
for(int j=0; j<1; j++)
if(arr[i]> arr[j] && dp[i]<dp[j] + arr[i])
dp[i] = dp[j] + arr[i];
for(int i=0; i<n; i++)
if(max < dp[i])
max = dp[i];
return max;
}
}
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
ANS:-
package DS;
public class countWays {
public static int countWays(int n){
int[] dp = new int[n+1];
dp[0] =1;
dp[1] = 1;
dp[2] =2;
for(int i=3; i<=n; i++) {
dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
}
return dp[n];
}
}
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
ANS:-
package DS;
import java.util.Arrays;
import java.util.ArraysList;
import java.util.List;
public class NMeetings {
public static void main(String[] args) {
int[] S = {1,3,0,5,8,5};
int[] F = {2,4,6,7,9,9};
System.out.println(maxMeetings(S,F));
}
static class Meeting implements Comparable<Meeting>{
int start;
int finish;
int index;
Meeting(int start,int finish,int index){
this.start = start;
this.finish = finish;
this.index =index;
}
public int compareTo(Meeting m) {
return this.finish - m.finish;
}
}
static int maxMeetings(int[] S, int[] F) {
int n = S.length;
Meeting[] meetings = new Meeting[n];
for(int i=0; i<n; i++) {
meetings[i]=new Meeting(S[i],F[i],i+1);
}
Arrays.sort(meetings);
int finishTime =0;
int counr =0;
List<Integer> order = new ArrayList<>();
for(int i =0; i<n; i++) {
if(meetings[i].start>= finishTime) {
finishTime = meetings[i].finish;
count++;
order.add(meetings[i].index);
}
}
System.out.println(order);
return count;
}
}
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 <= 107107
1 <= A[], B[] <= 1018
ANS:-
package DS;
import java.util.Arrays;
public class MiniMizeSum {
public static int minimizeSumOfProduct(int[] A, int[] B) {
Arrays.sort(A);
Arrays.sort(B);
int sum =0;
for(int i =0; i<A.length; i++) {
sum += A[i] * B[A.length - i -1];
}
return sum;
}
public static void main(String[] args) {
int[] A = {...};
int[]B = {...};
System.out.println(minimizeSumOfProducts(A,B));
}
}
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)
ANS:-
package DS;
public class LargestNumber {
public static void main(String[] args) {
int N = 3, S = 29;
StringBuilder result = new StringBuilder();
if (S>N *9) {
System.out.println(-1);
return;
}
for(int i=0; i<N; i++) {
if(S>=9) {
result.append("9");
S-= 9;
}else {
result.append(S);
S=0;
}
}
System.out.println(result);
}
}
LONGEST DISTINCT CHARACTERS IN STRING
Given a string S, find length of the longest substring with all distinct characters. For example, for input "abca", the output is 3 as "abc" is the longest substring with all distinct characters.
Input: String s.
Print length of smallest substring with maximum number of distinct characters.
Constraints:
1 ≤ size of str ≤ 10000
ANS:-
package DS;
public class LongestSubString {
public static int longestSubString(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans =0,i=0,j=0;
while (i<n&& j<n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
ans = Math.max(ans,j-i);
}else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
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
ANS:-
package DS;
import java.util.HashMap;
public class SmallestWindow {
public static String smallestWindow(String s, String t) {
if (s.length()<t.length()) return "-1";
HashMap<Character,Integer> target = new HashMap<>();
for(char c : t.toCharArray()) target.put(c, target.GETOrDefault(c,0)+1);
int left =0,right =0, count =0, minLen = Integer.MAX_VALUE;
int start =0;
HashMap<Character,Integer> window = new HashMap<>();
while (right < s.length()) {
char c = s.charAt(right);
if(target.containsKey(c)) {
window.put(c, window.getOrDefault(c,0)+1);
if(window.get(c).intValue()== target.get(c).intValue()) count++;
}
right++;
while (count == target.size()) {
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char d=s.charAt(left);
if(target.containsKey(d)) {
window.put(d, window.get(d)-1);
if(window.get(d).intValue()< target.get(d).intValue())count--;
}
left++;
}
}
}
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 <= 1018
ANS:-
package DS;
public class PowerOf2 {
public static void main(String[] args) {
int N = 16;
if(N>0 && (N & (N -1)) ==0) {
System.out.println("YES");
}else {
System.out.println("No");
}
}
}