Java

Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum. Problem link :- click here Code import java.util.Scanner; // KADANE'S ALGORITHM public class DynamicProgramming_04 { static int maxSum(int arr[]) { int cur_sum = arr[0]; int max_sum = arr[0]; for(int i=1; i<arr.length; i++) { cur_sum += arr[i]; if(max_sum < cur_sum) max_sum = cur_sum; if(cur_sum < 0) cur_sum = 0; } return max_sum; } public static void main(String[] args) { Scanner s = new Scanner(System.in); System.out.print("Enter the size of the array : "); int n = s.nextInt(); int arr[] = new int[n]; for(int i=0...

Given an integer N denoting the Length of a line segment. You need to cut the line segment in such a way that the cut length of a line segment each time is either x, y, or z. Here x, y, and z are integers. After performing all the cut operations, your total number of cut segments must be maximum. Problem link :- click here Code import java.util.Scanner; // MAXIMIZE THE CUT SEGMENT public class DynamicProgramming_03 { // Recursion and Memoization(its not spelling mistake) static int maxCut(int l, int p, int q, int r, int arr[]) { int min = Math.min( Math.min(p, q), r ); int option_p = 0; int option_q = 0; int option_r = 0; if( l < min || l == 0 ) return 0; if(arr[l] != 0) return arr[l]; if(p <= l) option_p = maxCut(l-p, p, q, r, arr); if(q <= l) option_q = maxCut(l-q, p, q,...

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top(order does matter) Problem link :- click here Code import java.util.Scanner; // COUNT WAYS TO REACH THE N'TH STAIR public class DynamicProgramming_02 { static int numberOfWaysToReachNthStair(int n, int arr[]) { if(n==1) { arr[1] = 1; return 1; } if(n==2) { arr[2] = 2; return 2; } else { int ans = numberOfWaysToReachNthStair(n-1, arr) + numberOfWaysToReachNthStair(n-2, arr); arr[n] = ans; return ans; } } static int numberOfWaysToReachNthStair2(int n) { int arr[] = new int[n+1]; arr[1] = 1; arr[2] = 2; ...

Given a number N, find the first N Fibonacci numbers. The first two number of the series are 1 and 1. Problem link :- click here Code import java.util.Scanner; // PRINT FIRST N FIBONACCI NUMBERS public class DynamicProgramming_01 {          // Recursion and memoization static long fibonacci(int n, long arr[]) { if(arr[n] != 0) return arr[n]; if(n==1) { arr[1] = 1; return 1; } if(n==2) { arr[2] = 1; return 1; } else { long ans = fibonacci(n-1, arr) + fibonacci(n-2, arr); arr[n] = ans; return ans; } }          // Dynamic programming static long[] fibonacci1(int n) { long arr[] = new long[n+1]; arr[1] = 1; arr[2] = 1; for(int i=3; i<=n; i++) arr[i] = arr[i-1] + arr[i-2]; return arr; } public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); // long[] ans = fibonacci1(n); // // for...

Given an unsorted array A of size N that contains only non-negative integers, find a continuous sub-array which adds to a given number S. In case of multiple subarrays, return the subarray which comes first on moving from left to right. Problem link :- click here Code import java.util.Scanner; // SUBARRAY WITH GIVEN SUM public class Prefix_sum__Sliding_window_09 { static int[] subarrayWithGivenSum(int arr[], int S) { int m = 0; //size of subarray int ending_index = -1; //ending index of subarray int starting_index = -1; //starting index of subarray int sum = 0; //sum of the subarray for(int i=0; i<arr.length; i++) { sum += arr[i]; m++; if(sum > S) { sum -= arr[i - (m-1)]; m--; } if(...

