The Coding Shala

Home >> Interview Questions >> first duplicate element In this post, we will discuss how to find first duplicate in an array and will implement its solution in Java. First Duplicate in an Array Problem Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1. Example 1: For a = [2, 1, 3, 5, 3, 2], the output should be firstDuplicate(a) = 3. There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3. First Duplicate in an Array Java Solution Approach 1: We can use HashSet. If a number repeat, we will return that. It will take an additional O(n) space to sto

Home >> LeetCode >> degree of an array LeetCode - Degree of an Array In this post, you will learn how to find the Degree of an Array. Here we will implement LeetCode's Degree of an array solution in Java. Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.  Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums. Example 1: Input: [1, 2, 2, 3, 1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. The subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: [1,2,2,3,1,4,2] Output: 6 Practice this problem on LeetCode: Click Here Degree of an Array Java Solution Approach 1: To solve this problem in need to count occurrences of each element in the array an

Home >> Interview Questions >> counting bits How to Count Set Bits in a Number In this post, you will learn how to count set bits or numbers of 1's in a given number. We will implement counting bits solution in Java. Given a non-negative integer number. For every number, i in the range 0 = i = num calculate the number of 1's in their binary representation and return them as an array. Example 1: Input: 2 Output: [0,1,1] Example 2: Input: 5 Output: [0,1,1,2,1,2] Counting Bits Java Solution Approach 1: Using Java's bitCount() method. Java Program:  class Solution { public int [] countBits ( int num ) { int [] ans = new int [ num + 1 ]; for ( int i = 0 ; i <= num ; i ++){ ans [ i ] = Integer . bitCount (( Integer ) i ); } return ans ; } } Approach 2: Let's denote the number as num. If it is even, the ending bit is 0, then that bit can be ignored, countBits(num) is the same as

Home >> Programming Questions >> N and its double Check if N and its Double Exist in an array In this post, we will learn how to check if N and its double exist in an array and will implement its solution in Java. Given an array arr of integers, check if there exist two integers N and M such that N is the double of M ( i.e. N = 2 * M). More formally check if there exists two indices i and j such that: i != jk 0 <= i, j < arr.length arr[i] == 2 * arr[j] Example 1: Input: arr = [10,2,5,3] Output: true Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5. Example 2: Input: arr = [7,1,14,11] Output: true Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7. Example 3: Input: arr = [3,1,7,11] Output: false Explanation: In this case does not exist N and M, such that N = 2 * M. Check N and its double exist Solution Approach: We can check this using HashSet. Check every number's double and if its divisible by two then check its half in the set.