Programming Blog

Java Solution for finding Non Divisible Subset in Given Array Problem Description : Given a set of distinct integers, print the size of a maximal subset of S where the sum of any 2 numbers in S' is not evenly divisible by k. Example 1 : S = [19, 10, 12, 10, 24, 25, 22], k = 4 Output = 3 One of the arrays that can be created is S'[0] = [10, 12, 25] Another is S'[1] = [19, 22, 24]. After testing all permutations, the maximum length solution array has 3 elements. Example 2 : S = [1, 7, 2, 4], k = 3 Output = 3 [1, 7, 4] Example 3 : S = [278, 576, 496, 727, 410, 124, 338, 149, 209, 702, 282, 718, 771, 575, 436], k = 7 Output = 11 In simple word, we have to find maximum subset of current array where it can not be divisible by given k. Lets jump on code. Solution 1 : Java Solution for finding Non Divisible Subset in Given Array import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.funct...

Search Minimum number in Rotated and Sorted Array in Java using Binary Search Problem Description : Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [5, 6, 7, 0, 1, 2, 4] if it was rotated 3 times. [2, 4, 5, 6, 7, 0, 1] if it was rotated 5 times. Example 1 : Input : [5, 6, 7, 0, 1, 2, 4] Output : 0 Example 2 : Input : [5, 8, 10, 15, 20, 50, 100, 200] Output : 5 Example 3 : Input : [100, 50, 25, 5, 1] Output : 1 We will use Binary Search for finding solution. Solution 1 : Find Minimum Element in Rotated Sorted Array in Java   import   java . util . Scanner ;   public   class   FindMinimumInRotatedSortedArray   {      public   static   void   main ( String []   args )   {                   Scanner   sc   =   new ...

Java Solution for Forming a Magic Square Problem | HackerRank Problem Problem Description : We define a to be an n * n matrix of distinct positive integers from 1 to n^2 where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant . You will be given a 3 * 3 matrix of integers in the inclusive range [1, 9]. We can convert any digit 'a' to any other digit 'b' in the range [1, 9] at cost of |a - b|. Given s, convert it into a magic square at minimal cost. Print this cost on a new line. In recreational mathematics, a square array of numbers, usually positive integers, is called a magic square if the sums of the numbers in each row, each column, and both main diagonals are the same. There are 8 ways to make a 3×3 magic square . See below image for reference. Example 1 : Input : 5 3 4 1 5 8 6 4 2 Output : 7  8 3 4 1 5 9 6 7 2 This took three replacements at a cost of |5 - 8| + |8 - 9| + |4 - 7| = 3 + 1 + 3 = 7. Exa...

Search target element in Rotated and Sorted Array in Java with explanation Problem Description : Given a sorted and rotated array nums[] of size N and a target, the task is to find the target in the nums[] array. Array is sorted but it is also rotated. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Example 1 : Input:  nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2 : Input: nums = [4,5,6,7,0,1,2], target = 8 Output: -1 Example 3 : Input: nums = [1,2,3,4,6,8,12,15], target = 2 Output : 1 Example 4 : Input: nums = [2, 4, 8, 16, 32, 0, 1], target = 5 Output: -1 Here we can use binary search, but given array is rotated so we have to apply extra logic with binary search. Solution 1 : Searching target element from rotated sorted array in Java import   java . util . Scanner ; public   class   SearchInRotatedSortedArray   {      public   static   void   main ( String []   args ...

Find First and Last Index Occurrence of given target from Java Array using Binary Search Problem Description : Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1] . Example 1 : Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 8 Output: [3, 5] Example 2 : Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 6 Output: [-1, -1] We can solve this problem using brute force approach but it will take more time than binary search. So lets see binary search approach. Solution 1 : Finding First and Last Position of Element in Array. import   java . util . Scanner ; public   class   FindFirstAndLastPosition   {      public   static   void   main ( String []   args )   {          Scanner   sc   =   new   Scanner ( System . in );   ...

Return all unique triplets sum to given target | Leetcode Problem Problem Description : Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j , i != k , and j != k , and nums[i] + nums[j] + nums[k] == 0 . Example 1 : Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. The order of the output and the order of the triplets does not matter. Example 2 : Input: nums = [0,1,1] Output: [] Explanation: Any triplet does not sum up to 0. Here we can solve this problem using two pointer approach.  Solution 1 : Java solution for finding triplets sum to given target import   java . util . ArrayList ; import   java . util . Arrays ; import   java . util . List ; import   java . util . Scanner ; public ...