<jupyter_start><jupyter_text>Binary Search Time complexities: O(Log n)  Using Binary searchunsorted - O(n)<jupyter_code>def binarySearch(array,low,high,val):
    if high<low:
        return -1
    mid=(high+low)/2
    mid=int(mid)
    if val==array[mid]:
        return mid+1
    
    if val>array[mid]:
        return binarySearch(array,mid+1,high,val)
    
    return binarySearch(array,low,mid-1,val)
    
array=[1,2,3,5,7,10,12]

print("Location: "+str(binarySearch(array,0,len(array),7)))<jupyter_output>Location: 5<jupyter_text>Given an array A[] and a number x, check for pair in A[] with sum as x<jupyter_code>#Using HashMap  O(n) time if range of numbers is known

CONSTBIN=100000

def searchPairSum(array,sumValue):
    bin=[0]*CONSTBIN
    for i in range(0,len(array)):
        temp=sumValue-array[i]
        if temp>0 and bin[temp]==1:
            print("Pair with  the sum "+str(sumValue)+" are: "+str(array[i])+" , "+str(temp))
        
        bin[array[i]]=1
        
# use Sorting array and den search

def searchPairInSortedArray(array,sumValue,r,l):
    if(l<=r):
        return 
    
    s=array[r]+array[l]
    
    if s==sumValue:
        print("Pair with  the sum "+str(sumValue)+" are: "+str(array[r])+" , "+str(array[l]))
        
    if s>sumValue :
        return searchPairInSortedArray(array,sumValue,r,l-1)
    
    return searchPairInSortedArray(array,sumValue,r+1,l)

    
    
array=[1,2,3,5,7,10,12]
searchPairSum(array,16)
searchPairInSortedArray(sorted(array),16,0,len(array)-1)<jupyter_output><empty_output><jupyter_text>Find the Number Occurring Odd Number of TimesGiven an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times.<jupyter_code>def getOddOccurence(array):
    res=0
    
    for a in array:
        res=res^a
    return res
arr = [ 2, 3, 5, 4, 5, 2, 5, 3, 5, 2, 4, 4, 2]

print(str(getOddOccurence(arr)))<jupyter_output>4<jupyter_text>Largest Sum Contiguous Subarrayfind the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.<jupyter_code>array=[-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7]

i=1
largestSum=array[0]
curSum=array[0]

for i in range(1,len(array)):
    curSum=max(curSum+array[i],array[i])
    largestSum=max(largestSum,curSum)

print(largestSum)<jupyter_output>-3<jupyter_text>Find the Missing NumberYou are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.<jupyter_code>def FindMissingNUmber(array):
    n=len(array)
    s=0
    for i in range(0,n):
        s=s+array[i]
    n=n+1
    missingNumber=(n*(n+1)/2)-s
    return missingNumber

array=[1, 2, 4,6, 3, 7, 8]
    
print(FindMissingNUmber(array))<jupyter_output>5.0<jupyter_text>Search an element in a sorted and rotated arrayAssume that all elements in array are distinct.<jupyter_code>def BinanrySearchRotatedSorted(arr,lb,ub,key):
        if lb>ub:
            return "NOT FOUND"
        
        mid=(lb+ub)/2
        mid=int(mid)
        
        if key==arr[mid]:
            return mid
        
        if arr[lb]<=arr[mid]:
            if key<=arr[mid] and key>arr[lb]:
                return BinanrySearchRotatedSorted(arr,lb,mid-1,key)
            return BinanrySearchRotatedSorted(arr,mid+1,ub,key)
        
        else:
            if key<=arr[ub] and key>=arr[mid]:
                return BinanrySearchRotatedSorted(arr,mid+1,ub,key)
            return BinanrySearchRotatedSorted(arr,lb,mid-1,key)

        
arr = [30, 40, 50, 10, 20];
print(BinanrySearchRotatedSorted(arr,0,len(arr)-1,90))<jupyter_output>NOT FOUND<jupyter_text>Merge an array of size n into another array of size m+nThere are two sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the output is sorted.<jupyter_code>import numpy as np

def MoveToEnd(M):
    j=len(M)-1
    for i in range(len(M)-1,-1,-1):
         if not np.isnan(M[i]):
                M[j]=M[i]
                j=j-1
    return M

def MergeSortedArrays(M,N):
    m=len(N)
    n=0
    
    for i in range(0,len(M)):
        if n>=len(N):
            break
            
        if m<len(M):
            if M[m]<N[n]:
                M[i]=M[m]
                m=m+1
                continue
        M[i]=N[n]
        n=n+1
            
    return M
    

a = [2, 8, np.nan, np.nan, np.nan, 13, np.nan, 15, 20]
b=[5, 7, 9, 25]
print(a)
print(b)

a=MoveToEnd(a)