Given an array of integers and a number K. Find the count of distinct elements in every window of size K in the array. Problem link :- click here Code import java.util.HashMap; import java.util.Map; import java.util.Scanner; // COUNT DISTINCT ELEMENT IN EVERY WINDOW public class Prefix_sum__Sliding_window_08 { static int[] countDistinctElementInEveryWindow(int arr[], int k) { int count = 0; int n = arr.length - (k - 1); int c_arr[] = new int[n]; Map<Integer, Integer> hm = new HashMap<>(); // step1: - First window where only adding is required and no removing for(int i=0; i<k; i++) { if( hm.containsKey(arr[i]) == false ) { count++; hm.put(arr[i], 1); } else hm.put(arr[i], hm.get(arr[i]) + 1); } ...

Given an array of integers Arr of size N and a number K. Return the maximum sum of a subarray of size K. Problem link :- click here Code import java.util.Scanner; // MAX SUM SUBARRAY OF SIZE K public class Prefix_sum__Sliding_window_07 { static int maxSumOfSubarrayOfSizeK(int arr[], int k) { if(k > arr.length) return -1; // SLIDING WINDOW /* arr = {100, 200, 300, 100} k = 2 step1: -   add the values of first k elements to `sum` and update `maxSum`. step2: - until last element of the `arr` ( i=k to i=n)      i) subtract the value of leftmost element which is not yet subtracted      from `sum`.      ii) add the value of the present element in the iteration. i.e., `i`.      iii) update the `maxSum`. sum = arr[0] + arr[2] sum = 100 + 200 = 300 maxSum = 300 sum = sum - arr[0] subtract = 300 - 100 = 200 ...

Given two binary arrays arr1[] and arr2[] of same size N. Find length of the longest common span [i, j] where j>=i such that arr1[i] + arr1[i+1] + .... + arr1[j] = arr2[i] + arr2[i+1] + .... + arr2[j]. Problem link :- click here Code import java.util.HashMap; import java.util.Map; import java.util.Scanner; // LONGEST SPAN IN TWO BINARY ARRAYS public class Prefix_sum__Sliding_window_06 { static int longestSpanInTwoBinaryArrays(int arr1[], int arr2[], int n) { int arr[] = new int[n]; // Initializing the array `arr` for(int i=0; i<n; i++) arr[i] = arr1[i] - arr2[i]; /* METHOD: - arr1 = {0, 1, 0, 0, 0, 0} arr2 = {1, 0, 1, 0, 0, 1} arr = arr1 - arr2 arr = {-1, 1, -1, 0, 0, -1} psa = {-1, 0, -1, -...

Given an array of 0's and 1's. Find the length of the largest subarray with equal number of 0's and 1's. Problem link :- click here Code import java.util.HashMap; import java.util.Map; import java.util.Scanner; // LONGEST SUBARRAY WITH EQUAL NUMBER OF 0's AND 1;s public class Prefix_sum__Sliding_window_05 { static int longestSubarrayWith0sAnd1s(int[] arr) { /* If we convert this problem to problem number 2, then it will be easy. In problem 2 we find the sub-array with sum == 0. In this problem, the given array contains only 0's and 1's. If we replace 0's with -1's, then this is exactly the same problem. */ // Replacing 0 with -1 for(int i=0; i<arr.length; i++) arr[i] = (arr[i] == 0)? -1:1; Map<Integer, Integer> hp = new HashMap<>(); int s...

Given an array containing N integers and a positive integer K, find the length of the longest sub array with sum of the elements divisible by the given values k. Problem link :- click here Code import java.util.HashMap; import java.util.Map; import java.util.Scanner; //LONGEST SUBARRAY WITH SUM DIVISIBLE BY K public class Prefix_sum__Sliding_window_04 { static int longestSubarrayWithSumDivisibleByK(int arr[], int k) { /* *) This problem is similar to problem 2 where we have used the psa(prefix sum array). *) Here instead of `psa` we are creating `modarr` such that modarr[i] = psa[i] % k *) If any element in `modarr` is == 0, then there is a sub-array starting from index 0 having sum of elements divisible by k. *) How to verify sub-arrays which doesn't start with index 0? *) Consider a example: arr = {2, 7, 6, 1, 4, 5} k = 3 psa = {2, 9, 15, 16, 20, 25} modarr = {2, 0, 0, 1, 2, 1}    ...

