Theprogrammersfirst | A technical portal.

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}...

Write a program to find largest and smallest number in an array.  Note - Time and space complexity efficient  /*   Find Largest and Smallest Number in an Array Example   This Java Example shows how to find largest and smallest number in an    array. */ public class FindLargestSmallestNumber {    public static void main(String[] args) {    //array of 10 numbers  int numbers[] = new int[]{32,43,53,54,32,65,63,98,43,23};    //assign first element of an array to largest and smallest  int smallest = numbers[0];  int largetst = numbers[0];    for(int i=1; i< numbers.length; i++)  {  if(numbers[i] > largetst)  largetst = numbers[i];  else if (numbers[i] < smallest)  smallest = numbers[i];    }    System.out.println("Largest Number is : " + largetst);  System.out.println("Smallest Number is : " + smallest);  } }   /* Output of this program wou...

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...

Given an integer K and an array arr[] consisting of N positive integers, the task is to find the number of subarrays whose sum modulo K is equal to the size of the subarray. Examples: Input: arr[] = {1, 4, 3, 2}, K = 3 Output: 4 Explanation: 1 % 3 = 1 (1 + 4) % 3 = 2 4 % 3 = 1 (3 + 2) % 3 = 2 Therefore, subarrays {1}, {1, 4}, {4}, {3, 2} satisfy the required conditions. Input: arr[] = {2, 3, 5, 3, 1, 5}, K = 4 Output: 5 Explanation: The subarrays (5), (1), (5), (1, 5), (3, 5, 3) satisfy the required condition. Naive Approach: The simplest approach is to find the prefix sum of the given array, then generate all the subarrays of the prefix sum array and count those subarrays having sum modulo K equal to the length of that subarray. Print the final count of subarrays obtained. Below is the implementation of the above approach: // C++ program of the above approach     #include <bits/stdc++.h>  using namespace std;     // Function that counts the suba...

Given an integer N, the task is to find an integer K such that the sum of the numbers formed by repeated removal of last digit of K is equal to N. Examples: Input: N = 136 Output: 123 Explanation: Click to enlarge The numbers formed by repeatedly removing the last digit of 123 are {123, 12, 1}. Therefore, the sum of these numbers = 123 + 12 + 1 = 136( = N). Input: N = 107 Output: 98 Explanation: The numbers formed by repeatedly removing the last digit of 98 are {98, 9}. Therefore, the sum of these numbers = 98 + 7 = 107( = N). Approach: The approach is based on the following observations: Consider K = 123. The possible numbers formed from 123 are 1, 12, and 123. Now, 123 can be expressed as 100 + 20 + 3. If all the other numbers are expressed similarly, then the idea is to know the position and frequency of each digit in all the numbers combined, to get the total sum as N. Digit Frequency of each digit Sum units tens hundreds 1 1 1 1 1*1 + 1*10 + 1*100 = 111 2 1 1 ...