a=MergeSortedArrays(a,b)

print("After merge: "+str(a))<jupyter_output>[2, 8, nan, nan, nan, 13, nan, 15, 20]
[5, 7, 9, 25]
After merge: [2, 5, 7, 8, 9, 13, 15, 20, 25]<jupyter_text>Median of two sorted arraysThere are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))Analysis:Note that the definition of the Median:1. If the size of the sequence N is odd: N/2+1th element is median.2. If the size of the sequence N is even:  average of the N/2th and N/2+1th element is median.<jupyter_code>class Solution:
    # @return a float
    def findMedianSortedArrays(self, A, B):
        if (len(A) + len(B)) % 2 == 0:
            return (self.fms(A, B, (len(A) + len(B))/2) + self.fms(A, B, (len(A) + len(B))/2 + 1))/2.0
        else:
            return self.fms(A, B, (len(A) + len(B))/2 + 1)
     
    def fms(self, A, B, k):
        
        if len(A) > len(B):
            return self.fms(B, A, k)
        else:
            if len(A) == 0:
                return B[k-1]
            if k == 1:
                return min(A[0], B[0])
            pa = min(k/2, len(A))
            pa=int(pa)
            pb = k - pa
            pb=int(pb)
            if A[pa-1] <= B[pb-1]:
                return self.fms(A[pa:], B[:pb], int(k-pa))
            else:
                return self.fms(A[:pa], B[pb:], int(k-pb))
             
        

ar1= [1,3,5,7,9] 
ar2 = [2,4,8,10,12,14,16,18]

s=Solution()
print(str(s.findMedianSortedArrays(ar1,ar2)))<jupyter_output>8<jupyter_text>Reverse Array or String<jupyter_code>def ReverseArray(arr):
    end=len(arr)
    for i in range(0,int(end/2)):
        temp=arr[i]
        arr[i]=arr[end-i-1]
        arr[end-i-1]=temp
    return arr
        
arr = [1, 2, 3, 4, 5, 6,7]
arr=ReverseArray(arr)
print(arr)<jupyter_output>[7, 6, 5, 4, 3, 2, 1]<jupyter_text>Program for array rotationWrite a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.<jupyter_code>def ReverseLimitedArray(arr,start,end):
    mid=int((end-start)/2)
    for i in range(0,mid):
        temp=arr[start+i]
        arr[start+i]=arr[end-i-1]
        arr[end-i-1]=temp
    return arr

def RotateArray(arr,order):
    arr=ReverseLimitedArray(arr,0,order)
    arr=ReverseLimitedArray(arr,order,len(arr))
    arr=ReverseLimitedArray(arr,0,len(arr))
    return arr
    
arr = [1, 2, 3, 4, 5, 6,7]
arr=RotateArray(arr,2)
print(arr)<jupyter_output>[3, 4, 5, 6, 7, 1, 2]<jupyter_text>Maximum sum such that no two elements are adjacentGiven an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.<jupyter_code>def MaxSumNoTwoAdjacent(array):
    incld=0
    excld=0
    
    for i in array:
        new_excld=incld if incld>excld else excld
        incld=excld+i
        excld=new_excld
    
    return (incld if incld>excld else excld)

arr = [5, 5, 10, 4, 5, 65]
print(str(MaxSumNoTwoAdjacent(arr)))<jupyter_output>80<jupyter_text>Leaders in an arrayWrite a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.<jupyter_code>def findLeaders(array):
    
    arrayLength=len(array)
    if arrayLength==1:
        print(array)
    maxVal=array[arrayLength-1]
    for i in range(arrayLength-2,-1,-1):
        if maxVal<array[i]:
            print(maxVal)
            maxVal=array[i]
    print(maxVal)
        

findLeaders([16, 17, 4, 13, 5, 42])<jupyter_output>42<jupyter_text>Sort elements by frequencyPrint the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.  Count Inversions in an array nversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j<jupyter_code>def count_inversion(lst):
    return merge_count_inversion(lst)[1]

def merge_count_inversion(array):
    if len(array)<2:
        return array,0
    
    mid=int(len(array)/2)
    left,a=merge_count_inversion(array[:mid])
    right,b=merge_count_inversion(array[mid:])
    
    result,c=Merge_InversionCount_Split(left,right)
    #print(str(a)+" "+str(b)+" "+str(c))
    return result,(a+b+c)

def Merge_InversionCount_Split(left,right):
    i,j=0,0
    count=0
    result=[]
    
    leftLen=len(left)
    
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            result.append(left[i])
            i+=1
            
        else:
            result.append(right[j])
            count+=leftLen-i
            
            j+=1
            
    result+=left[i:]
    result+=right[j:]
    
    return result,count

