<file_sep>#Count NUMBER OF SUBSET WITH GIVEN DIFFERENCE

arr=[3, 1, 4, 1, 5]
d=2
s= (d+sum(arr))//2
n=len(arr)
k=[[0 for i in range (s+1)] for j in range(n+1)]


for i in range(n+1):
  k[i][0]=1
for i in range(1,s+1):
  k[0][i]=0

for i in range(1,n+1):
  for j in range(1,s+1):

    if arr[i-1]> j:
      k[i][j]= k[i-1][j]
    else:
      k[i][j]= k[i-1][j-arr[i-1]] + k[i-1][j]



print("Given Array {}\nNumber of Subset with given difference {} is {}".format(arr,d,k[n][s]))


'''Here we have to find S2-S1 equal to given difference

So eq [1]-> s2-s1= difference
   eq [2]-> s2+s1 = Total SUM
   =>eq[1] + eq[2]
   2s2= difference + Total SUM
   s2 = (difference + Total SUM)/ 2
   
   Hence s2 can be found i.e the required SUM'''<file_sep># -*- coding: utf-8 -*-
"""
Created on Fri Jun 12 21:04:30 2020

@author: MrMaak
"""
#12321 to check for palindrome to number
#best way is to convert it to string and then check it by #reversing.
def palin(num):
  snum=str(num)
  rnum=snum[::-1]
  return rnum==snum

# if conversion to string is not allowed then:
# using while loop [O[n]]
def palindrome(num):
    n=num
    rev=0
    while num>0:
        d = num % 10
        rev = rev * 10 + d
        num = num // 10
    return rev==n

