Theprogrammersfirst | A technical portal.

Subset Sum Problem with Negative Numbers Description: Given an array of integers that can include negative numbers, determine if there is a subset with a sum equal to a given target sum. Input: An array of integers arr[] and a target sum target . Output: Return true if there is a subset with a sum equal to the target sum; otherwise, return false . Example: Input: arr = [-1, 2, 3, 4] , target = 6 Output: true (Subset [-1, 2, 3, 4] has a sum of 6)   Solution: Subset Sum Problem with Negative Numbers java Copy code public class SubsetSumWithNegatives { public static boolean isSubsetSum ( int [] arr, int target) { int sum = Arrays.stream(arr).sum(); if (target > sum || (sum + target) % 2 != 0 ) return false ; target = (sum + target) / 2 ; boolean [] dp = new boolean [target + 1 ]; dp[ 0 ] = true ; for ( int num : arr) { for ( int j = target; j >= num; j--) { dp[j] = dp[j]...

  Description: Given an array of integers and a target sum, find the number of subsets that sum up to the target sum. Input: An array of integers arr[] and a target sum target . Output: Return the number of subsets with a sum equal to the target sum. Example: Input: arr = [1, 2, 3, 3] , target = 6 Output: 2 (Subsets [1, 2, 3] and [3, 3] have a sum of 6) Solution: Count of Subsets with Given Sum java Copy code public class SubsetSumCount { public static int countSubsets ( int [] arr, int target) { int [][] dp = new int [arr.length + 1 ][target + 1 ]; // Initialize for ( int i = 0 ; i <= arr.length; i++) { dp[i][ 0 ] = 1 ; } // Fill the dp table for ( int i = 1 ; i <= arr.length; i++) { for ( int j = 1 ; j <= target; j++) { if (arr[i - 1 ] <= j) { dp[i][j] = dp[i - 1 ][j] + dp[i - 1 ][j - arr[i - 1 ]]; ...

  Description: Given an array of integers, determine if there is a subset with a sum equal to a given target sum. Input: An array of integers arr[] and a target sum target . Output: Return true if there is a subset with sum equal to the target sum; otherwise, return false . Example: Input: arr = [3, 34, 4, 12, 5, 2] , target = 9 Output: true (Subset [3, 4, 2] has a sum of 9) Solution: Basic Subset Sum Problem java: import java.util.*; public class SubsetSum { public static boolean isSubsetSum ( int [] arr, int target) { boolean [][] dp = new boolean [arr.length + 1 ][target + 1 ]; // Initialize for ( int i = 0 ; i <= arr.length; i++) { dp[i][ 0 ] = true ; } // Fill the dp table for ( int i = 1 ; i <= arr.length; i++) { for ( int j = 1 ; j <= target; j++) { if (arr[i - 1 ] <= j) { dp[i][j] = dp[i - 1 ][j] || dp...

Given a matrix, mat[][] of size N * M, the task is to find the minimum count of operations required to make all elements of at least one row of the given matrix prime. In each operation, merge any two rows of the matrix based on the following conditions: If kth elements of both rows of the matrix, i.e, mat[i][k] and mat[j][k] are prime numbers or composite numbers then kth element of the merged row contains min(mat[i][k], mat[j][k]). Otherwise, kth element of the merged row contains the element which is prime. If it is not possible to get all elements of a row as prime numbers, then print -1. Examples: Input: mat[][] = { { 4, 6, 5 }, { 2, 9, 12 }, { 32, 7, 18 }, { 12, 4, 35 } } Output: 2 Explanation: Merging mat[0] and mat[1] modifies mat[][] to { { 2, 6, 5 }, { 32, 7, 18 }, { 12, 4, 35 } } Merging mat[0] and mat[1] modifies mat[][] to { { 2, 7, 5 }, { 12, 4, 35 } } Since first row of the matrix consists only of prime numbers, the required output is 2. Input: mat[][] = { {4, 6}, {8, 3}...

The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation     Fn = Fn-1 + Fn-2 with seed values    F0 = 0 and F1 = 1. Given a number n, print n-th Fibonacci Number. Examples: Input  : n = 2 Output : 1 Input  : n = 9 Output : 34 Write a function int fib(int n) that returns Fn. For example, if n = 0, then fib() should return 0. If n = 1, then it should return 1. For n > 1, it should return Fn-1 + Fn-2 For n = 9 Output:34 Following are different methods to get the nth Fibonacci number. Method 1 ( Use recursion ) A simple method that is a direct recursive implementation mathematical recurrence relation given above. //Fibonacci Series using Recursion  class fibonacci  {      static int fib(int n)      {      if (n <= 1)      ...

Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. kadane-algorithm Kadane’s Algorithm: Initialize:     max_so_far = 0     max_ending_here = 0 Loop for each element of the array   (a) max_ending_here = max_ending_here + a[i]   (b) if(max_so_far < max_ending_here)             max_so_far = max_ending_here   (c) if(max_ending_here < 0)             max_ending_here = 0 return max_so_far Explanation: Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far     Lets take the example:     {-2, -3, 4...

Given a matrix m[][] of dimensions N × M and an integer K, calculate XOR(i, j) which is equal to the Bitwise Xor of all elements of submatrix from indices (1, 1) to (i, j)), for every indices of the matrix. The task is to find the submatrix {(1, 1), …, (i, j)} having Kth maximum XOR(i, j) value. If multiple such submatrices exists, then print the smallest one. Note: Consider the starting index of the matrix from (1, 1). Examples: Input: m[][] = {{1, 2}, {2, 3}}, K = 2 Output: 1 2 Explanation: XOR(1, 1) : m[1][1] = 1 XOR(1, 2): m[1][1] xor m[1][2] = 3 XOR(2, 1): m[1][1] xor m[2][1] = 3 XOR(2, 2): m[1][1] xor m[1][2] xor m[2][1] xor m[2][2] = 2 Hence, the 2nd maximum value is 3 at position [1, 2]. Input: m[][] = {{1, 2, 3}, {2, 2, 1}, {2, 4, 2} }, k = 1 Output: 3 2 Approach: The idea is to find XOR (i, j) using Dynamic Programming. Calculate the bitwise XOR(i, j) as xor[i][j] = xor[i-1][j] ^ xor[i][j-1] ^ xor[i-1][j-1] ^ m[i][j]. Store the XOR(i, j) values obtained for respective indices...

Given an 2D array arr[][] consisting of N pairs of integers, the task is to find the pair which covers all other pairs of the given array. If it is impossible to find such a pair, then print -1. A pair {a,  b} will cover another pair {c,  d}, if the condition (a ≤ c ≤ d ≤ b) holds true. Examples: Input: arr[][2] = {{2, 2}, {3, 3}, {3, 5}, {4, 5}, {1, 1}, {1, 5}} Output: 6 Explanation: There exist a pair (1, 5) which cover all other pair because all other pair lies in the pair {1, 5}. Therefore, the position of the pair {1, 5} is 6. So, the output is 6. Input: arr[][] = {{1, 20}, {2, 22}, {3, 18}} Output: -1 Explanation: No such pair exists which covers all the remaining pairs. Therefore, the output is -1 Naive Approach: The simplest approach is to compare each pair with all other pairs and check if any pair covers all the pairs or not. Below are the steps: Initialize a variable count = 0 which stores the number pairs that lie between the current pair. Traverse the array of pairs and fo...

Given an array arr[] consisting of N positive integers and an integer K, which represents the maximum number that can be added to the array elements. The task is to maximize the length of longest possible subarray of equal elements by adding atmost K. Examples: Input: arr[] = {3, 0, 2, 2, 1}, k = 3 Output: 4 Explanation: Step 1: Adding 2 to arr[1] modifies array to {3, 2, 2, 2, 1} Step 2: Adding 1 to arr[4] modifies array to {3, 2, 2, 2, 2} Therefore, answer will be 4 ({arr[1], …, arr[4]}). Input: arr[] = {1, 1, 1}, k = 7 Output: 3 Explanation: All array elements are already equal. Therefore, the length is 3. Approach: Follow the steps below to solve the problem: Sort the array arr[]. Then, use Binary Search to pick a possible value for the maximum indices having the same element. For each picked_value, use the Sliding Window technique to check if it is possible to make all elements equal for any subarray of size picked_value. Finally, print the longest possible length of subarray obta...

Given a string, we have to find out all subsequences of it. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order. Examples: Input : abc Output : a, b, c, ab, bc, ac, abc Input : aaa Output : a, aa, aaa Method 1 (Pick and Don’t Pick Concept) import java.util.*;  class GFG {         // creating a public static Arraylist such that      // we can store values      // IF there is any question of returning the      // we can directly return too// public static ArrayList<String> al = new ArrayList<String>();      public static void main(String[] args)      {          String s = "abcd";          findsubsequences(s, ""); // Calling a function          System.out.println(al);      }       ...

Given an integer K and a numeric string str, the task is to find the longest subsequence from the given string which is divisible by K. Examples: Input: str = “121400”, K = 8 Output: 121400 Explanation: Since the whole string is divisible by 8, the entire string is the answer. Input: str: “7675437”, K = 64 Output: 64 Explanation: The longest subsequence from the string which is divisible by 64, is “64” itself. Approach: The idea is to find all subsequences of the given string and for each subsequence, check if its integer representation is divisible by K or not. Follow the steps below to solve the problem: Traverse the string. For every character encountered, two possibilities exists. Either consider the current character in the subsequence or not. For both the cases, proceed to the next characters of the string and find the longest subsequence that is divisible by K. Compare the longest subsequences obtained above with the current maximum length of longest subsequence and update accor...

Given an array arr[] consisting of N integers, the task is to find the maximum Bitwise XOR from all the possible pairs in the given array. Examples: Input: arr[] = {25, 10, 2, 8, 5, 3} Output: 28 Explanation: The maximum result is 5^25 = 28. Input: arr[] = {1, 2, 3, 4, 5, 6, 7} Output: 7 Explanation: The maximum result is 1^6 = 7. Naive Approach: Refer to the article Maximum XOR of Two Numbers in an Array for the simplest approach to solve the problem by generating all pairs of the given array and computing XOR of each pair to find the maximum among them. Time Complexity: O(N2) Auxiliary Space: O(1) Bitmasking Approach:  Refer to the article Maximum XOR of Two Numbers in an Array to solve the problem using Bitmasking. Time Complexity: O(N*log M), where M is the maximum number present in the array  Auxiliary Space: O(N) Efficient Approach: The above approach can be solved by using Trie by inserting the binary representation of the numbers in the array arr[]. Now iterate the bin...