boolean isUniqueChars(String str){
    if(str.length()>128) return false;
    
    boolean[] char_set = new boolean[128];
    
    for(int i =0;i<str.length();  ++i){
        int val = str.charAt(i);
        if(char_set[val]){ // Already found this char in string
            return false;
        }
        char_set[val] = true;
    }
    return true;
}

boolean isUniqueChars(String str){
    int checker = 0;
    for(int i = 0;i<str.length() ; i++){
        int val = str.charAt(i) - 'a';
        if((checker & (1<<val) )>0) return false;
        checker |= (1<<val);
    }
    return true;
}

String sort(Strings s){
    char[] content = s.toCharArray();
    java.util.Array.sort(content);
    return new String(content);
}
boolean permutation(String s, String t){
    if(s.legth()!=t.length()) return false;
    return sort(s).quals(sort(t));
}

boolean permutation(String s, String t){
    if(s.length() != t.length()){
        return false;
    }
    int [] letters = new int[128];
    
    char[] s_array = s.toCharArray();
    for(char c:s_array){
        letters[c]++;
    }
    
    for(int i=0;i<t.length();++i){
        int c = (int)t.charAt(i);
        letters[c]--;
        if(letters[c]<0) return false;
    }
    return true;
    
}

EXAMPLE
Input: "Mr John Smith ", 13 
Output: "Mr%20John%20Smith"


void replaceSpaces(char[] str, int trueLength){
    int splaceCount = 0, index , i = 0;
    for(i = 0;i<trueLength ; ++i){
        if(str[i] == ' ') splaceCount++;
    }
    
    
    index = trueLength + splaceCount*2;
    if(trueLength < str.length) str[trueLength] = '\0'; //End array
    for(i = trueLength-1;i>=0;i--){
        if(str[i]==' '){
            str[index-1] = '0';
            str[index-2] = '2';
            str[index-3] = '%';
            index = index - 3;            
        }
        else{
            str[index-1] = sre[i];
            index--;
        }
    }
}

EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat'; "atc o eta·; etc.)

EXAMPLE
pale, ple true 
pales, pale -> true 
pale, bale -> true 
pale, bae -> false

enum State { Unvisited, Visited, Visiting; }
boolean search(Graph g, Node start, Node end) {
    if (start == end) return true;
    // operates as Queue
    LinkedList<Node> q = new Linkedlist<Node>();
    for (Node u : g.getNodes()) {
        u.state = State.Unvisited;
    }
    start.state =  State.Visiting;
    q.add(start);
    Node u;
    while (!q.isEmpty()) {
        u = q.removeFirst(); II i.e., dequeue() 
        if (u != null) {
            for (Node v : u.getAdjacent()) {
                if (v.state == State.Unvisited) {
                    if (v == end) {
                        return true;
                    } 
                    else {
                        v.state = State.Visiting;
                        q.add(v);
                    }
                }
            }
            u.stateState.Visited;
        }
    }
    return false;
}

int index = 0;
void copyBST(TreeNode root, int[] array) {
    if(root==null) return ;
    copyBST(root.left, array);
    array[index] = root.data;
    index++;
    copyBST(root.right, array);

}
boolean checkBST(TreeNode root) {
    int [] array = new ont[root.size];
    
    copyBST(root, array);
    
    
    for(int i=1;i<array.length;++i){
        if(array[i-1]>array[i] ) return false;
    }
    return true;
}

Integer last_printed = null;

boolean checkBST(TreeNode n) {
    if(n==null) return true;
    
    //  Check  recurse left
    if (!checkBST(n.left)) return false;
    
    // Check current
    if (last_printed != null && n.data =< last_printed){
        return false;
    }
    
    last_printed = n.data;
    
    //  Check recurse right
    if (!checkBST(n.right)) return false;
    
    return true;
    
    
    
}

// O(n) time and O(logN) space
boolean checkBST(TreeNode n) {

    return checkBST(n, null, null);
}

boolean checkBST(TreeNode n, Integer min, Intefet max){
    if(n==null) return true;
    
    
    // check this level 
    if( (min!=null && n.data<=min) || (max!=null && n.data>max) ){
        return false;
    }
    
    // check left child and right child
    if(!checkBST(n.left, min, n.data) || !checkBST(n.right, n.data, max)){
        return false;
    }
    
    
    
    return true;
}

TreeNode inorderSucc(TreeNode n) {
    if(n==null) return null;
    if(n.right!=null){
        return leftMostChild(n.right);
    }
    else{
        TreeNode q = n;
        TreeNode x = q.parent;
        while( x!=null && x.left=q){
            q = x;
            x = x.parent;
        }
        return x;
    }    
    

}


