Competitive Programming

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

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

Binary Search Algorithm: ASSUMPTION: • Let a base i 1 ≤ i ≤ n be a list of elements which are sorted in non-decreasing  order. PROBLEM: • Consider the problem of determining whether a given element x is  present in the list. • In case x is present, we are to determine a value j such that a base j = x. • If x is not in the list then j is to be set to zero. Process of Binary Search Using Divide and  Conquer: • Divide-and conquer suggests breaking up any instance • I = (n, a 1 , ... , a n,   x) of this search problem into sub instances. •   One possibility is to pick an index k and obtain three instances: •   I1 = (k - 1, a 1 , ••• , ak-1, x), •   I2 = (1, a k , x), and •     I3 = (n - k, a k+1 ,••••, an , x). Algorithm of Binary Search: Algorithm Binary Search(a,i,l,x) {         if(l=i) then // small(p) only one element        {  if(x==a[i]) then return i; else return 0;   ...

Java Primality Test Problem Description: A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself.  For example, the first six prime numbers are 2, 3, 5, 7, 11, and 13. Given a large integer, n, use the Java BigInteger class'  isProbablePrime method to determine and print whether it's prime or not prime. Input Format A single line containing an integer,  n(the number to be checked). Constraints n contains at most 100 digits. Output Format: If n is a prime number, print prime; otherwise, print not prime. Sample Input 13 Sample Output prime Explanation The only positive divisors of 13 are 1 and 13, so we print prime. Solution : import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in); ...

Valid Username Regular Expression: Problem Description: You are updating the username policy on your company's internal networking platform. According to the policy, a username is considered valid if all the following constraints are satisfied: The username consists of 8 to 30 characters inclusive. If the username consists of less than  or greater than 8 characters, then it is an invalid username. The username can only contain alphanumeric characters and underscores (_). Alphanumeric characters describe the character set consisting of lowercase characters[a-z] , uppercase characters[A-Z] , and digits[0-9]. The first character of the username must be an alphabetic character, i.e., either lowercase character [a-z] or uppercase character [A-Z]. Update the value of regularExpression field in the UsernameValidator class so that the regular expression only matches with valid usernames. Input Format The first line of input contains an integer , describing the total number of usernames. Ea...

Remove duplicates from sorted array Given a sorted array, the task is to remove the duplicate elements from the array. Examples: 1) Input  : arr[] = {2, 2, 2, 2, 2} Output : arr[] = {2}          new size = 1 2) Input  : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5} Output : arr[] = {1, 2, 3, 4, 5}          new size = 5 Method 1: (Using extra space) Create an auxiliary array temp[] to store unique elements. Traverse input array and one by one copy unique elements of arr[] to temp[]. Also keep track of count of unique elements. Let this count be j. Copy j elements from temp[] to arr[] and return j // simple java program to remove  // duplicates  Solution : class Main  {  // Function to remove duplicate elements  // This function returns new size of modified  // array.  static int removeDuplicates(int arr[], int n)  {  // Return, if array is empty  // or contains a single ele...

Problem Description: How Many Numbers Are Smaller Than the Current Number Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i]. Return the answer in an array.   Example 1: Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation:  For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).  For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1).  For nums[3]=2 there exist one smaller number than it (1).  For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2). Example 2: Input: nums = [6,5,4,8] Output: [2,1,0,3] Example 3: Input: nums = [7,7,7,7] Output: [0,0,0,0]   Constraints: 2 <= nums.length <= 500 0 <= nums[i] <= 100 Solution : class Solution {     public int[] smallerNumbersThanCurrent(int[] n...

Program Description: Number of Good Pairs Given an array of integers nums. A pair (i,j) is called good if nums[i] == nums[j] and i < j. Return the number of good pairs. Example 1: Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed. Example 2: Input: nums = [1,1,1,1] Output: 6 Explanation: Each pair in the array are good. Example 3: Input: nums = [1,2,3] Output: 0   Constraints: 1 <= nums.length <= 100 1 <= nums[i] <= 100 Solution: class Solution {     public int numIdenticalPairs(int[] nums) {         int count = 0;         for(int i = 0; i< nums.length-1; i++){             for(int j=i+1; j<nums.length; j++){                 if(i<j && nums[i]==nums[j]){                     count++;             ...