Competitive Programming

Sum of  Non Lower Triangle Elements: Program: import java.util.Scanner; public class NonLowerTriangleElementsSum { 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 i = 0; i<r; i++) { for(int j = 0;j<c; j++) { if(i<j) { System.out.print(matrix[i][j]); System.out.print(" "); sum+=matrix[i][j]; } } } System.out.println("\nThe sum of Non Lower triangular elements of a matrix is: " + sum); } } Output: 3 3  1 2 3 4 5 6 7 8 9 2 3 6  The sum of Non Lower triangular elements of a matrix is: 11 Happy Coding💻:-)

Sum of Each Row of A Matrix: Program: import java.util.*; public class MatrixRowSum { 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 i = 0; i<r; i++) { sum = 0; for(int j = 0;j<c; j++) { sum += matrix[i][j]; } System.out.println(i+1 + "  " + "Row sum is: " + ""+ sum); } } } Output: 1) 3 3 1 2 3 4 5 6 7 8 9 1  Row sum is: 6 2  Row sum is: 15 3  Row sum is: 24 2) 3 4 1 2 3 4 5 6 7 8 9 10 11 12 1  Row sum is: 10 2  Row sum is: 26 3  Row sum is: 42                                                                 ...

Rotate String in Right Direction in java: Program: import java.util.*; public class RotateString { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); char[] ch = new char[n]; for(int i=0;i<n;i++) { ch[i] = s.next().charAt(0); } int r = s.nextInt(); char temp = 'a'; r=r%n; while(r>0) { temp = ch[n-1]; for(int i = n-1; i>0;i--) { ch[i] = ch[i-1]; } ch[0] = temp; System.out.println("r: " + r); for(int i=0;i<n;i++) { System.out.print(ch[i]); } System.out.println(); r--; } for(int i=0;i<n;i++) { System.out.print(ch[i]); } } } Output : 5 a s d f g 3 r: 3 gasdf r: 2 fgasd r: 1 dfgas dfgas                                                            Happy Coding 💻:-)

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 Elements of Lower Triangular Matrix: Program: import java.util.Scanner; public class LowerTriangularElementsSum { 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.exit(0); } 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 i = 0; i<r; i++) { for(int j = 0;j<c; j++) { if(i>=j) { System.out.print(matrix[i][j]); System.out.print(" "); sum+=matrix[i][j]; } } } System.out.println("\nThe sum of Lower triangular elements of a matrix is: " + sum); } } /* In other words, a square matrix is lower triangular if all its entries above the main diagonal are zero.  * Example of a 3 × 3 lower triangular matrix: Diagonal matrices are both upper  *and lower triangular since they have zeroes a...

Partition Equal Subset Sum: Problem Description: Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Example 1: Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2: Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.   Constraints: 1 <= nums.length <= 200 1 <= nums[i] <= 100 Solution: class Solution {     public boolean canPartition(int[] nums) {         int totalsum = 0, subsetsum = 0;         for(int num: nums)             totalsum+=num;         if(totalsum%2 == 0)             subsetsum = totalsum/2;         else return false;         int n = nums.length;   ...

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

AddTwoMatrices: Program: import java.util.Scanner; public class AddTwoMatrices { 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.exit(0); } int[][] matrix1 = new int[r1][c1]; int[][] matrix2 = new int[r2][c2]; int[][] matrix3 = new int[r1][c1]; 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(); } } for(int i = 0; i<r1; i++) { for(int j = 0;j<c1; j++) { matrix3[i][j] = matrix1[i][j] + matrix2[i][j]; } } for(int i = 0; i<r1; i++) { for(int j = 0;j<c1; j++) { System.out.print(matrix3[i][j]); System.out.print(" "); } System.out.println(); } } }        ...

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

Two Sum II - Input array is sorted: Problem Description: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.   Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. Example 2: Input: numbers = [2,3,4], target = 6 Output: [1,3] Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2]   Constraints: 2 <= nums.length <= 3 * 104 -1000 <= nums[i] <= 1000 nums is sorted in increasing order. -1000 <= target <= 1000 Program: class Solution {     public int[] twoSum(int[] num...