TreeNode leftMostChild(TreeNode n){
    if(n==null) return null;
    
    while(n.left!=null){
        n=n.left;
    }
    return n;
}

// O(d) time, d is the depth of the deeper node.
TreeNode * commonAncestor(TreeNode p, TreeNode q){
    int delta = depth(p)- depth(q);
    TreeNode first = delta>0?q:p; // get shallower node
    TreeNode second = delta>0?p:q; // get deeper node

    second = goUpBy(second, Math.abs(delta)); 
    /* Find where paths intersect. */
    while(first !=second && first!=null && second !=null){
        first = first.parent;
        second = second.parent;
    }
    return first==null || second == null ? null:first;
    
}
TreeNdoe goUpBy(TreeNode node , int delta){
    while(delta >0 && node!=null){
        node = node.parent;
        delta--;
    }
    return node;
}
int depth(TreeNode node){
    int depth = 0;
    while(node !=null){
        node = node.parent;
        depth++;
    }
    return depth;
}

// O(t) time , t is the size of the subtree for the first common ancestor

TreeNode commonAncestor(TreeNode root, TreeNOde p, TreeNode q){
    if(!covers(root, p) || !covers(root, q)){
        return null;
    }
    else if( covers(p,q)) return p;
    else if (covers(q,p)) return q;
    TreeNode sibling = getSibling(p);
    TreeNode parent = p.parent;
    while(!covers(sibling, q)){
        sibling = getSibling(parent);
        parent = parent.parent;
    }
    return parent;
}
bool covers(TreeNode root, TreeNode p){
    if(root == null) return false;
    if( root==p ) return true;
    return covers(root.left, p) || covers(root.right, p);
}
TreeNode getSibling(TreeNode node){
    if(node==null || node.parent = null ) return null;
    TreeNode parent = node.parent;
    return parent.left ==node ?parent.right :parent.left;
}

TreeNode commonAncestor(TreeNode root, TreeNOde p, TreeNode q){
    if(!covers(root, p) || !covers(root, q)){
        return null;
    }

    return ancestorHelper(root, p, q);

}

TreeNode ancestorHelper(TreeNode root, TreeNOde p, TreeNode q){
    if(root ==null || root==p || root==q){
        return root;
    }

    boolean pIsOnLeft = covers(root.left, p);
    boolean qIsOnLeft = covers(root.left, q);
    if(pIsOnLeft !=qIsOnLeft) return root;

    TreeNode childSide = pIsOnLeft?root.left:root.right;
    return ancestorHelper(childSide, p, q);

    
}
bool covers(TreeNode root, TreeNode p){
    if(root == null) return false;
    if( root==p ) return true;
    return covers(root.left, p) || covers(root.right, p);
}

class Result{
    public TreeNode node;
    public boolean isAncestor;
    public Result(TreeNode n , boolean isAnc){
        node = n;
        isAncestor =isAnc;
    }
}
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
        Result r = commonAncestorHelper(root,p,q);
        if(r.isAncestor){
            return r.ndoe;
        }
        return null;
    }

}

Result commonAncestorHelper(TreeNode root, TreeNode p, TreeNode q){
    if(root==null) return new Result(null, false);
    if(root==p || root==q){
        return new Result(root, true);
    }

    Result rx = commonAncestorHelper(root.left, p, q);
    if(ry.isAncestor){
        return ry;
    }

    if(rx.node !=null && ry.node !=null){
        return new Result(root, true);
    }
    else if(root ==p || root==q){
        boolean isAncestor = rx.node !=null || ry.node==null;
        return new Rsult(root, isAncestor);
    }
    else{
        return new Result(rx.node !=null?rx.node:ry.node, false);
    }
}

class TreeNode{
    private int data;
    public TreeNode left;
    public TreeNode right;
    private int size = 0;
    public TreeNode(int d){
        data = d;
        size = 1;
    }
    public TreeNode getRandomNote(){
        int leftSize = left ==null?0:left.size();
        Random random = new Random();
        int index = random.nextInt(size);
        if(index<leftSize){
            return left.getRandomNode();
           
        }
        else if (index==leftSize){
            return this;
        }
        else  return right.getRandomNode();
    }
    publoc void insertInOrder(int d){
        if(d<=data){
            if(left ==null){
                left = new TreeNode(d);
                
            }
            else{
                left.insertInOrder(d);
            }
        }
        else{
            if(right==null)
            {
                right = new TreeNode(d);
            }
            else{
                right.insertInOrder(d);
            }
        }
        size++;

    }
    public int size(){return size;}
    public int data() {return data;

    public TreeNode find(int d){
        if(d==data){
            return this;
        }
        else if(d<= data){
            return left != null? left.find(d): null;
        }
        else if(d>data){
            return right != null?right.find(d):null;
        }
        return null;
    }
}

class Tree{
    TreeNode root= nullptr;
    public int size() {return root ==null ?0 : root.size();}
    public TreeNode getRandomNode(){
        if(root==null) return null;

        Random random = new Random();
        int i = random.nextInt(size());
        return root.getIthNode(i);
    }
    public void insertInOrder(int value){
        if(root=null){
            root = new TreeNode(value);
        }
        else{
            root.insertInOrder(value);
        }
    }
}
class TreeNode{
    