input_array = [4, 1, 3, 2, 9, 5] 
inv=count_inversion(input_array)
print(inv)<jupyter_output>5<jupyter_text>Two elements whose sum is closest to zeroAn Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.<jupyter_code>def sumClosestToZero(array):
    array.sort()
    l=0
    r=len(array)-1
    
    min_l=0
    min_r=r
    min_sum=array[l]+array[r]
    
    while l<r:
        summ=array[l]+array[r]
        if abs(min_sum)>abs(summ) :
            min_sum=summ
            min_l=l
            min_r=r
        
        if summ<0:
            l+=1
        else:
            r-=1
    
    print(str(array[min_l])+" "+str(array[min_r]))
    
array=[1, 60, -10, 70, -80, 85]
sumClosestToZero(array)<jupyter_output>-80 85<jupyter_text>Find the smallest and second smallest element in an array<jupyter_code>def FindSmallestAndSecondSmallest(array):
    smallest=array[0] if array[0]<array[1] else array[1]
    secondSmallest=array[1] if array[0]<array[1] else array[0]
    
    for i in range(2,len(array)):
        if array[i]<secondSmallest:
            if array[i]<smallest:
                secondSmallest=smallest
                smallest=array[i]
            if array[i]!=smallest:    
                secondSmallest=array[i]
    
    print(str(smallest)+" "+str(secondSmallest))

array=[12, 13, 1, 10, 34, 1]
FindSmallestAndSecondSmallest(array)<jupyter_output>1 10<jupyter_text>Check for Majority Element in a sorted arrayQuestion: Write a C function to find if a given integer x appears more than n/2 times in a sorted array of n integers.Basically, we need to write a function say isMajority() that takes an array (arr[] ), array’s size (n) and a number to be searched (x) as parameters and returns true if x is a majority element (present more than n/2 times).<jupyter_code>def isMajority(array,num):
    length=len(array)
    ithloction=BinarySearch(array,0,length-1,num)
    print(ithloction)
    if array[ithloction+int(length/2)]==num:
        print("True")
        
    else:
        print("False")
    
    
def BinarySearch(array,left,right,key):
    if left<=right:
        mid=(left+right)/2
        mid=int(mid)
        if (array[0]==key or array[mid-1]<key) and array[mid]==key:
            return mid

        if key>array[mid]:
            BinarySearch(array,mid+1,right,key)
        else:
            BinarySearch(array,left,mid-1,key)

    return -1

array=[1, 1, 1, 2, 2]
isMajority(array,1)<jupyter_output>2
False<jupyter_text>Maximum and minimum of an array using minimum number of comparisons<jupyter_code>def findMaxAndMin(arr):
    if(len(arr)==1):
        return arr[0],arr[0]
    
    minimum=arr[0] if arr[0]<arr[1] else arr[1]
    maximum=arr[1] if arr[0]<arr[1] else arr[0]
    
    for i in range(2,len(arr)):
        if arr[i]>maximum:
            maximum=arr[i]
        if arr[i]<minimum:
            minimum=arr[i]
    return minimum,maximum
    
    
arr=[2,3,6,12,16,1]
minimum=findMaxAndMin(arr)[0]
maximum=findMaxAndMin(arr)[1]
print("Minimum: "+str(minimum)+" \nMaximum "+str(maximum))<jupyter_output>Minimum: 1 
Maximum 16<jupyter_text>Segregate 0s and 1s in an arrayYou are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array. Traverse array only once.<jupyter_code>def segregateArray(arr):
    if(len(arr)<=1):
        return arr
    l=0
    r=len(arr)-1
    while l<r:
        while(arr[l]==0):
            l+=1
        while(arr[r]==1):
            r-=1
        if(l<r):
            arr[l]=0
            arr[r]=1
            l+=1
            r-=1
    return arr

