Competitive Programming

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

Two Sum: Program Description: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1]   Constraints: 2 <= nums.length <= 105 -109 <= nums[i] <= 109 -109 <= target <= 109 Only one valid answer exists. : Solution : class Solution {     public int[] twoSum(int[] nums, int tar) {         Map<Integer, Integer> dic = new HashMap<Integer, Integer>();                  for(int i=0; i<nums.length ; i++){           ...