    public TreeNode getIthNode(int i){
        int leftSize = left ==null ?0:left.size();
        if(i<leftSize){
            return left.getIthNode(i);
        }
        else if(i==leftSize){
            return this;
        }
        else{
            return right.getIthNode(i - (leftSize+1));
        }
    }
    public void insertInOrder(int d){
        if(d<=data){
            if(left ==null){
                left = new TreeNode(d);
                
            }
            else{
                left.insertInOrder(d);
            }
        }
        else{
            if(right==null)
            {
                right = new TreeNode(d);
            }
            else{
                right.insertInOrder(d);
            }
        }
        size++;
    }
    public int size(){return size;}
    public TreeNode find(int d){
        if(d==data){
            return this;
        }
        else if(d<= data){
            return left != null? left.find(d): null;
        }
        else if(d>data){
            return right != null?right.find(d):null;
        }
        return null;

    }
}

int countPathWithSum(TreeNode root, int targetSum){
        return countPathWitheSum(root, targetSum, 0, new HashMap<Integer, Integer>());
}
int countPathWitheSum(TreeNode root, int targetSum, int runningSum, HashMap<Integer, Integer> pathCount){
    if(node==null) return 0; // Base case
    /* Count paths with sum ending at the the current node */
    runningSum += node.data;
    int sum = runningSum -targetSum;
    int totalPaths = pathCount.getOrDefault(sum , 0);

    /*  If runningSum eaquls targetSum , then one additionl path starts at root. Add in this path */
    if(runningSum == targetSum) totalPaths++;

    /*  Increment pathCount, recurse, then decrement pathCount. */
    incrementHashTable(pathCount, runningSum, 1);
    totalPaths+= countPathWitheSum(root.left, targetSum, runningSum, pathCount);
    totalPaths+= countPathWitheSum(root.right, targetSum, runningSum, pathCount);
    incrementHashTable(pathCount, runningSum, -1);
    return totalPaths;
}

void incrementHashTable(HashMap<Integer, Integer> hashTable, int key, int delta){
        int newCount = hashTable.getOrDefault(key,0) + delta;
        if(newCount==0) hashTable.reome(key);
        else hashTable.put(key, newCount);
}
    

int updateBits(int n, int m, int i , int ,j){
    // EXAMPLE
    //  input: N = 10000000000, M = 10011 , i=2 j= 6
    // output: N = 10001001100
    // 
    int allOnes = ~0; // will equal sequence of all 1s.

    // 1s before position j, then 0s. left = 11110000000
    int left = allOnes << (j+1);

    // 1's after position i . right = 00000000100 - 1 = 00000000011
    int right = ((1<<i)-1); 
    
    // All 1s, excepts for 0s between i and j , mask = 11110000011
    int mask = left | right;

    int n_cleared = n & mask; // clear bits j throught i/ n_cleared = 10000000000
    int m_shifted = m<<i;  // MOve m into correct position. , m_shifted = 00001001100


    //  10000000000 | 00001001100 = 10001001100
    return n_cleared | m_shifted; // OR them, and we-'re down.
}

String printBinary(double num){
    if(num>=1 || num<=0) return "ERROR";

    StringBuilder binary = new StringBuilder();
    binary.append(".");
    while(num>0){
        if(binary.length() >=32){
            return "ERROR";
        }

        double r = num*2;
        if(r>=1){
            binary.append(1);
            num = r-1;
        }
        else{
            binary.append(0);
            num = r;
        }
    }
    return binary.toString();
}

String printBinary(double num){
    if(num>=1 || num<=0) return "ERROR";

    StringBuilder binary = new StringBuilder();
    double frac = 0.5;
    binary.append(".");
    while(num>0){
        if(binary.length() > 32){
            return "ERROR";
        }
        
        if(num>=frac){
            binary.append(1);
            num -= frac;
        }
        else{
            binary.append(0)
        }
        frac /=2;
    }
    return binary.toString();
}

// brute force
// EXAMPLE 
// input : 1175 (or: 11011101111) seq =  [0,4,1,3,1,2,21] reading bfrom right to left
// output 8
// O(b) time and O(b) space , where b in the length of the sequence.
int longestSequence(int n){
    if(n==-1) return Integer.BYTES*8;
    ArrayList<Integer> sequences = getAlternatingSequeces(n);
    return findLongestSequence(sequences);
}
/* Return a list of the sizes of the sequences. The sequence starts off with the
 number of 0s (which might be 0) and then alternates with the counts of each value
 */
ArrayList<Integer> getAlternatingSequeces(int n){
    ArrayList<Integer> sequences = new ArrayList<Integer>();

    int searchingFor = 0;
    int counter = 0;

    for(int i=0;i<Integer.BYTES*8 ;++i){
        if((n&1)!=searchingFor){
            sequences.add(counter);
            searchingFor = n&1;
            counter = 0;
        }
        counter++;
        n >>>=1;
    }
    sequences.add(counter);
    return sequences; //seq =  [0,4,1,3,1,2,21] 
}
/* Given the lengths of alternating sequences of 0s and ls, find the longest one
 we can build. */
int findLongestSequence(ArrayList<Integer> seq){
    int maxSeq = 1;
    for(int i=0;i<seq.size();i+=2){
        int zerosSeq = seq.get(i);
        int onesSeqRight = i-1 >=0 ? seq.get(i-1):0;
        int onesSeqLeft = i+1 <seq.size() ? seq.get(i+1) : 0 ;

        int thisSeq =0;
        if(zerosSeq == 1){  // can merge
            thisSeq = onesSeqLeft +1 + onesSeqRight;
        }
        if(zerosSeq>1){ // just add a zero to either side
            thisSeq = 1+ Math.max(onesSeqRight, onesSeqLeft);
        }
        else if(zerosSeq==0){ // No zero, but take either size
            thisSeq = Math.max(onesSeqRight, onesSeqLeft);
        }
        maxSeq = Math.max(thisSeq, maxSeq);
    }
    return maxSeq;
}

// O(b) time  but O(1) space
// When we see a zero, update previous Length:
// If the next bit is a 1, previous Length should be set to current Length.
// If the next bit is a 0, then we can't merge these sequences together. So, set previous Length to 0.

int flipBit(int a){
    /* If all 1s , this is already the longest sequence */
    if(~a==0) return Integer.BYTES*8;

    int currentLength =  0;
    int previousLength = 0;
    int maxLength = 1 ;

    while(a!=0){
        if((a&1) == 1){
            currentLength++;
        }
        else if((a&1)==0){
            previousLength = (a&2)==0?0:currentLength;
            currentLength  = 0;
        }

        maxLength = Math.max(previousLength + currentLength +1 , maxLength);
        a >>>=1;
    }
    return  maxLength;
}

// Bit Manipulation for Get Next Number
// EXAMPLE 13948 = 1101101111100
// step 1 Flip rightmost non-trailing zero => 11011011111100
// step 2 Clear bits to the right of p from befor, c0 = 2, c1 = 5, p=7 => 11011010000000
// a = 1<<p;
// b=a-1;
// mask = ~b;
// n=n&mask;
// equal to 
// n &= ~((1<<p)-1)
// step 3 Add in c1-1 ones => 11011010001111 
// a = 1<< (c1-1);
// b= a-1;
// n = n| b;
// equal to
// n |= (1<<(c1-1)) -1;

int getNext(int n){
    /* compute c0 and c1 */
    int c = n;
    int c0 = 0;
    int c1 = 0;

    while( ((c&1)==0) && (c!=0) ){
        c0++;
        c >>= 1;
    }
    while( (c&1) ==1){
        c1++;
        c >>= 1 ;
    }


    /* Error: if n == 11..1100...00, then there is no bigger number with the same number of 1s*/
    if(c0+c1 ==31 || c0+c1 ==0){
        return -1;
    }
    int p = c0+c1; //position of rightmost non-trailing zeros

    n |= (1<<p); //Flip rightmost non-trailing zeros
    n &= ~((1<<p)-1 ) ; // Clear all bits to the right of p
    n |= (1<< (c1-1))-1 ; // Insert (c1-1) ones on the right

    return n;
}


// Bit Manipulation for Get Previous Number
// steps 1 initialize number p = 7 , c1 =2, c0 = 5
// 10011110000011
// steps 2 & 3 clear bits 0 through p
// 10011100000000
// int a= ~0;
// int b = a<<(p+1);
// n &=b;
// steps 4 Insert c1+1 ones immediately to the right of position p.
// int a = 1<< (c1+1);
// int b = a-1;
// int c = b<<(c0-1);
// n|=c;
// 10011101110000
int getPrec(int n){
    int temp = n;
    int c0 = 0; // the size of block of zeros immediately to the left of the trailing ones
    int c1 = 0;  // c1 is the number of trailing ones
    while( ( temp&1)==1){
        c1++;
        temp>>=1;
    }

    if(temp==0)return -1;

    while( ((temp&1)==0 ) && (temp!=0)){
        c0++;
        temp>>=1;
    }
    
    
    

    int p = c0+c1;
    n &= ((~0) << (p+1)); // clears from bits p onwards

    int mask = (1<<(c1+1))-1;  //Sequence of (c1+1) ones

    n|= mask <<(c0-1);

    return n
}

// Arithmetic Approach for Get Next Number
// c0 is the number of trailing zeros, c1 is the size of the one block immediately followind, and  p=c0+c1,
//  we can word our solution from eariler as follows
// step 1 set the Pth bit to 1
// step 2 set all bits following p to 0
// step 3 set bits 0 through c1-2 to 1. This will be c1-1 total bits
// n+= 2^c0 -1 
// 
int getNextArith(int n){
    int c = n;
    int c0 = 0;
    int c1 = 0;

    while( ((c&1)==0) && (c!=0) ){
        c0++;
        c >>= 1;
    }
    while( (c&1) ==1){
        c1++;
        c >>= 1 ;
    }

    return n + (1 << c0) + (1 << (c1 - 1)) - 1;
}


// Arithmetic Approach for Get Previous Number
//  c1 is the number of trailing ones , c0 is the size of the zero block immediately following, 
// and p = c0+c1
// step 1 set the Pth bit to 1
// step 2 set all bits following p to 0
// step 3 set bits 0 through c1-2 to 1. This will be c1-1 total bits


int getPrevArith(int n){
    int temp = n;
    int c0 = 0; // the size of block of zeros immediately to the left of the trailing ones
    int c1 = 0;  // c1 is the number of trailing ones
    while( ( temp&1)==1){
        c1++;
        temp>>=1;
    }

    if(temp==0)return -1;

    while( ((temp&1)==0 ) && (temp!=0)){
        c0++;
        temp>>=1;
    }

    return n - (1 << c1) - (1 << (c0 - 1)) + 1;
    
    
}

int bitSwapRequired(int a, int b){
    int count = 0;
    for(int c = a^b ; c!=0 ; c =c >>1){
        count += (c&1);
    }
    return count;
}


// c = c & (c - 1) will clear the least significant bit in c


int bitSwapRequired(int a, int b){
    int count = 0;
    for(int c = a^b ; c!=0 ; c  = c &(c-1)){
        count ++;
    }
    return count;
}

0xa =  1010 , 0x5 = 0101

int swapOddEvenBits(int x){
    return ( ((x& 0xaaaaaaaa)>>>1 ) | ((x& 0x55555555)<<1) );
}

void drawLine(byte[] screen , int width, int x1, int x2, int y){
    int start_offset = x1%8;
    int first_full_byte = x1 / 8;

    if(start_offset !=0){
        first_full_byte++;
    }
    int end_offset = x2%8;
    int last_full_byte = x2/8;
    if(end_offsetet!=7){
        last_full_byte--;
    }

    // set full bytes
    for(int b = first_full_byte ; b<=last_full_byte; ++b){
        screen[(width/8)*y + b] = (byte) 0xFF;
    }

    // create masks for start and end of line
    byte start_mask = (byte)(0xFF >> start_offset);
    byte end_mask = (byte) ~(0xFF >> (end_offset + 1));

    // set start and end of lines
    if( (x1/8) == (x1/8)){ // xl and x2 are in the same byte
        byte mask= (byte) (start_mask & end_mask);
        screen[(width/ 8) * y + (xl / 8)] I= mask;
    }
    else{
        if (start_offset != 0) {
            int byte_number =(width/ 8) * y + first_full_byte - 1; 
            screen[byte_number] I= start_mask;
        }
        if(end_offset !=7){
            int byte_number =(width/ 8) * y + last_full_byte + 1;
            screen[byte_number] I= end_mask;
        }
    }
}

// brute force 
int magicSlow(int []array){
    for(int i=0;i<array.legth ; i++){
        if(array[i]==i){
            return i;
        }
    }
    return -1;
}

// assume elements are distinct 
int magicFast(int []array){
    return magicFast(array, 0 ,array.length-1);   
}
int magicFast(int []array , int start, int end){
    if(end<start) return -1;
    while(start<=end){
        int mid = start + (end-start)/2;
        if(array[mid]==mid) return mid;
        else if(array[min]>mid ) end = mid-1;
        else start = mid+1;
    }
}

// assume elements are not  distinct 
int magicFast(int []array){
    return magicFast(array, 0 ,array.length-1);   
}
int magicFast(int []array , int start, int end){
    if(end<start) return -1;

    int midIndex = start + (end-start)/2;
    int midValue = array[midindex];
    if (midValue ==midIndex) {
        return midIndex;
    }

    /* Search Left */
    int leftindex = Math.min(midindex - 1, midValue);
    int left =magicFast(array, start, leftindex);
    if(left>0) return left;

    /* Search Right */
    int rightindex = Math.max(midindex + 1, midValue);
    int right = magicFast(array, rightlndex, end);
    return right;

}

int minProduct(int a, int b){
    int bigger = a<b?b:a;
    int smaller = a<b?a:b;
    return minProductHelper(smaller, bigger);
}

int minProductHelper(int smaller, int bigger){
    if(smaller==0) return 0;
    else if(smaller ==1) return bigger;

    int s = smaller >>1 
    int side1 = minProduct(s, bigger);
    int side2 = side1;
    if(smaller %2==1) side2 = minProductHelper(smaller-s , bigger);
    return side1+side2;
}

int minProduct(int a, int b, int []memo){
    int bigger = a<b?b:a;
    int smaller = a<b?a:b;
    int memo[] = new int[smaller +1 ];
    return minProductHelper(smaller, bigger, memo);
}

int minProductHelper(int smaller, int bigger, int []memo){
    if(smaller==0) return 0;
    else if(smaller ==1) return bigger;
    else if(memo[smaller]>0) return memo[smaller];

    int s = smaller >>1 
    int side1 = minProduct(s, bigger, memo);
    int side2 = side1;
    if(smaller %2==1) side2 = minProductHelper(smaller-s , bigger, memo);
    memo[smaller] = side1 + side2 ; 

    return memo[smaller];
}

int minProduct(int a, int b){
    int bigger = a<b?b:a;
    int smaller = a<b?a:b;
    return minProductHelper(smaller, bigger);
}

int minProductHelper(int smaller, int bigger){
    if(smaller==0) return 0;
    else if(smaller ==1) return bigger;

    int s = smaller >>1 
    int halfProd =  minProduct(s, bigger);
    int side2 = side1;
    if(smaller %2==0) return  halfProd + halfProd;;
    else retrun  halfProd + halfProd + bigger;

    
}

void main(String [] args){
    int n = 3;
    Tower[] towers = new Tower[n];
    for(int i = 0;i<3;++i){
        towers[i] = new Tower(i);
    }

    for(int i=n-1;i>=0;i--){
        towers[0].add(i);
    }
    towers[0].moveDisk(n, towers[2], towers[1]);
}

class Tower{
    private Stack<Integer> disks;
    private int index;public Tower(int i ){
        disks = new Stack<Integer>();
        index = i;
    }
    public int index(){
        return index;
    }