arr=[0, 1, 0, 1, 1,0, 1]
print(segregateArray(arr))<jupyter_output>[0, 0, 0, 1, 1, 1, 1]<jupyter_text>k largest(or smallest) elements in an array | added Min Heap methodQuestion: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.<jupyter_code>public class minHeap {
	public int size;
	public int [] mH;
	public int position;
	public minHeap(int size){
		this.size=size;
		mH = new int [size+1];
		position = 0;
	}
	public void createHeap(int [] arrA){
		if(arrA.length>0){
			for(int i=0;i<arrA.length;i++){
				insert(arrA[i]);
			}
		}		
	}
	public void display(){
		for(int i=1;i<mH.length;i++){
			System.out.print(" " + mH[i]);			
		}
		System.out.println("");
	}
	public void insert(int x){
		if(position==0){
			mH[position+1]=x;
			position = 2;
		}else{
			mH[position++]=x;
			bubbleUp();
		}
	}
	public void bubbleUp(){
		int pos = position-1;
		while(pos>0 && mH[pos/2]>mH[pos]){
			int y = mH[pos];
			mH[pos]=mH[pos/2];
			mH[pos/2] = y;
			pos = pos/2;
		}
	}
	public int extractMin(){
		int min = mH[1];
		mH[1]=mH[position-1];
		mH[position-1]=0;
		position--;		
		sinkDown(1);
		return min;
	}
	
	public void sinkDown(int k){int a = mH[k];
		int smallest =k;
		if(2*k<position && mH[smallest]>mH[2*k]){
			smallest = 2*k;
		}
		if(2*k+1<position && mH[smallest]>mH[2*k+1]){
			smallest = 2*k+1;
		}
		if(smallest!=k){
			swap(k,smallest);
			sinkDown(smallest);
		}
				
	}
	public void swap(int a, int b){
		//System.out.println("swappinh" + mH[a] + " and " + mH[b]);
		int temp = mH[a];
		mH[a] = mH[b];
		mH[b] = temp;
	}
	
	public static void main(String args[]){
		int arrA [] = {3,2,1,7,8,4,10,16,12};
		System.out.print("Original Array : ");
		for(int i=0;i<arrA.length;i++){
			System.out.print("  " + arrA[i]);
		}
		minHeap m = new minHeap(arrA.length);
		System.out.print("\nMin-Heap : ");
		m.createHeap(arrA);		
		m.display();
		System.out.print("Extract Min :");
		for(int i=0;i<arrA.length;i++){
			System.out.print("  " + m.extractMin());
		}
		
	}
	
		
}
public class KthSmallestElementInArray {

	public static int find(int [] A, int k){
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for(int i=0;i<A.length;i++){
			pq.offer(A[i]);
		}
		int n = -1;
		while(k>0){
			n = pq.poll();
			k--;
		}
		return n;
	}
	public static void main(String[] args) {
		int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 };
		int k = 4;
		System.out.println("4th smallest element:" + find(A,4));

	}

}<jupyter_output><empty_output><jupyter_text>Get sqaureroot of a number<jupyter_code>def findSqrt(a):
    if a<0:
        return -1
    
    if a==1 or a==0:
        return a
    
    start=1
    end=a/2
    
    ans=0
    
    while start<=end:
        mid= int((start+end)/2)
        midprd=mid*mid
        if midprd==a:
            return mid

        if midprd<a:
            start=mid+1
            ans=mid
        else:
            end=mid-1

    return ans

findSqrt(11)<jupyter_output><empty_output><jupyter_text>Count number of occurrences (or frequency) in a sorted array<jupyter_code>def noOfOccurence(arr,a):
    n=len(arr)
    if n==1 and arr[0]==a:
        return 1
    
    firstoccurence=first(arr,0,n-1,a)
    
    if firstoccurence==-1:
        return -1
    
    lastoccurence=last(arr,0,n-1,a,n)
    
    #print(str(lastoccurence)+" "+str(firstoccurence))
    
    return lastoccurence-firstoccurence+1

def first(arr,start,end,a):
    while start<=end:
        mid=int((start+end)/2)
        if (arr[mid-1]<a or mid==0)and(arr[mid]==a):
            return mid
        
        if arr[mid]<a:
            start=mid+1
        else:
            end=mid-1
        
    return -1

def last(arr,start,end,a,n):
    while start<=end:
        mid=int((start+end)/2)
        #print(mid)
        if (mid==n-1 or arr[mid+1]>a)and(arr[mid]==a):
            return mid
        
        if arr[mid]>a:
            end=mid-1
        else:
            start=mid+1
        
    return -1

noOfOccurence([1, 2, 2, 3, 3, 3, 3],3)<jupyter_output><empty_output><jupyter_text>Print all valid combinations of groups of parenthesis<jupyter_code>def printParanthesis(openP,closeP,bracket):
    if openP==0 and closeP==0:
        print(bracket)
    
    if openP>closeP:
        return
    
    if(openP>0):
        printParanthesis(openP-1,closeP,bracket+"(")
    
    if(closeP>0):
        printParanthesis(openP,closeP-1,bracket+")")
        

length=6

printParanthesis(int(length/2),int(length/2),"")<jupyter_output>((()))
(()())
(())()
()(())
()()()
{'fraction_non_alphanumeric': 0.13706006439435994, 'fraction_numerical': 0.03169756855778839, 'mean_word_length': 2.782280075582616, 'pattern_counts': {'":': 0, '<': 115, '<?xml version=': 0, '>': 98, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '22', 'dir': 'jupyter-structured-clean-dedup', 'id': '658259', 'license': 'MIT', 'n_tokens_mistral': 7156, 'n_tokens_neox': 6671, 'n_words': 1670, 'path': 'Array.ipynb', 'repo_name': 'vimithamanohar/practice', 'size': '18014'}