The Coding Shala

Home >> Data Structures >> Implement Stack using Linked List  In this post, we will learn how to Implement Stack Using Linked List and will write a Java Program for the same. Implement Stack using Linked List We will implement Stack operations using LinkedList. If we implement using a linked list then the stack can grow and shrink dynamically but it requires extra memory because of pointers involvement. Java Program:  class MyStack { Node root ; //linked list node class Node { int data ; Node next ; Node ( int data ) { this . data = data ; } } boolean isEmpty () { return root == null ; } void push ( int x ) { Node newNode = new Node ( x ); //if stack is empty //make this as root node if ( root == null ) { root = newNode ; } else { ...

Home >> Data Structures >> Implement Stack Using Array  In this post, we will learn how to Implement Stack Using Array and will write a Java program for the same. Implement Stack Using Array We will implement Stack's operations using an array. If we use an array then it is easy to implement but the size limit is there. Java Program:  class MyStack { static final int MAX = 1000 ; int top ; int a []; boolean isEmpty () { return ( top < 0 ); } MyStack () { top = - 1 ; a = new int [ MAX ]; } void push ( int x ) { if ( top >= ( MAX - 1 )) { //stack overflow //return false or print error } else { a [++ top ] = x ; } } int pop () { if ( top < 0 ) { //stack underflow return - 1 ; } e...

Home >> Java Program >> Swap Two Numbers using XOR  In this post, we will learn how to Swap Two Numbers using XOR and will write a Java Program for the same. Java Program to Swap Two Numbers using XOR Swap two numbers without using an additional variable. Example: Input: a = 10;           b = 20; Output: a = 20;              b = 10; We can use XOR to swap the numbers. Java Program:  public class SwapTwoNumbers { public static void main ( String [] args ) { int a = 10 ; int b = 20 ; System . out . println ( "Before swap" ); System . out . println ( "a: " + a ); System . out . println ( "b: " + b ); //swap using xor a = a ^ b ; b = a ^ b ; a = a ^ b ; System . out . println ( "After swap" ); System . out . println ( "a: " + a ); System . out . println ( "b: " + b ); } } Output:  Before swap a: 10 b: 20 Af...

Home >> LeetCode >> Integer Replacement  In this post, we will learn how to solve LeetCode's Integer Replacement Problem and will implement its solution in Java. Integer Replacement Problem Given a positive integer n, you can apply one of the following operations: If n is even, replace n with n / 2. If n is odd, replace n with either n + 1 or n - 1. Return the minimum number of operations needed for n to become 1. Example 1: Input: n = 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1 Example 2: Input: n = 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1 Practice this problem on LeetCode . LeetCode - Integer Replacement Java Solution Approach 1 Using Bit Manipulation. If n is even then the operation is fixed. If n is odd then we have two operations +1 or -1, so for this let's check the binary of the number. We need to check only the second bit of the number. (from right side) Case 1. If the second bit is 1, t...

Home >> LeetCode >> Prime Number of Set Bits in Binary Representation  In this post, we will learn how to solve LeetCode's Prime Number of Set Bits in Binary Representation Problem and will implement its solution in Java. Prime Number of Set Bits in Binary Representation Problem Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation. Example 1: Input: L = 6, R = 10 Output: 4 Explanation: 6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 9 -> 1001 (2 set bits , 2 is prime) 10->1010 (2 set bits , 2 is prime) Practice this problem on LeetCode . LeetCode - Prime Number of Set Bits in Binary Representation Java Solution Approach 1 First count set bits in number then check if it's prime or not. Java Program:  class Solution { public boolean isPrime ( int num ) { if ( num < 2 ) return false ; ...

Home >> LeetCode >> Number Complement  In this post, we will learn how to solve LeetCode's Number Complement Problem and will implement its solution in Java. Number Complement Problem Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation. Example 1: Input: num = 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. Practice this problem on LeetCode . LeetCode - Number Complement Java Solution Approach 1 Just flip the bit and make decimal value from it. Java Program:  class Solution { public int findComplement( int num) { int ans = 0 ; int two = 1 ; while (num > 0 ) { // if bit is 0 then flip and make binary of result if (num % 2 == 0 ) { ans += two; } two *= 2 ; num...

Home >> Programming >> Hamming Distance  In this post, we will learn how to find Hamming Distance between two integers and will implement its solution in Java. Hamming Distance The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Example 1: Input: x = 1, y = 4 Output: 2 Explanation: 1   (0 0 0 1) 4   (0 1 0 0) Hamming Distance Java Program Approach 1 First find the XOR or both number then check bits, if 1 than increase count by 1. Java Program:  class Solution { public int hammingDistance( int x, int y) { x = x ^ y; int dis = 0 ; for ( int i = 0 ; i < 32 ; i ++ ) { if (((x >> i) & 1 ) == 1 ) dis ++ ; } return dis; } } Other Posts You May Like Power of Two Power of Three LeetCode - Single Number Find XOR from 1 t...

Home >> LeetCode >> XOR Operation in an Array  In this post, we will learn how to solve LeetCode's XOR Operation in an Array Problem and will implement its solution in Java. XOR Operation in an Array Problem Given an integer n and an integer start. Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length. Return the bitwise XOR of all elements of nums. Example 1: Input: n = 5, start = 0 Output: 8 Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8. Where "^" corresponds to the bitwise XOR operator. LeetCode - XOR Operation in an Array Java Solution Approach 1 Simple Math and xor operation. Java Program:  class Solution { public int xorOperation ( int n , int start ) { int res = start ; for ( int i = 1 ; i < n ; i ++) { res ^= start + 2 * i ; } return res ; } } Other Posts You May Like LeetCode - Number...

Home >> LeetCode >> Number of Steps to Reduce a Number to Zero  In this post, we will learn how to solve LeetCode's Number of Steps to Reduce a Number to Zero problem and will implement its solution in Java. Number of Steps to Reduce a Number to Zero Problem Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it. Example 1: Input: num = 14 Output: 6 Explanation:  Step 1) 14 is even; divide by 2 and obtain 7.  Step 2) 7 is odd; subtract 1 and obtain 6. Step 3) 6 is even; divide by 2 and obtain 3.  Step 4) 3 is odd; subtract 1 and obtain 2.  Step 5) 2 is even; divide by 2 and obtain 1.  Step 6) 1 is odd; subtract 1 and obtain 0. Practice this problem on LeetCode . LeetCode - Number of Steps to Reduce a Number to Zero Java Solution Approach 1 A simple iterative approach using the loop. Java Program:  ...

Home >> LeetCode >> Find the Difference  In this post, we will learn how to solve LeetCode's Find the Difference Problem and will implement its solution in Java. Find the Difference Problem You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t. Example 1: Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter that was added. Practice this problem on LeetCode . LeetCode - Find the Difference Java Solution Approach 1 Using HashMap. Java Program:  class Solution { public char findTheDifference ( String s , String t ) { Map < Character , Integer > map = new HashMap <>(); for ( int i = 0 ; i < s . length (); i ++) { if ( map . containsKey ( s . charAt ( i ))) { map . put ( s . charAt ( i ), map . get ( s ....

Home >> LeetCode >> Binary Number with Alternating Bits  In this post, we will learn how to solve LeetCode's Binary Number with Alternating Bits Problem and will implement its solution in Java. Binary Number with Alternating Bits Problem Given a positive integer, check whether it has alternating bits: namely if two adjacent bits will always have different values. Example 1: Input: n = 5 Output: true Explanation: The binary representation of 5 is: 101 Example 2: Input: n = 7 Output: false Explanation: The binary representation of 7 is: 111. LeetCode - Binary Number with Alternating Bits Java Solution Approach 1 Compare alternate bits. Java Program:  class Solution { public boolean hasAlternatingBits ( int n ) { int i = 31 ; //find first 1 bit from left side while ((( n >> i ) & 1 ) == 0 ) i --; int prevBit = ( n >> i ) & 1 ; i --; while ( i >...