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

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