    public void add(int d){
        if(!disks.isEmpty() && disks.peek()<=d){
            System.out.println("Error placing disk" + d);
        }
        else{
            disks.push(d);
        }
    }
    public void moveTopTo(Tower t){
        int top = disks.top();
        t.add(top);
    }
    public void moveDisks(int n, Tower destination, Tower buffer){
        if(n>0){
            moveDisks(n-1, buffer, destination);
            moveTopTo(destination);
            buffer.moveDisks(n-1 , destination, this);
        }
    }
}

Arraylist<String> getPerms(String str) {
    if (str == null) return null;
    Arraylist<String> permutations new ArrayList<String>();
    if (str.length() == 0) {//base case
        permutations. add('"');
        return permutations;
    }

    char first= str.charAt(0); // get the first char
    String remainder= str.substring(l); // remove the first char
    Arraylist<String> words= getPerms(remainder);
    for(String word :words){
        for(int j =0;j<word.length(); j++){
            String s = insertCharAt(word, first, j);
            permutations.add(s);
        }
    }
    return permutations;
}
/* Insert char c at index i in word. */
String insertCharAt(String word, char c, int i) {
    String start= word.substring(0, i);
    String end= word.substring(i);
    return start+ c + end;
}

Arraylist<String> getPerms(String str) {
    Arraylist<String> result = new Arraylist<String>();
    getPerms("", str, result);
    return  result;

}


void getPerms(String prefix, String remainder, Arraylist<String> result) {
    if (remainder.length()== 0) result.add(prefix);

    int len = remainder.length();
    for (int i= 0; i < len; i++) {
        String before = remainder.substring(0, i);
        String after = remainder.substring(i+1, len);
        char c =remainder.charAt(i);
        getPerms(prefix+c, before+after, result);
    }
}

Arraylist<String> printPerms(String s) {
    Arraylist<String> result;
    HashMap<Character, Integer> map = buidFreqTable(s);
    printPerms(map, "", s.length(), result);

    return result;
}

HashMap<Character, Integer> buidFreqTable{
    HashMap<Character, Integer> map= new HashMap<Character, Integer>();
    for (char c : s.toCharArray()) {
        if(!map.containsKey(c)){
            map.put(c,0);
        }
        map.put(c, map.get(c) + 1);
    }
    return map;
}

void printPerms(HashMap<Character, Integer> map, String prefix, int remaining,Arraylist<String> result){
    /* Base case. Permutation has been completed. */
    if (remaining== 0) {{
        result.add(prefix);
        return;
    }

    /* Try remaining letters for next char, and generate remaining permutations. */
    for (Character c : map.keySet()) {
        int count = map.get(c).toInt();
        if(count>0){
            map.put(c, count-1);
            printPerms(map, prefix+c, remaining-1, result)
            map.put(c, count);
        }
    }
}

int makeChanges(int amount , int []denoms, int index){
    if(index > denoms.length-1) return 1; //last denom

    int denomAmount =denoms[index];
    int ways = 0 ;

    for(int i=0;i* denomAmount <= amount;++i){
        int amountRemaining = amount - i*denomAmount;
        ways += makeChanges(amountRemaining, denoms, index+1);
    }
    return ways;
}

int makeChanges(int n){
    int[] denoms = {25,10,5,1};
    return makeChanges(n, denoms, 0);
}


// memo

int makeChanges(int amount , int []denoms, int index, int[][] map){
    if(map[amount][index] >0) return map[amount][index];

    if(index > denoms.length-1) return 1; //last denom

    int denomAmount =denoms[index];
    int ways = 0 ;

    for(int i=0;i* denomAmount <= amount;++i){
        int amountRemaining = amount - i*denomAmount;
        ways += makeChanges(amountRemaining, denoms, index+1);
    }
    map[amount][index] = ways;
    return ways;
}

int makeChanges(int n){
    int[] denoms = {25,10,5,1};
    int[][] map = new int[n+1][denoms.length];
    return makeChanges(n, denoms, 0);
}

int GRID_SIZE = 8 ;

void placeQueens(int row, Integer[] columns, ArrayList<Integer[]> results){
    if(row == GRID_SIZE){
        results.add(columns.clone());
    }
    else{
        for(int col = 0; col<GRID_SIZE;col++){
            if(checkValid(columns, row, col)){
                columns[row] = col; //place queen
                placeQueens(row+1, columns, results);
            }
        }
    }
}


boolean checkValid(Integer[] columns, int row1, int column1){
    for(int row2 = 0;row2 < row1 ; row2++){
        int column2 = columns[row2];


        if(column1 == column2){
            return false;
        }

        int columnDistance = Math.abs(column2- column1);

        int rowDistance = row1 - row2;
        if(columnDistance== rowDistance) return false;
    }
    return true;
}

EXAMPLE
INPUT: ball , {"at","","","","ball","","","car","","","dad","",""}
OUTPUT: 4 




int search(String [] strings, String str, int first, int last){
    if(first > last) return -1;

    int mid = (last + first )/2;

    if(strings[mid].isEmpty()){
        int left = mid -1;
        int right = mid +1;

        while(true){
            if(left < first && right > last){
                return -1;
            }
            else if(right <=last && !strings[right].isEmpty()){
                mid = right;
                break;
            }
            else if(left >=first && !strings[left].isEmpty()){
                mid = left;
                break;
            }
            right++;
            left--;
        }
    }
    if(str.equals(strings[mid])){ //found it
        return mid;
    }
    else if(strings[mid].compareTo(str)<0){ //search right
        return search(strings, str, mid+1, last);
    }
    else{ //search left
        return search(strings, str, first, mid-1);
    }

}

int search(String[] strings, String str){
    if(strings == null || str == null || str=="") return -1;

    return search(strings, str,0, str.length-1);
}

FOLLOW UP
What if you have only 10 MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.



long numberOflnts = ((long) Integer.MAX_VALUE) + 1;
byte[] bitfield new byte [(int) (numberOfints / 8)];
String filename = ................
void findOpenNumber() throws FileNotFoundException {
    Scanner in = new Scanner(new FileReader(filename));
    while (in.hasNextint()) {
        int n = in.nextlnt ();
        /* Finds the corresponding number in the bitfield by using the OR operator to
        * set the nth bit of a byte (e.g., 10 would correspond to the 2nd bit of
        * index 2 in the byte array). */
        bitfield[n/8] I=1«(n%8);
    }
    for (int i= 0; i < bitfield.length; i++) {
        for (int j= 0; j < 8; j++) {
            /* Retrieves the individual bits of each byte. When 0 bit is found, print
                * the corresponding value. */
            if ((bitfield[i] & (1 << j)) == 0) {
                System.out.println (i * 8 + j);
                return ;
            }
        }
    }
}


// Follow Up: What if we have only 10 MB memory?
int findOpenNumber(String filename) throws FileNotFoundException {
    int rangeSize = (1 << 20); // 2A20 bits (2A17 bytes)
    /* Get count of number of values within each block. */
    int[] blocks = getCountPerBlock(filename, rangeSize);

    /* Find a block with a missing value. */
    int blocklndex findBlockWithMissing(blocks, rangeSize);
    if (blocklndex < 0) return -1;

    /* Create bit vector for items within this range. */
    byte[] bitVector = getBitVectorForRange(filename, blockindex, rangeSize);

    /* Find a zero in the bit vector */
    int offset findZero(bitVector);
    if (offset <0) return -1;

    /* Compute missing value. */
    return blockindex * rangeSize + offset;
}


/* Get count of items within each range. */
int[] getCountPerBlock(String filename, int rangeSize) throws FileNotFoundException {

    int arraySize = Integer.MAX_VALUE / rangeSize + 1;
    int[] blocks = new int[arraySize];
    Scanner in = new Scanner (new FileReader(filename));
    while (in.hasNextint()) {
        int value = in.nextint();
        blocks[value / rangeSize]++;
    }
    in.close();
    return blocks;
}

/* Find a block whose count is low. */
int findBlockWithMissing(int[] blocks, int rangeSize) {
    for (int i= 0; i < blocks.length; i++) {
        if (blocks[i] <rangeSize){
            return i;
        }
    }
    return -1;
}

/* Create a bit vector for the values within a specific range. */
byte[] getBitVectorForRange(String filename, int blockindex, int rangeSize) throws FileNotFoundException {
    int startRange = blockindex * rangeSize;
    int endRange = startRange + rangeSize;
    byte[] bitVector = new byte[rangeSize/Byte.SIZE];

    Scanner in = new Scanner(new FileReader(filename));
    while (in.hasNextint()) {
        int value = in.nextint();
        /* If the number is inside the block that's missing numbers, we record it */
        if (startRange <= value && value <endRange) {
            int offset = value - startRange;
            int mask = (1 <<(offset% Byte.SIZE));
            bitVector[offset / Byte.SIZE) I= mask;
        }
    }
    in.close();
    return bitVector;
}

/*Find bit index that is 0 within byte. */
int findZero(byte b) {
    for (int i= 0; i < Byte.SIZE; i++) {
        int mask= 1 << i;
        if ((b & mask)== 0) {
            return i ;
        }
    }
    return -1;
}

/*Find a zero within the bit vector and return the index. */
int findZero(byte[] bitVector) {
    for (int i= 0; i < bitVector.length; i++) {
        if (bitVector[i] =! -0) {//If not all ls
            int bitindex= findZero(bitVector[i]);
            return i *Byte.SIZE+ bitindex;
        }
    }
    return -1; 
}

void checkDuplicates(int[] array) {
    BitSet bs = new BitSet(32000);
    for (int i= 0; i < array.length; i++) {
        int num = array[i];
        int num0 = num - 1; //bitset starts at 0, numbers start at 1
        if (bs.get(num0)) {
            System.out.println(num);
        }
        else{
            bs.sgt(num0);
        }
    }
}

class BitSet {
    int [] bitset;
    public BitSet(int size){
        bitset = new int[(size>>5) +1 ]; //divid by 32
    }

    boolean get(int pos){
        int wordNumber = (pos >> 5); // divide by 32
        int bitNumber = (pos & 0x1F); // mod 32
        return (bitset[wordNumber] & (1 << bitNumber)) != 0;
    }

    void set(int pos){
        int wordNumber = (pos >> 5); // divide by 32
        int bitNumber = (pos & 0x1F); // mod 32
        bitset[wordNumber] I= 1 << bitNumber;
    }