Competitive Programming

Sum of Each Column of a Matrix: Program: import java.util.Scanner; public class MatrixColumnSum { public static void main(String[] args) { int r, c; Scanner s = new Scanner(System.in); r = s.nextInt(); c = s.nextInt(); int[][] matrix = new int[r][c]; for(int i = 0; i<r; i++) { for(int j = 0; j<c;j++) { matrix[i][j] = s.nextInt(); } } int sum = 0; for(int j = 0; j<c; j++) { sum = 0; for(int i = 0;i<r; i++) { sum += matrix[i][j]; } System.out.println(j+1 + "  " + "Column sum is: " + ""+ sum); } } } Output : 3 3 1 2 3 4 5 6 7 8 9 1  Column sum is: 12 2  Column sum is: 15 3  Column sum is: 18                                                           Happy Coding 💻:-)

Sum of Diagonal Elements of Matrix: Program: import java.util.Scanner; public class DiagonalAndOffDiagonalSum { public static void main(String[] args) { int r, c; Scanner s = new Scanner(System.in); r = s.nextInt(); c = s.nextInt(); if(r!=c) { System.out.println("Please enter dimensions of square matrix"); } int[][] matrix = new int[r][c]; for(int i = 0; i<r; i++) { for(int j = 0; j<c;j++) { matrix[i][j] = s.nextInt(); } } int dig1 = 0, dig2 = 0; for(int i = 0 ; i < r; i++) { dig1+=matrix[i][i]; dig2+=matrix[i][r-1-i]; } System.out.println("The Sum of diagonal1 is:" + " " + dig1); System.out.println("The Sum of diagonal2 is:" + " " + dig2); } } Output:                                                                       ...

Check Weather two Matrices are Identical: Program: import java.util.Scanner; public class CheckIdenticalMatrices { public static void main(String[] args) { int r1, c1, r2, c2; Scanner s = new Scanner(System.in); r1 = s.nextInt(); c1 = s.nextInt(); r2 = s.nextInt(); c2 = s.nextInt(); if(r1 != r2 || c1!=c2) { System.out.println("Matrices are not identical!"); } int[][] matrix1 = new int[r1][c1]; int[][] matrix2 = new int[r2][c2]; for(int i = 0; i<r1; i++) { for(int j = 0; j<c1;j++) { matrix1[i][j] = s.nextInt(); } } for(int i = 0; i<r2; i++) { for(int j = 0; j<c2;j++) { matrix2[i][j] = s.nextInt(); } } boolean flag = true; for(int i = 0; i<r1; i++) { for(int j = 0;j<c1; j++) { if(matrix1[i][j] != matrix2[i][j]) { flag = false; break; } } if(flag == false) { break; } } if(flag == true) { System.out.println("Matrices are Id...

0 1 Knapsack Problem – Dynamic Programming Solution: Problem Description: Given weights and values of n items, put these items in a knapsack of capacity M to get the maximum total value in the knapsack. Note that, you can select items, the sum of whose weight is less than or equal to the capacity of knapsack, W. Problem Solution: The problem is to find a subset of items such that –  the sum of weight of all the items in the subset should be less than or equal to knapsack capacity  out of all subsets that satisfy criteria 1 above, the desired subset is the one in which the sum values of its items is maximum. Expected Input and Output: Case-1: number of items, n=4 weight of items, w[]=2 3 4 5 value of items,  v[]=3 4 5 6 capacity of knapsack, M=5 maximum attainable value of items=7   by collecting first and second item in the knapsack. Case-2:   n=3 w[]=3 2 1 v[]=5 3 4 M=5 maximum attainable value of items=9  by collecting first and last item in the knap...

Sum of All Odd Length Subarrays: Problem Description: Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays. A subarray is a contiguous subsequence of the array. Return the sum of all odd-length subarrays of arr. Example 1: Input: arr = [1,4,2,5,3] Output: 58 Explanation: The odd-length subarrays of arr and their sums are: [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,2] = 7 [4,2,5] = 11 [2,5,3] = 10 [1,4,2,5,3] = 15 If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58 Example 2: Input: arr = [1,2] Output: 3 Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3. Example 3: Input: arr = [10,11,12] Output: 66   Constraints: 1 <= arr.length <= 100 1 <= arr[i] <= 1000 Solution: Optimized Solution: class Solution {     public int sumOddLengthSubarrays(int[] arr) {         int n = arr.length, res = 0, start = 0, end = 0,elementappearsinhowmanysubarrays ...

Running Sum of 1d Array: Problem Description: Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of nums. Example 1: Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. Example 2: Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]. Example 3: Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]   Constraints: 1 <= nums.length <= 1000 -10^6 <= nums[i] <= 10^6 Solution: class Solution {     public int[] runningSum(int[] nums) {         int sm = 0;         int[] runningSum = new int[nums.length];         for(int i=0; i < nums.length; i++){             sm += nums[i];             runningSum[i] = sm;         }   ...

Maximum Subarray  Problem Problem Description: Given a sequence of n real numbers A(1) … A(n), determine a contiguous subsequence A(i) … A(j) for which the sum of elements in the subsequence is maximized. Problem Solution: We will proceed in a linear fashion maintaining overall_max and current_max variables. If adding the current element to current_max results in overall maximum value, we will replace the value of overall_max variable. Otherwise, we will proceed furthere. Expected Input and Output: Case-1: A[]={2,4,6,8} maximum contiguous subarry= {2, 4, 6, 8} maximum contiguous subarray sum= 20 Case-2: A[]={-2, 3, -7, 5, -9} maximum contiguous subarry= {5} maximum contiguous subarray sum= 5 Case-3: A[]={3, -4, 7, -9, 8, 7} maximum contiguous subarry= {8, 7} maximum contiguous subarray sum= 15   A[]={3, -4, 9, -8, 8, 7} maximum contiguous subarry= {9, -8, 8, 7} maximum contiguous subarray sum= 16 Case-4: A[]={3, -4, 9, -8, 8, 7} maximum contiguous subarry= {9, -8, 8, 7} maximu...

Merge Sort: Merge Sort is a Divide and Conquer algorithm ( or  It follows divide and conquer design technique.) It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. Below is the basic algorithm for merge sort: MergeSort(arr[], l,  r) If r > l      1. Find the middle point to divide the array into two halves:                middle m = (l+r)/2      2. Call mergeSort for first half:                 Call mergeSort(arr, l, m)      3. Call mergeSort for second half:              Call mergeSort(arr, m+1, r)      4. Merge the two halves sorted in step 2 ...