# using Recursion
def recursion(num, rev=0):
    if num==0:
        return rev
    return recursion(num//10, rev*10+num%10 )
n=121
print("True" if recursion(n)==n else "False") 
    <file_sep>s="hello sam i am your senior"
cs=[i for i in s.split() if i[0]=='s']
print(cs)
<file_sep># -*- coding: utf-8 -*-
"""
Created on Tue Jun 16 16:23:48 2020

@author: MrMaak
"""

# STRING COMPRESSION

# Given an array of characters, compress it in-place.

# The length after compression must always be smaller than or equal to the original array.

# Every element of the array should be a character (not int) of length 1.

# After you are done modifying the input array in-place, return the new length of the array.

 
# Follow up:
# Could you solve it using only O(1) extra space?

 
# Example 1:

# Input:
# ["a","a","b","b","c","c","c"]

# Output:
# Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

# Explanation:
# "aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
 

# Example 2:

# Input:
# ["a"]

# Output:
# Return 1, and the first 1 characters of the input array should be: ["a"]

# Explanation:
# Nothing is replaced.
 

# Example 3:

# Input:
# ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

# Output:
# Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

# Explanation:
# Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
# Notice each digit has it's own entry in the array.


def compression(arr):
    if arr == None or len(arr) < 1:
        return 0;
    start, end, index = 0,0,0
    while start < len(arr):
        end=start
        while end < len(arr) and arr[start]==arr[end]:
            end+=1
        arr[index]=arr[start]
        index+=1
        if end-start>1:
            for s in str(end-start):
                arr[index]=s
                index+=1
        start=end
    return index
    
arr=["a","a","b","b","c","c","c","c","c","c","c","c","c","c","c","c"]
print(compression(arr))




















<file_sep>/*Snail Sort
Given an n x n array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.
array = [[1,2,3],
         [4,5,6],
         [7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]
For better understanding, please follow the numbers of the next array consecutively:
array = [[1,2,3],
         [8,9,4],
         [7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]
This image will illustrate things more clearly:
 
NOTE: The idea is not sort the elements from the lowest value to the highest; the idea is to traverse the 2-d array in a clockwise snailshell pattern.
NOTE 2: The 0x0 (empty matrix) is represented as [[]]
------------------------------------
CODE#*/
import java.util.Arrays;
public class Snail {
public static int[] snail(int[][] array) {
    if(array[0].length <= 0)  return new int[0];
    if(array[0].length == 1) { int[] j=new int[1]; j[0]=array[0][0];return j;}
    else{
    int m=array[0].length,k=0,l=0,n=array[1].length,j=0;
    String s="";
    while(k<m&&l<n)
		     {  
		         for(int i=k;i<m;i++) s=s+" "+array[k][i];
		         k++;
		         for(int i=k;i<n;i++) s=s+" "+(array[i][n-1]);
		         n--;
		         if(k<m)
		         {
		        	 for(int i=n-1;i>=l;--i) s=s+" "+(array[m-1][i]);
			         m--;
		         }
		         if(l<n)
		         {
		        	 for(int i=m-1;i>=k;--i) s=s+" "+(array[i][l]);
			         l++;
		         }
		     }
    s=s.trim();
    String[] stra=s.split(" ");
    int[] arra = Arrays.asList(stra).stream().mapToInt(Integer::parseInt).toArray();
    return arra;
   } 
  }
}
<file_sep>''' DYNAMIC PROGRAMMING --[COIN CHANGE]-min number of coin required to give the change amount'''
def coinchange(coins,amount):
	coins.sort()
	dp=[amount+1]*(amount+1)
	dp[0]=0
	for i in range(0,amount+1):
		for j in coins:
			if j<=i:
				dp[i]=min(dp[i],1+dp[i-j])
	return dp[amount] if dp[amount]<amount else -1
print(coinchange([1,2,5],46))<file_sep>def isPowerOfFour(n: int) -> bool:
	if n==1:
		return True
	
	if n>0 and n%4==0:
		n//=4
		return isPowerOfFour(n)

print(isPowerOfFour(36)==True)<file_sep>'''
TARGET SUM --> https://leetcode.com/problems/target-sum/
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.'''

nums=[1,0]
S=1
def kaa(nums, S):

  c=0
  for i in nums:
    if i==0:
      c+=1
  
  if S > sum(nums):
    return 0;
  if (S+sum(nums))%2!=0 :
    return 0;

  s= (S+sum(nums))//2
  n=len(nums)

  k=[[0 for i in range (s+1)] for j in range(n+1)]
  for i in range(n+1):
    k[i][0]=1
  for i in range(1,s+1):
    k[0][i]=0

  for i in range(1,n+1):
    for j in range(1,s+1):
      if nums[i-1]==0:
        k[i][j] = k[i-1][j];
      elif nums[i-1]> j:
        k[i][j]= k[i-1][j]
      else:
        k[i][j]= k[i-1][j-nums[i-1]] + k[i-1][j]

  return 2**c * k[n][s];

print("Given Array {}\nNumber of Subset with -/+ given TOTAL SUM {} is {}".format(nums, S, kaa(nums, S)))


'''Basically we have to find 2 subset one for + and another for negative
so it is a Count number of subset with given difference problem.

Let us assume S as d and +ve_subset as s2 and -ve_subset as s1
Here we have to find S2-S1 equal to given difference i.e d

So eq [1]-> s2+(-s1)== s2-s1= d
eq [2]-> s2-(-s1)== s2+s1 = Total SUM
=>eq[1] + eq[2]
2s2= difference + Total SUM
s2 = (difference + Total SUM)/ 2

Hence s2 can be found i.e the required SUM'''<file_sep># -*- coding: utf-8 -*-
"""
Created on Mon Jun 15 00:50:28 2020

@author: MrMaak
"""

# Remove Duplicates from Sorted Array II
# Medium

# Given a sorted array nums, remove the duplicates in-place such that 
# duplicates appeared at most twice and return the new length.

# Do not allocate extra space for another array,
#  you must do this by modifying the input array in-place with O(1) extra memory.

# Example 1:
    
# Given nums = [1,1,1,2,2,3],
# Your function should return length = 5,
#  with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
# It doesn't matter what you leave beyond the returned length.


# Example 2:
# Given nums = [0,0,1,1,1,1,2,3,3],
# Your function should return length = 7, 
# with the first seven elements of nums being modified 
# to 0, 0, 1, 1, 2, 3 and 3 respectively.
# It doesn't matter what values are set beyond the returned length.

def removedup2(nums):
    if len(nums)==0:
        return False
    i=0
    for j in nums:
        if nums[i]==j:
            i+=1
            nums[]




nums=[1,1,1,2,2,3]
print(removedup2(nums))
























<file_sep># -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 23:17:39 2020

@author: MrMaak
"""
# WORD SEARCH

# Given a 2D board and a word, find if the word exists in the grid.

# The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

# Example:

# board =
# [
#   ['A','B','C','E'],
#   ['S','F','C','S'],
#   ['A','D','E','E']
# ]

# Given word = "ABCCED", return true.
# Given word = "SEE", return true.
# Given word = "ABCB", return false.
 

# Constraints:

# board and word consists only of lowercase and uppercase English letters.
# 1 <= board.length <= 200
# 1 <= board[i].length <= 200
# 1 <= word.length <= 10^3
# Accepted



def searchword(board, word, i):
    for i in range (0, len(board)):
        for j in range( 0, len(board[i])):
            if board[i][j]== word[0] and dfs(board, word, i, j, 0):
                return True
    return False

def dfs(board, word, i, j, count):
    if count==len(word):
        return True
    if i<0 or i>=len(board) or j<0 or j>= len(board[i]) or board[i][j]!= word[count]:
        return False
    temp= board[i][j]
    board[i][j]=""
    found= dfs(board, word, i-1, j, count+1) or dfs(board, word, i+1, j, count+1)or dfs(board, word, i, j-1, count+1) or dfs(board, word, i, j+1, count+1)
    board[i][j]=temp
    return found
    
board =[
        ['A','B','C','E'],
        ['S','F','C','S'],
        ['A','D','E','E']]
word="SEE"
print(searchword(board, word, 0))<file_sep>def myPow(x: float, n: int) -> float:
		if n==0 :
				return 1
		else :
				if n>0 :
						return power(x,n)
				else :
						return 1/power(x,-n)
def power(x,n) :
		if n==0 :
				return 1
		temp=power(x,n//2)
		ans=temp*temp
		if n%2==0 :
				return ans
		else :
				return x*ans

print(myPow(2.1,3))<file_sep>def top(x,y,m,n):
  k=[[0 for j in range(n+1)] for i in range(m+1)]
  maximum=0
  for i in range(1,m+1):
    for j in range(1,n+1):
      if x[i-1]==y[j-1]:
        k[i][j]= 1+ k[i-1][j-1]
        maximum=max(k[i][j], maximum)
      else:
        k[i][j]=0

  return maximum

x="abcdefz"
y="abcfghijxyz"
print(top(x,y,len(x), len(y)))<file_sep>class Node: 
    # Constructor to create a new node 
    def __init__(self, val): 
        self.val = val 
        self.left = None
        self.right = None

def maxPathSum(root) -> int:
	res=[-9999]
		
	def solve(root, res):
			
			if root is None:
					return 0
			
			l= solve(root.left, res)
			r=solve(root.right, res)
			
			temp=max(l,r)+root.val
			if root.left is None and root.right is None:
				temp=max(temp, root.val)

			ans=max(temp, root.val+l+r)
			res[0] =max(res[0], ans)
			
			return temp
	
	solve(root, res)
	return res[0]
    
# Driver program to test above function 
root = Node(-15) 
root.left = Node(5) 
root.right = Node(6) 
root.left.left = Node(-8) 
root.left.right = Node(1) 
root.left.left.left = Node(2) 
root.left.left.right = Node(6) 
root.right.left = Node(3) 
root.right.right = Node(9) 
root.right.right.right= Node(0) 
root.right.right.right.left = Node(4) 
root.right.right.right.right = Node(-1) 
root.right.right.right.right.left = Node(10) 
  
print ("Max pathSum of the given binary tree is{}".format( maxPathSum( root)))

'''
Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.
The maximum sum path may or may not go through root. For example, in the following binary tree, the maximum sum is 27(3 + 6 + 9 + 0 – 1 + 10). Expected time complexity is O(n).
'''<file_sep>import heapq
points=[[3,3],[5,-1],[-2,4]]
K=2
heap = []
heapq.heapify(heap)
for i in range(len(points)):
		x = points[i][0]
		y = points[i][1]
		d = (x*x + y*y)
		heapq.heappush(heap,[d, [x, y]])
res = []
print(heap)

res.append([y for x, y in heapq.nsmallest(K, heap)])

out=[]
out=res.pop()
print(out)

#maxheap<file_sep>/*Perimeter of squares in a rectangle
The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It's easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80 
Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing: 

#Hint: See Fibonacci sequence
#Ref: http://oeis.org/A000045
The function perimeter has for parameter n where n + 1 is the number of squares (they are numbered from 0 to n) and returns the total perimeter of all the squares.
perimeter(5)  should return 80
perimeter(7)  should return 216
CODE#*/
import java.math.BigInteger;
public class SumFct {
	public static BigInteger perimeter(BigInteger n) {
		BigInteger a,temp,out,sum,i;
    a=BigInteger.valueOf(1);temp=BigInteger.valueOf(0);out=BigInteger.valueOf(0);
    sum  = BigInteger.valueOf(0);i = BigInteger.valueOf(0);
    while(i.compareTo(n)<0){ 
        out=a.add(temp);
        temp=a;
        a=out;
        sum=sum.add(out);
        i=i.add(BigInteger.valueOf(1));}
  return (sum.add(BigInteger.valueOf(1))).multiply(BigInteger.valueOf(4));
}}
<file_sep># -*- coding: utf-8 -*-
"""
Created on Sat Jun 13 00:23:51 2020

@author: MrMaak
"""

'''Given two integers n and k, 
return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]'''


rst=[]
def possible(curr,start):
    if len(curr)==k:
        rst.append(curr)
        return
    for i in range(start,n+1):
        possible(curr+[i],i+1)

n,k=4,2
possible([],1)
print(rst)








<file_sep># -*- coding: utf-8 -*-
"""
Created on Sat Jun 20 00:32:47 2020

@author: MrMaak
"""
# Given two integers dividend and divisor, 
#divide two integers without using 
#multiplication, division and mod operator.

# Return the quotient after dividing dividend by divisor.

# The integer division should truncate toward zero,
# which means losing its fractional part. 
#For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

# Example 1:

# Input: dividend = 10, divisor = 3
# Output: 3
# Explanation: 10/3 = truncate(3.33333..) = 3.
# Example 2:

# Input: dividend = 7, divisor = -3
# Output: -2
# Explanation: 7/-3 = truncate(-2.33333..) = -2.
# Note:

# Both dividend and divisor will be 32-bit signed integers.
# The divisor will never be 0.
# Assume we are dealing with an environment which could only 
#store integers within the 32-bit signed integer range:[−231,231 − 1].
# For the purpose of this problem, assume that your function 
#returns 231 − 1 when the division result overflows.

def divison(dividend, divisor):
    neg = (dividend< 0) != (divisor<0)
    dividend= abs(dividend)
    divisor = div = abs(divisor)
    ans, count = 0, 1
    while dividend >= divisor :
        dividend-= div
        div+= div
        ans+= count
        count+= count
        if dividend < div:
            div=divisor
            count=1
    if neg:
        return max(-ans, -2147483648)
    else:
        return min(ans, 2147483648)
    

print(divison(10, 3))
<file_sep>/*Kata Task
A bird flying high above a mountain range is able to estimate the height of the highest peak.

Can you?

Example
The birds-eye view
^^^^^^
 ^^^^^^^^
  ^^^^^^^
  ^^^^^
  ^^^^^^^^^^^
  ^^^^^^
  ^^^^
The bird-brain calculations
111111
 1^^^^111
  1^^^^11
  1^^^1
  1^^^^111111
  1^^^11
  1111
  ----------------------------
111111
 12222111
  12^^211
  12^21
  12^^2111111
  122211
  1111
  ------------------------------
111111
 12222111
  1233211
  12321
  12332111111
  122211
  1111
Height = 3*/
public class birdmountain {
	public static void main(String[] args) {
		char[][] mountains={
			      "^^^^^^        ".toCharArray(),
			      " ^^^^^^^^     ".toCharArray(),
			      "  ^^^^^^^     ".toCharArray(),
			      "  ^^^^^       ".toCharArray(),
			      "  ^^^^^^^^^^^ ".toCharArray(),
			      "  ^^^^^^      ".toCharArray(),
			      "  ^^^^        ".toCharArray()
			    };      
		int my=mountains.length;
		int mx=mountains[0].length;
		char[][] arr=mountains.clone();
		int height=0;
		boolean f;
		do {
			f=false;
			char[][] next=new char[my][mx];
			for (int y = 0; y < my; y++) 
			{
		        for (int x = 0; x < mx; x++) 
		        {
		          next[y][x] = arr[y][x];
		          if (arr[y][x] == '^' && (y == 0 ||  x == 0 || y == my-1 || x == mx-1 ||
		            arr[y-1][x] == ' ' || arr[y+1][x] == ' ' || arr[y][x-1] == ' ' || arr[y][x+1] == ' ')) 
		          		{
				            f = true;
				            next[y][x] = ' ';
				          }
		        	}
		      }
		if(f) { height++; arr=next;}
		}while (f);
		System.out.println(height);
	}

}
<file_sep>def sorting(arr,n):
  #BASE CASE
  if n==1:
    return

  #INDUCTION
  sorting(arr,n-1)

  #HYPOTHETICAL
  last=arr[n-1]
  j=n-2
  
  while j>=0 and arr[j]>last :
    arr[j+1]=arr[j]
    j-=1
  arr[j+1]=last

arr=[5,1,7,3,5,-1]
print("orignal array-->{}".format(arr))
sorting(arr,len(arr))
print("sorted array-->{}".format(arr))<file_sep># -*- coding: utf-8 -*-
"""
Created on Wed Jun 24 00:50:42 2020

@author: MrMaak
"""
''' Input:

Given an array A of
-positive
-sorted
-no duplicate
-integer

A positive integer k


Output:

Count of all such subsets of A,
Such that for any such subset S,
Min(S) + Max(S) = k
subset should contain atleast two elements

1. Backtracking approach to get subsets
2. Get min and max of subset
3. Add min and max and put them in Hashmap (or update the count)
4. repeat this process for all subsets
5. search for k in hashmap and return count of k

input: {1,2,3,4,5}

subsets: 
1, 2, 3, 4, 5, {1,2},{1,3}
k = 5

count = 5

{1, 4},{2,3} {1,2,4}, {1,2,3,4} {1,3,4}'''

def countSubsets(nums,k):
    nums.sort()
    count = 0
    for i in range(len(nums)):
        for j in range(i,len(nums)):
            if nums[i]+nums[j]>k:
                break
            if nums[i]+nums[j]==k:
                count += 2**((j-i-1) if j-i>1 else 0)
    print(count)
    return count

countSubsets([1,2,3,4,5], 5)




<file_sep>
def stair(n):
	if n<=1:
		return n
	 
	ways= stair(n-1) + stair(n-2)
	return ways

n=4
print(stair(n+1))<file_sep>def sub(x,y,m,n):
  #BASE CONDITION
  if m==0 or n==0:
    return 0
  
  #memorization
  if t[m][n]!=-1:
    return t[m][n]

  #CHOICE DIAGRAM
  if x[m-1]==y[n-1]:
    t[m][n]= 1+ sub(x,y,m-1,n-1)
    return t[m][n]
  else:
    t[m][n]=max(sub(x,y,m-1,n), sub(x,y,m,n-1))
    return t[m][n]

def top(x,y,m,n):
  k=[[0 for j in range(n+1)] for i in range(m+1)]

  for i in range(1,m+1):
    for j in range(1,n+1):
      if x[i-1]==y[j-1]:
        k[i][j]= 1+ k[i-1][j-1]
      else:
        k[i][j]=max(k[i-1][j], k[i][j-1])

  return k[m][n]

x="abcdefz"
y="abcfghijxyz"
t=[[-1 for j in range(len(y)+1)] for i in range(len(x)+1)]
print(sub(x,y,len(x), len(y)))
print(top(x,y,len(x), len(y)))<file_sep>def reverse(arr):
  if len(arr)==1:
    return
  l=arr.pop(len(arr)-1)
  reverse(arr)
  insert(arr,l)

def insert(arr, element):
  if len(arr)==0:
    arr.append(element)
    return
  p=arr.pop(len(arr)-1)
  insert(arr,element)
  arr.append(p)

arr=[1,2,3,4,5]
print("orignal array-->{}".format(arr))
reverse(arr)
print("reversed array-->{}".format(arr))<file_sep>def mah(arr):
	stack=[]
	left=[]
	for i in range(len(arr)):
		if len(stack)==0:
				left.append(-1)
		elif len(stack)>0 and stack[-1][0]<arr[i]:
				left.append(stack[-1][1])
		elif len(stack)>0 and stack[-1][0]>=arr[i]:
				while len(stack)>0 and stack[-1][0]>=arr[i]:
						stack.pop()
				if len(stack)==0:
						left.append(-1)
				else:
						left.append(stack[-1][1])
		stack.append([arr[i],i])
	stack=[]
	right=[]
	#NEXT SMALLER TO RIGHT
	for i in range(len(arr)-1,-1,-1):
		if len(stack)==0:
				right.append(len(arr))
		elif len(stack)>0 and stack[-1][0]<arr[i]:
				right.append(stack[-1][1])
		elif len(stack)>0 and stack[-1][0]>=arr[i]:
				while len(stack)>0 and stack[-1][0]>=arr[i]:
						stack.pop()
				if len(stack)==0:
						right.append(len(arr))
				else:
						right.append(stack[-1][1])
		stack.append([arr[i],i])
	right=right[::-1]

	out=[0] *len(arr)
	for i in range(len(arr)):
		out[i]=(right[i]-left[i]-1)*arr[i]
	return max(out)

def MaxAreaRectangleinbinarymatrix(matrix):
	maz=[]
	for u in matrix[0]:
		maz.append(u)
	maxi=mah(maz)
	for i in range(1,len(matrix)):
		for j in range(len(matrix[i])):
			if matrix[i][j]==0:
				maz[j]=0
			else:
				maz[j]=maz[j]+matrix[i][j]
		maxi=max(maxi, mah(maz))
	return maxi

matrix=[[0,1,1,0],[1,1,1,1],[1,1,1,1],[1,1,0,0]]
print(MaxAreaRectangleinbinarymatrix(matrix))<file_sep>/*Count the number of Duplicates
Write a function that will return the count of distinct case-insensitive alphabetic characters and numeric digits that occur more than once in the input string. The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.
Example
"abcde" -> 0 # no characters repeats more than once
"aabbcde" -> 2 # 'a' and 'b'
"aabBcde" -> 2 # 'a' occurs twice and 'b' twice (`b` and `B`)
"indivisibility" -> 1 # 'i' occurs six times
"Indivisibilities" -> 2 # 'i' occurs seven times and 's' occurs twice
"aA11" -> 2 # 'a' and '1'
"ABBA" -> 2 # 'A' and 'B' each occur twice
CODE#*/
public class CountingDuplicates {
  public static int duplicateCount(String text) {
    int i=0,j=0,c=0,a=0;
    text=text.toLowerCase();
    for(i=0;i<text.length();i++)
    {for(j=0;j<text.length();j++)
    {
      if(text.charAt(i)==text.charAt(j))
      {c++;}
    }
    if(c>1){a++;}
    String d= String.valueOf(text.charAt(i)).trim();
    text=text.replaceAll(d,"");
    c=0;
    i=0;
    j=0;
    }
  return a;
}
}
<file_sep># -*- coding: utf-8 -*-
"""
Created on Sat Jun 13 01:19:29 2020

@author: MrMaak
"""


#RECURSIVE IMPLEMENTATION OF
#CONVERTING A STRING TO AN INTEGER

def convert(s,num):
    if len(s)==1:
        return int(s)+ num*10
    num = int(s[0]) + num*10
    return convert(s[1:],num)
    
s="123"
convert(s,0)<file_sep>arr=[3,4,0,0]
stack=[]
left=[]
#NEXT SMALLER TO LEFT
for i in range(len(arr)):
		if len(stack)==0:
				left.append(-1)
		elif len(stack)>0 and stack[-1][0]<arr[i]:
				left.append(stack[-1][1])
		elif len(stack)>0 and stack[-1][0]>=arr[i]:
				while len(stack)>0 and stack[-1][0]>=arr[i]:
						stack.pop()
				if len(stack)==0:
						left.append(-1)
				else:
						left.append(stack[-1][1])
		stack.append([arr[i],i])
stack=[]
right=[]
#NEXT SMALLER TO RIGHT
for i in range(len(arr)-1,-1,-1):
	if len(stack)==0:
			right.append(len(arr))
	elif len(stack)>0 and stack[-1][0]<arr[i]:
			right.append(stack[-1][1])
	elif len(stack)>0 and stack[-1][0]>=arr[i]:
			while len(stack)>0 and stack[-1][0]>=arr[i]:
					stack.pop()
			if len(stack)==0:
					right.append(len(arr))
			else:
					right.append(stack[-1][1])
	stack.append([arr[i],i])
right=right[::-1]

out=[0] *len(arr)
for i in range(len(arr)):
	out[i]=(right[i]-left[i]-1)*arr[i]
print("The maximum area possible in given gistogram is {}".format(max(out)))
maz=[]
matrix=[[1,2],[3,4]]
for u in matrix[0]:
	maz.append(u)
maz[0]=12
print(maz)
print(matrix)<file_sep>'''find all the prime number till N'''
import math
n=30
arr=[1]*(n+1)
i=2
while i*i<=n:
	if arr[i]==1:
		for j in range((i*i),n+1,i):
			arr[j]=0
	i+=1
count=0
for i in arr:
	if i==1:
		count+=1
print(arr)
print("Numbers of prime number in range",n,"is",count)<file_sep>from functools import lru_cache
@lru_cache(100)
def grammar(n,k):
  if n==1 or k==1:
    return 0

  mid=(2**(n-1))//2

  if k<=mid:
    return int(grammar(n-1,k))
  else:
    return int(not(grammar(n-1,k-mid)))

print(grammar(3,3))


#0
#01
#0110
#01101001<file_sep>arr=[1,2,4,8,9,12,16]
n=len(arr)
c=4
low, high, best =arr[0], arr[n-1], 0
while (low<=high):
	mid=(low+high+1)/2
	left, cnt= 0, 1
	for (i,c) in zip(range(1,n), range(1,c)):
		if (arr[i]-arr[left])>=mid:
			left=i
			cnt+=1
	if cnt>= c:
		low=mid+1
		best=mid
	else:
		high=mid-1
print(int(best))<file_sep># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import sys
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        
        if root is None:
            return 0
        
        res=[-99999]
        
        def solve(root, res):
            
            if root is None:
                return 0
            
            l = solve(root.left, res)
            r = solve(root.right, res)
            
            temp= 1+ max(l,r) #PASS ABOVE
            ans = max(temp, 1+l+r) #INCLUDE IN ANS
            res[0] = max(res[0], ans)
            
            return temp
        
        solve(root,res)
        return res[0] -1
    
##LEETCODE<file_sep>#6--5--4--15
for i in range(10):
  n=int(input("Enter a number"))
  if n%9!=0:
    x=n%9
  else:
    x=9
  print(x)<file_sep>def per(i,o):
  if len(i)==1:
    print(o+i[0])
    return

  o1=o
  o2=o
  o1=o1+i[0]
  o2=o2+i[0]+"_"
  i=i[1:]
  per(i,o1)
  per(i,o2)

per("abc","")

'''OUTPUT:- 
abc
ab_c
a_bc
a_b_c
'''<file_sep># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        
        res=[-9999]
        
        def solve(root, res):
            
            if root is None:
                return 0
            
            l= solve(root.left, res)
            r=solve(root.right, res)
            
            temp=max(max(l,r)+root.val , root.val)
            ans=max(temp, root.val+l+r)
            res[0] =max(res[0], ans)
            
            return temp
        
        solve(root, res)
        return res[0]

#LEETCODE
'''
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Input: [1,2,3]

       1
      / \
     2   3

Output: 6
'''<file_sep>import heapq
arr=[1,1,1,2,2,3]
k=2
freq={}
for i in arr:
		if i in freq:
				freq[i]+=1
		else:
				freq[i]=1

arr=[]
for x,y in freq.items():
		arr.append([y,x])

heap = []
heapq.heapify(heap)
for i in range(len(arr)):
	heapq.heappush(heap,arr[i])

res = []
res.append([y for x, y in heapq.nlargest(k, heap)])

out=[]
out=res.pop()
print(out)

print("dhd;")<file_sep>def binarysearch(arr,low,high,x):
	if high<low:
		return -1

	mid=low+(high-low)//2

	if x==arr[mid]:
		return mid
	elif x<arr[mid]:
		return binarysearch(arr,low,mid-1,x)
	elif x>arr[mid]:
		return binarysearch(arr,mid+1,high,x)
    
arr=[1,5,8,12,13]
print(6," is at index ",binarysearch(arr,0,len(arr)-1,6))<file_sep>def isPrime(i):
  count=1
  for j in range(1,i//2+1):
    if i%j==0:
      count+=1
  if count==2:
    return 1
  return 0

def factor(num,arr):
  for i in range(1,num//2+1):
    if num%i==0 and isPrime(i):
      arr.append(i)

num=int(input("Enter a number...\n"))
arr=[]
factor(num, arr)
print(arr)<file_sep># -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 13:47:45 2020

@author: MrMaak
"""
#SUBSET SUM PROBLEM

#RECURSIVE APPROACH
def subrec(arr, s, n):
    #BASE CASE
    if s==0:
        return True
    if n==0 and s !=0:
        return False
    
    #CHOICE DIAGRAM
    if arr[n-1] > s:
        return subrec(arr, s, n-1)
    else:
        return ((subrec(arr, s-arr[n-1], n-1)) or (subrec(arr, s, n-1)))
    
#DP --> MEMORIZATION
def submem(arr, s, n):
    #BASE CASE
    if s==0:
        return True
    if n==0 and s !=0:
        return False
    
    if t[n][s] != -1:
        return t[n][s]
    
    #CHOICE DIAGRAM
    if arr[n-1] > s:
        t[n][s]= submem(arr, s, n-1)
        return t[n][s]
    else:
        t[n][s]= ((submem(arr, s-arr[n-1], n-1)) or (submem(arr, s, n-1)))
        return t[n][s]

#DP --> TOP-DOWN
def topdown(arr, s, n):
    for i in range(1,(s+1)):
        k[0][i]=False
    for i in range(n+1):
        k[i][0]=True
        
    for i in range(n+1):
        for j in range(s+1):
            if arr[i-1]> j:
                k[i][j]=k[i-1][j]
            else:
                k[i][j]= k[i-1][j-arr[i-1]] or k[i-1][j]
            
    return k[n][s]

arr=[1,2,3,5,14]
s=6
n=len(arr)
t=[[-1 for i in range(s+1)] for j in range(n+1)]
k=[[False for i in range(s+1)] for j in range(n+1)]

print("FOUND THE SUM RECURSIVE= {}? --> {}".format(s,subrec(arr,s, n)))
print("FOUND THE SUM MEMORIZATION= {}? --> {}".format(s,submem(arr,s, n)))
print("FOUND THE SUM TOPDOWN = {}? --> {}".format(s,topdown(arr,s,n)))<file_sep>def fib_fast(n):
    if n <= 1:
        return n
    a = [0, 1]
    while True:
        a.append((a[-1]+a[-2]) % 10)
        if a[-1] == 1 and a[-2] == 0:
            a.pop()
            a.pop()
            break
    return a[n % len(a)]
n=7
print((fib_fast(n+1))*(fib_fast(n) % 10))<file_sep>def per(i,o,s):
  if i=="":
    s.add(o)
    return
  
  o1=o
  o2=o
  o1=o1+i[0].lower()
  o2=o2+i[0].upper()
  i=i[1:]
  per(i,o1,s)
  per(i,o2,s)

s=set()
per("a1B2","",s)
print(s)

'''
OUTPUT:-
A1b2
a1B2
A1B2
a1b2
'''<file_sep># -*- coding: utf-8 -*-
"""
Created on Fri Jun 12 23:15:49 2020

@author: MrMaak
"""

''' Given a set of characters and a positive integer k, 
possibleint all possible strings of length k that can be formed 
from the given set.
Input: 
set[] = {'a', 'b'}, k = 3

Output:
aaa
aab
aba
abb
baa
bab
bba
bbb


Input: 
set[] = {'a', 'b', 'c', 'd'}, k = 1
Output:
a
b
c
d

'''

rst=[]
def possible(curr):
  if len(curr)==k:
    rst.append(curr)
    return
  for i in aset:
    possible(curr+i)
aset={'1','2'}
k=4
possible("")
print(rst)<file_sep>'''from CountNUMBEROFSUBSETWITHGIVENDIFFERENCE import *
print("\n\n")
from TARGET_SUM import *'''
print("\n\n")
from combinationoflengthR import *<file_sep>def areConsecutive(m, n): 
	if ( n < 1 ): 
		return False 
	Min = min(m) 
	Max = max(m) 
	if (Max - Min + 1 == n): 
		visited = [False for i in range(n)] 
		for i in range(n): 
			if (visited[m[i] - Min] != False): 
				return False
			visited[m[i] - Min] = True
		return True
	return False 

def check():
	arr=[5,4,3,2,1]
	maxi=-999
	for i in range(len(arr)):
		curr=arr[i]
		res=0
		l=[]
		for j in range(len(arr)):
			temp=arr[j]
			if curr<= temp:
				res+=curr
				l.append(j)
		c=res

		if areConsecutive(l, len(l)):
			maxi=max(maxi, c)

	return maxi

print(check())<file_sep>def activate(arr):



	n=len(arr)
	i=0
	while(i<=n-1):
		try:
			if arr[i]==0:
				i+=1
			
			if arr[i]==1:
				arr[i-2]=1
				arr[i-1]=1
				arr[i+1]=1
				arr[i+2]=1
				i+=3
		
		except IndexError:
			pass

	if sum(arr)==n-1:



'''
Problem Description

There is a corridor in a Jail which is N units long. Given an array A of size N. The ith index of this array is 0 if the light at ith position is faulty otherwise it is 1.

All the lights are of specific power B which if is placed at position X, it can light the corridor from [ X-B+1, X+B-1].

Initially all lights are off.

Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted.
'''
		<file_sep>def mySqrt(x: int) -> int:
		
		l=0
		r=x
		
		while l+1<r:
				mid= l+(r-l)//2
				
				sq=mid * mid
				if sq==x:
						return mid
				elif sq>x:
						r=mid
				else:
						l=mid
		
		if l*l ==x:
				return l
		elif r*r==x:
				return r
		else:
				return l

print(mySqrt(8))<file_sep>#TYPE OF UNBOUNDED KNAPSACK.

n=10
k=[[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
  k[0][i]=0
for i in range(n+1):
  k[i][0]=1
    
for i in range(1,n+1):
  for j in range(1,n+1):
    if i > j:
      k[i][j]=k[i-1][j]
    else:
      k[i][j]= max(i * k[i][j-i] , k[i-1][j])

print(k)
print(k[n-1][n]) <file_sep>
n, k = [int(c) for c in input().split()]
l=[int(c) for c in input().split()]
p=[0]* n
print(l)
queries=[]
for _ in range(k):
  t = [int(c) for c in input().split()]
  queries.append(t)
	
def update(arr):
	p=[0]*len(arr)
	p[0]=arr[0]
	for i in range(1,len(arr)):
		p[i]=arr[i]+ p[i-1]

for i in queries:
	if i[0]==1:
		
		for j in range(i[1]-1, i[2]):
			if l[j]==0:
				l[j]=1
			else:
				l[j]==0
			update(l)
	else:
		summ=0
		for j in range(i[1]-1, i[2]):
			summ+=l[j]
		print(summ%(10^9 + 7))


'''Sample Input:
9 6
1 0 0 1 1 0 0 0 1
1 2 6
1 4 8
2 1 9
2 3 5
1 2 7
2 5 8

Sample Output:
41
12
8

Explanation:
Array P initially: [1, 1, 1, 2, 3, 3, 3, 3, 4]
After 1st query:
A: [1, 1, 1, 0, 0, 1, 0, 0, 1]
P: [1, 2, 3, 3, 3, 4, 4, 4, 5]
After 2nd query:
A: [1, 1, 1, 1, 1, 0, 1, 1, 1]
P: [1, 2, 3, 4, 5, 5, 6, 7, 8]
'''<file_sep>list=[]
s=20
arr=[3,2,2,3,4,6]
for k in range(1,5):
 for i in arr:
  list.append(i/k)
 total=sum(list)
 list=[]
 if total<s:
  break
print(k)
  <file_sep>def leader(arr):
	out=[]
	n=len(arr)
	curr=arr[n-1]
	out.append(curr)

	for i in range(n-2, -1, -1):
		if arr[i]> curr:
			out.append(arr[i])
			curr=arr[i]
	
	return out

arr=[16, 17, 4, 3, 5, 2]
print(leader(arr))<file_sep>arr=[1,20,6,4,5]
def merge_sort(arr,n):
	temp=[0]*n
	return mergesort(arr,temp,0,len(arr)-1)
def mergesort(arr,temp,left,right):				# MERGE SORT BASICS STEPS
	count=0
	if left<right:
		mid=(left+right)//2
		count+=mergesort(arr,temp,0,mid)		# LEFT SIDE ARRAY
		count+=mergesort(arr,temp,mid+1,right)	# RIGHT SIDE ARRAY
		count+=merge(arr,temp,left,mid,right)	# MERGING BOTH LEFT AND RIGHT ARRAY
	return count
def merge(arr,temp,l,mid,r):
	i=l 										# i for left array 
	j=mid+1 									# j for right array
	k=l 										# k for temp array
	count=0
	while i<=mid and j<=r: 						# Conditions are checked to make sure that i and j don't exceed their subarray limits.
		if arr[i]<=arr[j]: 						# NO INVERSION
			temp[k]=arr[i]						# just copying elements to temp
			i+=1
			k+=1
		else:									# INVERSION 
			temp[k]=arr[j]
			count+=mid-i+1						# In merge process, let i is used for indexing left sub-array and j for right sub-array.
												# At any step in merge(), if a[i] is greater than a[j], then there are (mid – i) inversions.
												# because left and right subarrays are sorted, so all the remaining elements in left-subarray
												# (a[i+1], a[i+2] … a[mid]) will be greater than a[j]
			j+=1
			k+=1
	while i<=mid:								# Copy the remaining elements of LEFT subarray into temporary array.
		temp[k]=arr[i]
		i+=1
		k+=1
	while j<=r:									# Copy the remaining elements of RIGHT subarray into temporary array.
		temp[k]=arr[j]
		j+=1
		k+=1
	for x in range(l, r + 1):					# Copy the elements of temp into arr.
		arr[x] = temp[x]
	return count
print(merge_sort(arr,len(arr)))<file_sep>/*BAGELS
Here's a seemingly simple challenge. We're giving you a class called bagel, exactly as it appears below. All it really does is return an int, specifically 3.
sealed class Bagel {
    public int Value { get; private set; } = 3;
}
The catch? For the solution, we're testing that the result is equal to 4. But as a little hint, the solution to this Kata is (almost) exactly the same as the example test cases.
-------------------------------
CODE#*/
import java.lang.reflect.Field;
import java.lang.reflect.Modifier;
public class BagelSolver {
  public static Bagel getBagel() {
      try {
            Field f = Boolean.class.getField("TRUE");
            Field modifiers = Field.class.getDeclaredField("modifiers");
            modifiers.setAccessible(true);
            modifiers.setInt(f, f.getModifiers() & ~Modifier.FINAL);
            f.set(null, false);
        } catch (Exception e){}
    return new Bagel();
  }
}
<file_sep># -*- coding: utf-8 -*-
"""
Created on Tue Jun 16 02:01:02 2020

@author: MrMaak
"""


#Longest Common Prefix
# Write a function to find the longest common prefix string 
# amongst an array of strings.

# If there is no common prefix, return an empty string "".

# Example 1:

# Input: ["flower","flow","flight"]
# Output: "fl"
# Example 2:

# Input: ["dog","racecar","car"]
# Output: ""
# Explanation: There is no common prefix among the input strings.
# Note:

# All given inputs are in lowercase letters a-z.

def longestCommonPrefix(strs):
    prefix = strs[0] if strs else ''
    while True:
        if all(s.startswith(prefix) for s in strs):
            return prefix
        prefix = prefix[:-1]
print(longestCommonPrefix(["flower","flow","flight"]))



<file_sep>package javas;
/*Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

The result will be an array of arrays or of tuples (in C an array of Pair) or a string, each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

#Examples:

list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) --> [[42, 2500], [246, 84100]]*/
import java.util.ArrayList;
public class recreationinteger {

	public static void main(String[] args) {
		ArrayList<Long> divisors = new ArrayList<Long>();
        ArrayList<ArrayList<Long>> res = new ArrayList<ArrayList<Long>>();
        long m=1,n=42;
        for (long c = m; c <= n; c++)
        {
            divisors.clear();
            for (long i = 1; i <= c / 2; i++) 
            {
                if (c % i == 0) 
                    divisors.add(i);
            }
            divisors.add(c);
            long sum = new Long(0);
            for (int i = 0; i < divisors.size(); i++) {
                sum += (long) Math.pow(divisors.get(i).longValue(), 2);
            }
            Double d = new Double(Math.sqrt(sum));
            if (d.toString().substring(d.toString().indexOf('.')).equals(".0")) 
            {
                ArrayList<Long> r = new ArrayList<Long>();
                r.add(c);
                r.add(sum);
                res.add(r);
            }
        }
        System.out.println(res);
	}
}
<file_sep>def compute_min_refills(distance, tank, stops):
	fuel=tank
	count=0
	stops += [distance, distance]
	for i in range(len(stops)-1):
		if fuel<stops[i]:
			return -1
		if fuel<stops[i+1]:
			fuel=stops[i]+tank
			count+=1
	return count
print(compute_min_refills(200,250,[100,150]))

<file_sep>print("Hello <NAME>")
<file_sep>/*Nice Array
A Nice array is defined to be an array where for every value n in the array, there is also an element n-1 or n+1 in the array.
example:
[2,10,9,3] is Nice array because

2=3-1
10=9+1
3=2+1
9=10-1
Write a function named isNice/IsNice that returns true if its array argument is a Nice array, else false. You should also return false if input array has no elements. */

import java.util.ArrayList;
public class nicearray {
	public static void main(String[] args) {
	Integer[] arr= {2,10,9,3};
	System.out.println(st(arr));
	}
	private static boolean st(Integer[] arr) {
		 ArrayList<Integer> ar=new ArrayList<Integer>();
		 ArrayList<Integer> ar2=new ArrayList<Integer>();
		 for(int i=0;i<arr.length;i++)  ar.add(arr[i]);
		 for(int k=0;k<arr.length;k++) 
				if(ar.contains(arr[k]+1)||ar.contains(arr[k]-1)) ar2.add(arr[k])  ;
	     if(!(ar2.size()==arr.length)||arr.length==0) return false;
	     else  return true;
	} }
<file_sep>def lcsp(m,n):
	for i in range(1,m+1):
		for j in range(1,n+1):
			if x[i-1]==y[j-1]:
				t[i][j] =1+t[i-1][j-1]
			else:
				t[i][j]=max(t[i-1][j], t[i][j-1])

x="abcdef"
y="acehgfhgk"
t=[[0 for j in range(len(y)+1)] for i in range(len(x)+1)]
lcsp(len(x),len(y))

#PRINT
i, j=len(x),len(y)
s=""
while i>0 and j>0:
	if x[i-1]==y[j-1]:
		s+=x[i-1]
		i-=1
		j-=1
	else:
		if t[i][j-1]> t[i-1][j]:
			j-=1
		else:
			i-=1
s=s[-1::-1]
print(s)<file_sep>class Node():
	def __init__(self, data, left=None, right= None):
		self.left= left
		self.right=right
		self.data=data

def ctree(preorder, dict,start, end, pindex ):
	root= Node(preorder[pindex])
	pindex= pindex+1

	if pindex==len(preorder):
		return root, pindex
	
	index= dict.get(preorder[pindex])

	if start<= index and index + 1<= end - 1:
		root.left, pindex= ctree(preorder, dict, start, index, pindex)
		root.right, pindex= ctree(preorder, dict, index+1, end-1, pindex)

	return root, pindex

# Driver Code 
preorder = [1, 2, 4, 5, 3, 6, 8, 9, 7]
postorder = [4, 5, 2, 8, 9, 6, 7, 3, 1]
dict={}
for i, e in enumerate(postorder):
	dict[e]=i
start=0
end=len(postorder)-1
pindex=0
root=ctree(preorder, dict,start, end, pindex )[0]

def inorder(root):
	if root:
		inorder(root.left)
		print(root.data)
		inorder(root.right)

inorder(root)<file_sep>def rev(word):
	c=0
	for i in range(2,word):
		b=True;
		for j in range(2,i):	
			if i%j==0:
				b=False
				break
		if b:
			c+=1
	return c
print(rev(12))<file_sep># floor(log4(num))=ceil(log4(num) 

import math

def isPowerOfFour(n: int) -> bool:
	if n==0:
		return False
	return math.floor(math.log(n,4))==math.ceil(math.log(n,4))

print(isPowerOfFour(-2147483648))<file_sep># Uses python3
import sys

def get_fibonacci_last_digit_naive(n):
    f=[0,1]
    for i in range(2,n+1):
        f.append((f[i-1]+f[i-2])%10)
    return (f[n])
if __name__ == '__main__':
    input = sys.stdin.read()
    n = int(input)
    print(get_fibonacci_last_digit_naive(n))
<file_sep>def floor(arr, target):
  res=-1
  low,high=0,len(arr)-1
  while low<=high:
    mid=low+(high-low)//2
    if arr[mid]>target:
      high=mid-1
    elif arr[mid]<target:
      low=mid+1
      res=arr[mid]
    else:
      return arr[mid]
  return res

def ceil(arr,target):
  res=-1
  low,high=0,len(arr)-1
  while low<=high:
    mid=low+(high-low)//2
    if arr[mid]>target:
      high=mid-1
      res=arr[mid]
    elif arr[mid]<target:
      low=mid+1
    else:
      return arr[mid]
  return res

arr=[10,20,30,40]
target=25
f=floor(arr,target)
c=ceil(arr,target)
if target-f < c-target:
  print(f)
else:
  print(c)<file_sep>import sys
from collections import namedtuple
Item = namedtuple("Item", "value weight")
def get_optimal_value(capacity, weights, values):
	value=0
	weight_value_pairs = sorted([Item(v, w) for v, w in zip(values, weights)],key=lambda i: i.value / i.weight,reverse=True)
	current_weight=0
	final_value=0.0
	for i in weight_value_pairs:
		if current_weight+i.weight<=capacity:
			current_weight+=i.weight
			final_value+=i.value
		else:
			remain=capacity-current_weight
			final_value+=i.value*(remain/i.weight)
			break
	return final_value
capacity=50
values=[60,100,120]
weights=[20,50,30]
print(get_optimal_value(capacity,weights,values))<file_sep>def majority(arr,low,size):
	m={}
	for i in range(size):
		if arr[i] in m:
			m[arr[i]]+=1
		else:
			m[arr[i]]=1
	count=0
	for key in m:
		if m[key]>size//2:
			count=1
			break
	print(m)
	if count==1:
		return 1
	else:
		return 0
arr=[1,2,3,1]
size=len(arr)
print(majority(arr,0,size))<file_sep>''' Add 2 numbers represented as string / Sum of two large numbers
Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers.
Examples:
Input  : str1 = "3333311111111111", 
         str2 =   "44422222221111"
Output : 3377733333332222

Input  : str1 = "7777555511111111", 
         str2 =    "3332222221111"
Output : 7780887733332222'''
def addstring(num1,num2):
	# n2 must be greater than n1
	if len(num1)>len(num2):
		temp=num1
		num1=num2
		num2=temp
	diff=len(num2)-len(num1)
	carry=0
	out=""
	#for sum
	for i in range(len(num1)-1,-1,-1):   
		sum=((ord(num1[i])-ord('0'))+int((ord(num2[i+diff])-ord('0'))) + carry) 
		out=out+str(sum%10)
		carry=sum//10
	# Add remaining digits of str2[] 
	for i in range(diff-1,-1,-1):
		sum=ord(num2[i])-ord('0')+carry
		out=out+str(sum%10)
		carry=sum//10
	if carry:
		out=out+str(carry)
	return out[::-1]
print (addstring("9","9"))
<file_sep>import sys
def coinmin(arr,s):
  n=len(arr)

  k=[[0 for i in range(s+1)] for j in range(n+1)]

  for i in range(s+1):
    k[0][i]=sys.maxsize-1
  for i in range(1,n+1):
    k[i][0]=0


  for i in range(1,n+1):
    for j in range(1,s+1):
      if arr[i-1]> j:
        k[i][j]=k[i-1][j]
      else:
        k[i][j]= min(k[i][j-arr[i-1]], k[i-1][j])
  
  return k[n][s]

arr=[1,2,3]
s=5
if s<0:
  print("NOT POSSIBLE")
else:
  print("{} min coin is required to get sum= {} from coins={}".format(coinmin(arr,s),s,arr))
<file_sep>class Solution:
    def search(self, arr: List[int], target: int) -> int:
        
        if len(arr)==0 or arr==None:
            return -1
        
        left=0
        right=len(arr)-1
        minindex=0
        
        def minimum_element_index(left, right, arr):
            if len(arr)==0:
                return -1
            if len(arr)==1:
                return 0
            while left<= right:
                mid=left+(right-left)//2
                if mid> 0 and arr[mid]< arr[mid-1]:
                    return mid
                elif arr[mid]>= arr[left] and arr[mid]> arr[right]:
                    left=mid+1
                else:
                    right=mid-1
            return left
        
        minindex=minimum_element_index(left, right, arr)#RETURN MINIMUM ELEMENT's INDEX
        left=0
        right=len(arr)-1
        
        if target>= arr[minindex] and target<= arr[right]:
            left=minindex
        else:
            right=minindex
        
        while left<= right:  #NORMAL BINARY SEARCH
            mid=left+(right-left)//2
            if target == arr[mid]:
                return mid
            elif arr[mid]> target:
                right=mid-1
            else:
                left=mid+1
   
        return -1

#LEETCODE-->
'''
https://leetcode.com/problems/search-in-rotated-sorted-array/
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

'''<file_sep>class Solution:
    def findMin(self, arr: List[int]) -> int:
        if len(arr)==0:
            return -1
        if len(arr)==1:
            return arr[0]
        
        left=0
        right=len(arr)-1
        
        while(left<= right):
            mid= left+(right-left)//2
            
            if mid>0 and arr[mid]<arr[mid-1]:
                return arr[mid]
            
            elif arr[mid]>= arr[left] and arr[mid]> arr[right]:
                left= mid+1
                
            else:
                right=mid-1
                
        return arr[left]
<file_sep># -*- coding: utf-8 -*-
"""
Created on Tue Jun 16 15:17:26 2020

@author: MrMaak
"""


# The count-and-say sequence is the sequence of integers with the first five terms as following:

# 1.     1
# 2.     11
# 3.     21
# 4.     1211
# 5.     111221
# 1 is read off as "one 1" or 11.
# 11 is read off as "two 1s" or 21.
# 21 is read off as "one 2, then one 1" or 1211.

# Given an integer n where 1 ≤ n ≤ 30,
#  generate the nth term of the count-and-say sequence. 
#  You can do so recursively, in other words from the previous member
#  read off the digits, counting the number of digits in groups of
#  the same digit.

# Note: Each term of the sequence of integers will be represented as a 
# string.

 

# Example 1:

# Input: 1
# Output: "1"
# Explanation: This is the base case.
# Example 2:

# Input: 4
# Output: "1211"
# Explanation: For n = 3 the term was "21" in which 
# we have two groups "2" and "1", "2" can be read as "12" which means 
# frequency = 1 and value = 2, the same way "1" is read as "11"
# , so the answer is the concatenation of "12" and "11" which is "1211".


def counter(n):
    if n==1:
        return "1"
    prev=counter(n-1)
    res, count, curr = "", 1, prev[0]
    for i in range(1, len(prev)):
        if curr== prev[i]:
            count+=1
        else:
            res+=str(count)+str(curr)
            count, curr =1, prev[i]
    res+=str(count)+ str(curr)
    return res

print(counter(6))
<file_sep>def triplet(arr,n):
	ans=0
	for i in range(1, n-1):
		maxl=0
		maxr=0

		for j in range(0, i):
			if arr[i] > arr[j]:
				maxl=max(maxl, arr[j])

		for j in range(i+1, n):
			if arr[i] < arr[j]:
				maxr=max(maxr, arr[j])

		if maxl and maxr:
			ans= max(ans, maxl+arr[i]+maxr)
		
	return ans

arr=[2,5,3,1,4,9]
print(triplet(arr, len(arr)))

'''
 Instead of traversing through every triplets with three nested loops, we can traverse through two nested loops. While traversing through each number(assume as middle element(aj)), find maximum number(ai) smaller than aj preceding it and maximum number(ak) greater than aj beyond it. Now after that, update the maximum answer with calculated sum of ai + aj + ak
'''<file_sep>/*LARGE FACTORIALS
In mathematics, the factorial of integer n is written as n!. It is equal to the product of n and every integer preceding it. For example: 5! = 1 x 2 x 3 x 4 x 5 = 120
Your mission is simple: write a function that takes an integer n and returns the value of n!.
You are guaranteed an integer argument. For any values outside the non-negative range, return null, nil or None (return an empty string "" in C and C++). For non-negative numbers a full length number is expected for example, return 25! = "15511210043330985984000000" as a string.
For more on factorials, see http://en.wikipedia.org/wiki/Factorial
NOTES: 
The use of BigInteger or BigNumber functions has been disabled, this requires a complex solution
I have removed the use of require in the javascript language.
-------------------------
CODE#*/
import java.math.BigInteger;
public class Kata
{
  public static String Factorial(int n) {
  BigInteger fact = new BigInteger("1");
  for (int i = 2; i <= n; i++) 
    fact = fact.multiply(new BigInteger(i + ""));
  return fact.toString();
}}
<file_sep>def check(summ):
	for i in prime:
		if i==summ:
			return 1
	return 0

def g(stri, pos, summ, tight):
	if pos==len(stri):
		if check(summ) :
			return 1
		else:
			return 0

	elif dp[pos][summ][tight]!=-1:
		return dp[pos][summ][tight]

	elif tight==1:
		res=0
		for i in range(0,int(stri[pos])):
			if i==int(stri[pos]):
				res+=g(stri,pos+1,summ+i,1)
			else:
				res+=g(stri,pos+1,summ+i,0)
		dp[pos][summ][tight]=res
		return res

	else:
		res=0
		for i in range(0,9):
			res+=g(stri,pos+1,summ+i,0)
		dp[pos][summ][tight]=res
		return res

prime=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109]
l=10
r =19
l=l-1
a=str(l)
b=str(r)
dp=[[[-1 for k in range(2)] for j in range(80)]for i in range(10)]
ans1=g(b,0,0,1)
dp=[[[-1 for k in range(2)] for j in range(80)]for i in range(10)]
ans2=g(a,0,0,1)

print(ans1-ans2)<file_sep>def pig(word):
	f=word[0]
	if 'dog'=='adog eiou':
		return word+'ay'
	else:
		return word[1:]+'ay'+f
print(pig("hello"))<file_sep>def max_dot_product(a, b):
    res = 0
    while a:
        j=max(a)
        k=max(b)
        res+=j*k
        a.remove(j)
        b.remove(k)
    return res
print(max_dot_product([23],[39]))<file_sep>def coin(arr,s):
  n=len(arr)

  k=[[0 for i in range(s+1)] for j in range(n+1)]

  for i in range(1,s+1):
    k[0][i]=0
  for i in range(n+1):
    k[i][0]=1

  for i in range(1,n+1):
    for j in range(1,s+1):
      if arr[i-1]> j:
        k[i][j]=k[i-1][j]
      else:
        k[i][j]= k[i][j-arr[i-1]] + k[i-1][j]
  
  return k[n][s]

arr=[1,2,3]
s=5
if s<0:
  print("NOT POSSIBLE")
else:
  print("There are {} max ways to get sum= {} from coins={}".format(coin(arr,s),s,arr))<file_sep>def delete(k):
  
  if k==0:
    s.pop()
    return
  
  temp=s.pop()
  delete(k-1)
  s.append(temp)

s = [1,2,3,4,5] 
s1=s.copy()

k= len(s)//2-1 if len(s)%2==0 else len(s)//2 
delete(k)

print("The resultant stack after removing middle element from {} is {}".format(s1,s))<file_sep># -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 15:47:00 2020

@author: MrMaak
"""
# EQUAL SUBSET PARTION PROBLEM
#Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

# Note:

# Each of the array element will not exceed 100.
# The array size will not exceed 200.
 

# Example 1:

# Input: [1, 5, 11, 5]

# Output: true

# Explanation: The array can be partitioned as [1, 5, 5] and [11].
 

# Example 2:

# Input: [1, 2, 3, 5]

# Output: false

# Explanation: The array cannot be partitioned into equal sum subsets.


def recc(nums, s, n):
    if s==0:
        return True
    if n==0 and sum!=0:
        return False
    
    if t[n][s]!=- 1:
        return t[n][s]
    
    if nums[n-1]>s:
        t[n][s]= recc(nums, s, n-1)
        return t[n][s]
    else:
        t[n][s]= (recc(nums, s-nums[n-1], n-1) or recc(nums, s, n-1))
        return t[n][s]

def canPartition(nums) -> bool:
    s=sum(nums)
    if s%2!=0:
        return False
    else:
        s//=2
        n=len(nums)
        k=[[False for i in range(s+1)] for j in range(n+1)]
        for i in range(n+1):
            k[i][0]=True
        for i in range(1,s+1):
            k[0][i]= False
        for i in range(n+1):
            for j in range(s+1):
                if nums[i-1]> j:
                    k[i][j] = k[i-1][j]
                else:
                    k[i][j]= k[i-1][j-nums[i-1]] or k[i-1][j]        
        return k[n][s]
        
nums=[1,5,11,5]
s=sum(nums)
n=len(nums)
t=[[-1 for i in range(s+1)] for j in range(n+1)]
a1=recc(nums, s//2, n)
a=canPartition( nums)
print(a1)
<file_sep>def printpreorder(inorder, postorder, n): 
	if postorder[-1] in inorder: 
		root = inorder.index(postorder[-1])
	stack.append(postorder[-1])
		
	if root != 0: # left subtree exists 
		printpreorder(inorder[:root], 
					postorder[:root], 
					len(inorder[:root])) 
	
	if root != n - 1: # right subtree exists 
		printpreorder(inorder[root + 1:], 
					postorder[root: -1], 
					len(inorder[root + 1:])) 
		
# Driver Code 
postorder = [4, 12, 10, 18, 24, 22, 15, 31,44, 35, 66, 90, 70, 50, 25]
inorder = 	[4, 10, 12, 15, 18, 22, 24, 25,31, 35, 44, 50, 66, 70, 90]
n = len(inorder) 
stack=[]
printpreorder(inorder, postorder, n)
print ("Preorder traversal: {}".format(stack))
#25 15 10 4 12 22 18 24 50 35 31 44 70 66 90<file_sep># python3


def max_pairwise_product(numbers):
    n = len(numbers)
    maxxx=max(numbers[0],numbers[1])
    maxx=min(numbers[0],numbers[1])
    for i in range(2,n):
    	if numbers[i]>=maxxx:
    		maxx=maxxx
    		maxxx=numbers[i]
    	else :
    		if numbers[i]>=maxx:
    			maxx=numbers[i]
    		else:
    			pass
    max_product=maxx*maxxx

    return max_product


if __name__ == '__main__':
    input_n = int(input())
    input_numbers = [int(x) for x in input().split()]
    print(max_pairwise_product(input_numbers))
<file_sep># -*- coding: utf-8 -*-
"""
Created on Mon Jun 15 23:08:12 2020

@author: MrMaak
"""


# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""

#REMOVING DUPLICATE 1:
def removedup1():
    arr=[1,1,2]
    i=0
    for j in range(1, len(arr)):
        if arr[i]!= arr[j]:
            i+=1
            arr[i]=arr[j]
    print(i+1)



#REMOVING DUPLICATE 2:
# Given a sorted array nums, 
#remove the duplicates in-place such that duplicates 
#appeared at most twice and return the new length.

# Do not allocate extra space for another array, 
#you must do this by modifying the input array in-place
# with O(1) extra memory.

# Example 1:

# Given nums = [1,1,1,2,2,3],

# Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

# It doesn't matter what you leave beyond the returned length.
# Example 2:

# Given nums = [0,0,1,1,1,1,2,3,3],

# Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

#It doesn't matter what values are set beyond the returned length.
def removedup2():
    arr=[1,1,1,2,2,3]
    i=1
    for j in range(2, len(arr)):
        if arr[i-1]!=arr[j]:
            i+=1
            arr[i]=arr[j]
    print(i+1)
    
    
#CALLING FUNCTION
print(removedup1())
print(removedup2())
    <file_sep>stack=[]# storing index value
nums=[1,3,0,0,1,2,4]
stack.append(0)
out=[0 for i in range(len(nums))]

for i in range(len(nums)):  
	if len(stack)==0:
		stack.append(i)
		continue
	
	while len(stack)!=0 and nums[stack[-1]]< nums[i]:
		out[stack[-1]]=nums[i]
		stack.pop()
		
	stack.append(i)
	
for s in stack:
	out[s]=-1
	
print(out)<file_sep>def subset(i,o):
  if i=="":
    print(o)
    return
  
  o1=o
  o2=o
  o2=o2+i[0]
  i=i[1:]
  subset(i,o1)
  subset(i,o2)
  
i="abc"
o=""
subset(i,o)

'''
def subset(i,oi):
  if len(i)==0:
    print(oi)
    return
  
  o1=oi.copy()
  o2=oi.copy()
  o2.append(i[0])
  i=i[1:]
  subset(i,o1)
  subset(i,o2)
  
i=[1, 4, 9] 
oi=[]
out=[]
subset(i,oi)
'''<file_sep>def subArraySum(arr, sumi,n ):  
	for i in range(n): 
		curr_sum = arr[i]  
		j = i + 1
		while j <= n: 
			if curr_sum == sumi: 
				print ("Sum found between") 
				print("indexes % d and % d"%( i, j-1)) 
				return 1
			if curr_sum > sumi or j == n: 
				break
			curr_sum = curr_sum + arr[j] 
			j += 1
	print ("No subarray found") 
	return 0

arr=[1,2,3,7,5]
subArraySum(arr, 12, len(arr))<file_sep>def tower(n, s, d ,h):
  if n==1:
    print("Move disk 1 from {} to {}".format(s,d))
    return

  tower(n-1, s, h, d)
  print("Move disk {} from {} to {}".format(n,s,d))
  tower(n-1, h, d, s)

n=3
tower(n,'s','d','h')<file_sep># -*- coding: utf-8 -*-
"""
Created on Wed Jun 24 00:20:10 2020

@author: MrMaak
"""

s=5
arr=[1,2,3,5,10]
n=len(arr)

t=[[0 for j in range(s+1)] for i in range(n+1)]


for i in range(1, s+1):
    t[0][i]= 0
for i in range(n+1):
    t[i][0]= 1


for i in range(n+1):
    for j in range(s+1):
        
        if arr[i-1]> j:
            t[i][j]= t[i-1][j]
        else:
            t[i][j]= t[i-1][j-arr[i-1]] + t[i-1][j]
   
         
print(t[n][s])<file_sep>def rod(wt, n):
  for i in range(n+1):
    for j in range(wt+1):
      if w[i-1]>j:
        t[i][j]=t[i-1][j]
      else:
        t[i][j]=max((value[i-1]+t[i][j-w[i-1]]), (t[i-1][j]))
  return t[n][wt]

def submem(n,wt):
  #BASE CASE
  if n==0 or wt==0:
    return 0

  if k[n][wt] != -1:
    return k[n][wt]
  
  #CHOICE DIAGRAM
  if w[n-1] > wt:
    k[n][wt]= submem(n-1,wt)
    return k[n][wt]
  else:
    k[n][wt]= max((value[n-1]+submem( n, wt-w[n-1])) ,(submem(n-1,wt)))
    return k[n][wt]

value=[2,5,7,8]
w=[1,2,3,4]
wt=5
n=len(value)
k=[[-1 for j in range(wt+1)] for i in range(n+1)]
t=[[0 for j in range(wt+1)] for i in range(n+1)]
print(rod(wt,n))
print(submem(n,wt))


'''
|-------->length
|
|
|
^'
[size of array or the elements present in array]
FILLED WITH 0
'''<file_sep>startindex, bufferindex= 0, 0
arr=[1,2,3,4,5]
r=2
out=[0]*r

def combination(startindex, arr, bufferindex, out):
  #BaseCase
  if bufferindex==r:
    print(out)
    return

  for i in range(startindex, len(arr)): #BACKTRACKING
    out[bufferindex]=arr[i]
    combination(i+1, arr, bufferindex+1, out)

combination(startindex, arr, bufferindex,out)

'''
from itertools import combinations
lst = [1,2,3,4,5]
lengthOfStrings = 3
for i in combinations(lst, lengthOfStrings):
  print(i)
'''<file_sep>def per(i,o):
  if i=="":
    print(o)
    return
  
  o1=o
  o2=o
  o1=o1+i[0].lower()
  o2=o2+i[0].upper()
  i=i[1:]
  per(i,o1)
  per(i,o2)

per("ab","")

'''
OUTPUT:
ab
aB
Ab
AB
'''<file_sep>def subset(i,oi):
	if len(i)==0:
		if len(oi)==3:
			out.append(oi)
		return

	o1=oi.copy()
	o2=oi.copy()
	o2.append(i[0])
	i=i[1:]
	subset(i,o1)
	subset(i,o2)

i=[1, 4, 45, 6, 10, 8] 
oi=[]
out=[]
subset(i,oi)
sumi=22
outi=[]
for k in out:
	if sum(k)==sumi:
		outi.append(k)
print(outi)<file_sep>stack=[]
k=4
out=[]
arr=[10, 9, 8, 7, 4, 70, 60, 50]
for i in arr:
	if len(stack)==0:
		stack.append(i)
		print(stack)
		continue
	elif len(stack)>0 and stack[-1]>i:
		stack.append(i)
		print(stack)
	elif len(stack)>0 and stack[-1]<i:
		stack=[i]+stack
		print(stack)
	if len(stack)>k:
		temp=min(stack)
		stack.remove(temp)
		out.append(temp)
#kth largest and min heap
print(stack)
print(out)<file_sep>def desired(arr,c):
	sumi=sum(arr)
	c=0
	while sumi!=0:
		if alleven(arr):
			c+=divide(arr)
		else:
			c+=substract(arr)

		sumi=sum(arr)
	return c

def alleven(arr):
	all=False
	for i in range(0,len(arr)):
		if arr[i]%2==0:
			all=True
		else:
			all=False
			break
	return all

def divide(arr):
	for i in range(0, len(arr)):
		arr[i]//=2
	return 1
	
def substract(arr):
	t=0
	for i in range(0,len(arr)):
		if arr[i]%2==0:
			pass
		else:
			arr[i]-=1
			t+=1
	return t
			
c=0
arr=[2,1]
print(desired(arr,c))<file_sep>def areBookingsPossible(arrival, departure, n, k): 

	ans = [] 
	# Create a common vector both arrivals 
	# and departures. 
	for i in range(0, n): 
		ans.append((arrival[i], 1)) 
		ans.append((departure[i], 0)) 

	# Sort the vector 
	ans.sort() 
	#[(1, 1), (2, 0), (3, 1), (5, 1), (6, 0), (8, 0)]

	curr_active, max_active = 0, 0
	for i in range(0, len(ans)): 
		# If new arrival, increment current 
		# guests count and update max active 
		# guests so far 
		if ans[i][1] == 1:
			curr_active += 1
			max_active = max(max_active, 
							curr_active) 

		# if a guest departs, decrement 
		# current guests count. 
		else: 
			curr_active -= 1

	# If max active guests at any instant 
	# were more than the available rooms, 
	# return false. Else return true. 
	return k >= max_active 

arrival = [1, 3, 5] 
departure = [2, 6, 8] 
n = len(arrival) 
k=3
if areBookingsPossible(arrival, 
					departure, n, k): 
	print("Yes") 
else: 
	print("No") <file_sep>import random
arr=[5,7,85,4,6,1,2,9,3,4]
def quicksort(arr,l,r):
	if l >= r:
		return
	k = random.randint(l, r)
	arr[l], arr[k] = arr[k], arr[l]
	j, m = partition(arr, l, r)
	quicksort(arr,l,j-m)
	quicksort(arr,j+1,r)
def partition(arr,l,r):
	pivot = arr[l]
	j,k,m=l,1,0
	for i in range(l + 1, r + 1):
		if arr[i] < pivot:
			j += 1
			arr[i], arr[j] = arr[j], arr[i]
		elif arr[i] == pivot:
			j += 1
			arr[i], arr[j] = arr[j], arr[i]
			arr[j], arr[l + k] = arr[l + k], arr[j]
			k += 1
	while m < k:
		arr[l + m], arr[j - m] = arr[j - m], arr[l + m]
		m += 1
	return j, m
quicksort(arr,0,len(arr)-1)
print(arr)<file_sep>arr=[1,2,0,0,1,2,2]
pivot=1
low=0
high=len(arr)-1
i=0
while i<=high:
	if arr[i]<pivot:
		arr[i],arr[low]=arr[low],arr[i]
		low+=1
		i+=1
	elif arr[i]>pivot:
		arr[i],arr[high]=arr[high],arr[i]
		high-=1
	else:
		i+=1
print(arr)<file_sep>def wave(arr):
	arr.sort()

	for i in range(0,len(arr)-2,2):
		arr[i], arr[i+1]= arr[i+1], arr[i]

	return arr

arr=[3, 6, 5, 10, 7, 20]
print(wave(arr))


'''
Sort an array in wave form

Given an unsorted array of integers, sort the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..
Input:  arr[] = {3, 6, 5, 10, 7, 20}
Output: arr[] = {6, 3, 10, 5, 20, 7} OR any other array that is in wave form
'''<file_sep>def sumpossible(b,n, num):
    t=[[False for i in range(num+1)] for j in range((n+1))]
    
    for i in range (n+1):
        t[i][0]=True
    for i in range(1, num+1):
        t[0][i]=False
    for i in range(1,n+1):
        for j in range(1, num+1):
            if j< t[i-1]:
                t[i][j]=t[i-1][j]
            if j>=t[i-1]:
                t[i][j]=(t[i-1][j] or t[i-1][j-t[i-1]])

    return t[n][num]

#nu=int(input())
#arr=list(map(int, input().split()))
#a=list(map(int,input().split()))
#n2=int(input())
nu=2
arr=[3,2]
n2=4
z=[3,8,11,13]
print(n2)
#z=list(map(int,input().split()))

b=[]
for i in range(nu):
    sumi=0
    for j in range(i+1):
        sumi=sumi+(arr[j]* 2**j)
		b.append(sumi)
print(b)

out=[]
'''
for i in z:
    if sumpossible(b,len(b),i):
        out.append("YES")
    else:
        out.append("NO")
st=" ".join(out)
print("{}".format(st))
'''<file_sep>def first(arr, target):
  res=-1
  low,high=0,len(arr)-1
  while low<=high:
    mid=low+(high-low)//2
    if arr[mid]>target:
      high=mid-1
    elif arr[mid]<target:
      low=mid+1
    else:
      res=mid
      high=mid-1
  return res

def last(arr,target):
  res=-1
  low,high=0,len(arr)-1
  while low<=high:
    mid=low+(high-low)//2
    if arr[mid]>target:
      high=mid-1
    elif arr[mid]<target:
      low=mid+1
    else:
      res=mid
      low=mid+1
  return res

arr=[1,2,2,2,3,4]
res=-1
target=2
print(first(arr,target))
print(last(arr,target))<file_sep>from sys import maxsize

def lcsum(arr):
	maxsumsofar= -maxsize-1
	maxendinghere=0

	for i in range(len(arr)):
		maxendinghere+=arr[i]

		if maxendinghere > maxsumsofar:
			maxsumsofar=maxendinghere

		if maxendinghere < 0:
			maxendinghere=0

	return maxsumsofar

def printlcsum(arr):
	maxsumsofar= -maxsize-1
	maxendinghere=0
	start,end=0,0
	s=0
	for i in range(len(arr)):
		maxendinghere+=arr[i]
		if maxendinghere > maxsumsofar:
			maxsumsofar=maxendinghere
			start=s
			end=i
		if maxendinghere < 0:
			maxendinghere=0
			s=i+1
	return maxsumsofar, start, end


arr= [-2, -3, 4, -1, -2, 1, 5, -3]
#[-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7] 
print(lcsum(arr))
print(printlcsum(arr))


'''Largest Sum Contiguous Subarray

Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.
'''<file_sep># Python program to print postorder 
# traversal from preorder and 
# inorder traversals 
def printpostorder(inorder, preorder, n): 
	if preorder[0] in inorder: 
		root = inorder.index(preorder[0]) 
		
	if root != 0: # left subtree exists 
		printpostorder(inorder[:root], 
					preorder[1:root + 1], 
					len(inorder[:root])) 
	
	if root != n - 1: # right subtree exists 
		printpostorder(inorder[root + 1:], 
					preorder[root + 1:], 
					len(inorder[root + 1:])) 
	
	print(preorder[0])
		
# Driver Code 
inorder = [4, 2, 5, 1, 3, 6]; 
preorder = [1, 2, 4, 5, 3, 6]; 
n = len(inorder) 
print ("Postorder traversal ")
printpostorder(inorder, preorder, n) <file_sep>import heapq
def findsthLargest(nums, k):
	heap = []
	heapq.heapify(heap)
	for i in range(len(nums)):
		heapq.heappush(heap,nums[i])

	res=[]
	res.append([y for y in heapq.nsmallest(k, heap)])
	print(res)
	return res[-1][-1]

print(findsthLargest([5,2,3,1,9],4))<file_sep>def triplet(arr,n):
	total=0
	for i in range(1, n-1):
		lc=0
		rc=0
		for j in range(0,i):
			if arr[i]> arr[j]:
				lc+=1

		for j in range(i+1,n):
			if arr[i]< arr[j]:
				rc+=1

		total+=lc*rc
	
	return total

arr=[1,3,2]
print(triplet(arr, len(arr)))<file_sep>def change(m):
	deno=[1,5,10]
	ans=[]
	i=len(deno)-1
	while(i >= 0):
		while(m>=deno[i]):
			m-=deno[i]
			ans.append(deno[i])
		i-=1
	print(ans)
	return len(ans)
print(change(23))
<file_sep>import heapq
def findKthLargest(nums, k):
	heap = []
	heapq.heapify(heap)
	for i in range(len(nums)):
		heapq.heappush(heap,nums[i])

	res=[]
	res.append([y for y in heapq.nlargest(k, heap)])
	print(res)
	return res[-1][-1]

print(findKthLargest([3,1,2,4],2))

#minheap