Given an array containing N integers and an integer K, Your task is to find the length of the longest Sub-Array with the sum of the elements equal to the given value k. Problem link :- click here Code import java.util.Scanner; // LONGEST SUBARRAY WITH SUM K public class Prefix_sum__Sliding_window_03 { // Sliding window technique static int sizeOfSubarrayWithSumK(int[] arr, int k) { int max_m = 0; int m = 0; // length of subarray int sum = 0; for(int i=0; i<arr.length; i++) { sum += arr[i]; m++; if(sum == k) max_m = m; else if(sum > k) { // deleting the first element of the sub-array sum -= arr[i-(m-1)]; m--; } } return max_m; } public stati...

Given an array of positive and negative numbers. Find if there is a subarray(of at-least one) with 0 sum. Problem link :- click here Code import java.util.HashSet; import java.util.Scanner; import java.util.Set; // CHECK IF THERE IS A SUBARRAY WITH 0 SUM public class Prefix_sum__Sliding_window_02 { static boolean containsSubarrayWith0sum(int[] arr, int n) { // Calculating prefix sum array(psa) int[] psa = new int[n]; psa[0] = arr[0]; for(int i=1; i<n; i++) psa[i] = psa[i-1] + arr[i]; /* LOGIC: - *) In `psa` we have sum of elements starting from index 0 to that index. *) If any element in `psa` is == 0 then there is a sub-array starting from index 0 having sum of elements = 0 *) How to verify sub-arrays wh...

Given an array A of n positive numbers. The task is to find the first Equilibrium Point in the array. Equilibrium Point in an array is a position such that the sum of elements before it is equal to the sum of elements after it. Problem link :- click here Code // EQUILIBRIUM POINT import java.util.Scanner; public class Prefix_sum__Sliding_window_01 { static int equilibriumPoint(int[] arr, int n) { // Calculating prefix sum array(psa) int[] psa = new int[n]; psa[0] = arr[0]; for(int i=1; i<n; i++) psa[i] = psa[i-1] + arr[i]; /* NOTE: - if n==1 then the only element in the array is the equilibrium point if n==2 then there will not be any equilibrium point To find the equilibrium point steps are: - 1) We have to iterate through each element starting from index 1, `ref` 2) Then we have to compare the sum of elements to the left <---- of `ref` and the sum of elements to the right ----> of `ref` ...

Understanding why prefix sum is needed and know how to use prefix sum to calculate the sum of elements of an array in a given range Video1 link :- click here Video2 link :- click here

Given a N x N matrix M. Write a program to find count of all the distinct elements common to all rows of the matrix. Print count of such elements. Problem link :- Click Here Code import java.util.Scanner; class Hashing__01 { public static void main(String args[]) { Scanner scan = new Scanner(System.in); System.out.println("Enter the Size of array"); Integer n = scan.nextInt(); Integer count = 0,count1 = 0; Integer array[][] = new Integer[n][n]; System.out.println("Enter the array elements"); //Input for array for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { array[i][j] = scan.nextInt(); } } //Comparing first row elements with all other elements for(int k=0;k<n;k++) { for(int l=1;l<n;l++) { ...

POST TITLE Problem link :- click here Code // ENUM CONSTRUCTOR /* Write a program to display the values of currency where in the currency will be PENNY(5), DIME(10), NICKLE(15), QUARTER(25). */ public class Problem__5 { enum Currency { PENNY(5), DIME(10), NICKLE(15), QUARTER(25); int value; Currency(int a) { this.value = a; } int getValue() { return this.value; } } public static void main(String[] args) { Currency c[] = new Currency[4]; c[0] = Currency.PENNY; c[1] = Currency.DIME; c[2] = Currency.NICKLE; c[3] = Currency.QUARTER; for(Currency x:c) { System.out.println("The value of " + x + " = " + x.getValue()); } } }