CareerCup

Hi I have a code for this, but the problem is that its terribly slow. The max volume is decided recurently by observing the fact that at each song you have only two choices, increase the volume by current difference, or decrease. So the recurent function makes a binary tree with cutoffs, where the current volume is out of bounds the code stop reccur deeper.
At worst case there are 2^n possible volumes for last song. And the number of additions or subtractions that the code perform will be the same as number of edges in the tree. So i guess if you define n as volume levels in array the complexity would be 2^n+1?

the code below

public static int maxVolume(int vol[], int init, int max)
    {
        return max(vol, init, max, 0);
    }
    
    private static int max(int vol[], int init, int max, int level)
    {
        if(init < 0 || init > max)return -1;
        if(level == vol.length)return init;
        int maximum = max(vol, init + vol[level], max, level + 1);
        int maximum2 = max(vol, init - vol[level], max, level + 1);
        return Math.max(maximum, maximum2);
    }

     public static void main(String []args){
        System.out.println(maxVolume(new int[]{5,3,7}, 5, 10));//10
        System.out.println(maxVolume(new int[]{1,1,1}, 0, 5));//3
        System.out.println(maxVolume(new int[]{9,1,5,4}, 8, 15));//-1
        System.out.println(maxVolume(new int[]{4,9,1,5,4}, 8, 15));//13
     }

Hi this is one of this problems that looks extremaly intimidating but somehow ends up being easy. If you check the number of ways for first few stairs length you can see that ways one can climb a staircase in respect to staircase length grows exacly like fibonacci number sequence. Lets say one step move = 1, and two steps move = 2. Possible ways for:
1 step staircase => 1 = {1} -> 1 way
2 step => 2 = {1+1}, {2} -> 2 ways
3 step => 3 = {1+1+1}, {1+2}, {2+1} -> 3 ways
4 step => 4 = {1+1+1+1}, {1+1+2}, {2+1+1}, {1+2+1}, {2+2} -> 5 ways
5 step => 5 = {1+1+1+1+1}, {2+1+1+1}, {1+2+1+1}, {1+1+2+1}, {1+1+1+2}, {2+2+1},
{1+2+2}, {2+1+2} = 8 ways.
ways(5) = ways(4) + ways(3) = 5 + 3 = 8.
I use sequencial code for optimal space complexity and additional array to store partial results to reduce time complexity to linear.

public static int countWays(int n)
	{
		if(n < 1)return -1;
		if(n == 1)return 1;
		int res[] = new int[n+1];
		res[1] = 1;
		res[2] = 2;
		
		for(int i = 3; i < n+1; i++)
		{
			res[i] = res[i-1] + res[i-2];
		}
		
		return res[n];
	}
	
	public static void main(String args[])
	{
		for(int i = 1; i < 10; i++)
		System.out.println(countWays(i));
	}

I dig a little into Wikipedia, so my code takes advantage of the fact that every prime number can be described as 6k + 1 or 6k - 1, and the fact if you check if number is prime, you don't need to check bigger divisors than square root of number we check.
So isPrime(n) function checks if number can be divided by divisors that are smaller than sqrt(n) and can be described as 6k + 1 or 6k - 1 or 2 and 3. 2 and 3 are only valid divisors that are not 6k +-1.
countPimes(low, high) function check for primality only numbers that are between low and high, and can be described as 6k+1 or 6k-1.

public static boolean isPrime(int n)
    {
        if(n == 2 || n == 3)return true;
        if(n % 2 == 0 || n % 3 == 0 || n <= 1)return false;
        int i = 5;
        int increment = 2;
        while(i*i <= n)
        {
            if(n % i == 0)return false;
            i+=increment;
            increment=6-increment;
        }
        return true;
    }
   
    public static int countPrimes(int low, int high)
    {
        if(low > high)return -1;
        //special cases because while loop checks numbers >= 5
        if(low == high && low == 2 || low == high && low == 3)return 1;
        int counter = (low <= 2 && high >=3) ? 2 : 0;
        int increment;
        //set first number to check if its prime checking only 6k-1 or 6k+1
        if(low % 6 == 0){
            low += 1;
            increment = 4;
        }else{
            low = (((low/6) + 1)*6) - 1;
            increment = 2;
        }
        
        while(low <= high)
        {
            if(isPrime(low))counter++;
            //checking only numbers that can be described as 6k-1 or 6k+1. Increment provides this capability
            low += increment;
            increment = 6 - increment;
        }
        return counter;
    }

     public static void main(String []args){
        System.out.println(countPrimes(32, 81));//11
     }

public static int reverse(int n)
    {
        int res = 0;
        while(n > 0)
        {
            int digit = n % 10;
            res = res * 10 + digit;
            n /= 10;
        }
        return res;
    }

     public static void main(String []args){
        System.out.println(reverse(78421));//12487
     }

Unfortunately I have only relatively slow O(list.length * digits in each list member) solution to the problem. Inside my algorithm there is a for loop that for every number in a collection calls another function countDigit(int n, int digit) that counts how many times digit appears in that number. countDigit is recursive function with O(digits in number) complexity.

import java.util.*;

public class Example{
    
    public static int countDigit(int n, int digit)
    {
        if(n == digit)return 1;
        if(n == 0 && n != digit)return 0;
        if(n % 10 == digit)
        {
            return 1 + countDigit(n/10, digit);
        }else
        {
            return 0 + countDigit(n/10, digit);
        }
        //for example n = 3242 digit = 2;
        //1. 3242 % 10 == 2 so return 1 + countDigit(3242/10, 2)
        //2. 324 % 10 != 2 so return 0 + countDigit(324/10, 2)
        //3. 32 % 10 == 2 so return 1 + countDigit(32/10, 2);
        //4. 3 % 10 != 2 so return 0 + countDigit(3/10, 2);
        //5. 0 == base case so return 0;
        //countDigit = cD
        //cD(3242, 2) = 1 + cD(324, 2); cd(3242, 2) = 1 + 0 + cD(32, 2);
        //cd(3242, 2) = 1 + 0 + 1 + cd(3, 2); cd(3242, 2) = 1+0+1+cD(0, 2) = 1+0+1+0 = 2;
    }
    
    public static int howMany(List<Integer> list, int digit)
    {
        int counter = 0;
        for(int number : list)
        {
            counter += countDigit(number, digit);
        }
        return counter;
    }

     public static void main(String []args){
        List<Integer> list = new ArrayList<Integer>();
        list.add(2);
        list.add(12);
        list.add(245);
        list.add(34);
        list.add(764);
        list.add(2227); 
        list.add(324262);
        
        int number = 2;
        
        System.out.println("In list there are " + howMany(list,  number) + " digits equals " + number);
        //In list there are 9 digits equals 2
     }
}

Hi. I couldn't find a O(n) algoritm to it that would truly work without any extra space. I only have O(nlogn) in place solution. So the basic idea is to try to split the array to two regions left and right. In right half of the array you have all the second largest at last, fourth largest at last -1 etc. You can do it in one for loop with swap function inside, and after this loop you have all this elements in place. In the left half of the array after the for loop you have all the elements like largest at first, third largest at second etc. but they are out of place so we need to sort it. I choose quicksort to sort left half of array in desc order to do it in place.
For example {1,2,3,4,5,6} array after for loop should be something like this {4,2,6,1,3,5}.Notice left half out of order so we quick sort left half and we have our answer {6,4,2,1,3,5}.

public class Order{
    
    public static void quickSort(int a[], int left, int right)
    {
        if(left >= right)
        {
            return;
        }else
        {
            int pivot = partitionIt(a, left, right);
            quickSort(a, left, pivot - 1);
            quickSort(a, pivot, right);
        }
    }
    
    public static int partitionIt(int a[], int left, int right)
    {
        int pivot = right;
        
        while(true)
        {
            while(left < right && a[++left] > a[pivot])
            ;
            while(right > left && a[--right] < a[pivot])
            ;
            
            if(left < right)
            {
                swap(a, left, right);
            }else
            {
                break;
            }
        }
        
        swap(a, left, pivot);
        return left;
    }
    
    private static void swap(int a[], int ind1, int ind2)
    {
        int temp = a[ind1];
        a[ind1] = a[ind2];
        a[ind2] = temp;
    }
    
    public static void reOrder(int a[])
    {
        int right = a.length - 1;
        //for loop shift apropriate group of numbers to right half
        //taking advantage of fact that input is sorted
        for(int i = a.length - 2; i >= 0; i -= 2)
        {
            swap(a, i, right--);
        }
        //sort left group, because they are out of place even thou in apropriate group
        quickSort(a, -1, right);
    }
    
     public static void main(String []args){
         int a[] = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14};
         reOrder(a);
         for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        //14,12,10,8,6,4,2,1,3,5,7,9,11,13
     }
}

To calculate sum of all leaves in a Tree i use modified traverse function. The function is recursive, first it calculates the sum of leaves in left subTree of a node, then the leaves of right subTree, and then returns sum of left + right. To identify a leaf node it checks if its leftChild and rightChild are null. If they are null it returns a value of current node. The code is in java. To make code simpler i use only Node class without tree.

public class SumLeafExample{
    
    public static class Node{
        private int key;
        private Node left;
        private Node right;
        
        public Node(int key)
        {
            this.key = key;
            this.left = null;
            this.right = null;
        }
        
        public void insert(int key)
        {
            insert(key, this);
        }
        
        private void insert(int key, Node localRoot)
        {
            if(key < localRoot.key)
            {
                if(localRoot.left != null)
                {
                    insert(key, localRoot.left);
                }else
                {
                    localRoot.left = new Node(key);
                }
            }else
            {
                if(localRoot.right != null)
                {
                    insert(key, localRoot.right);
                }else
                {
                    localRoot.right = new Node(key);
                }
            }
        }
        
        public int leafSum()
        {
            return leafSum(this);
        }
        
        private int leafSum(Node localRoot)
        {
            if(localRoot == null)return 0;
            if(localRoot.left == null && localRoot.right == null)
            {
                return localRoot.key;
            }else
            {
                int leftSum = leafSum(localRoot.left);
                int rightSum = leafSum(localRoot.right);
                return leftSum + rightSum;
            }
        }
    }

     public static void main(String []args){
        Node treeRoot = new Node(20);
        treeRoot.insert(10);
        treeRoot.insert(30);
        treeRoot.insert(18);
        treeRoot.insert(29);
        treeRoot.insert(45);
        
        System.out.println(treeRoot.leafSum());
        //18 + 29 + 45 = 92
     }
}

public static int lucas(int n)
    {
        int res[] = new int[n + 1];
        for(int i = 0; i < res.length; i++){res[i] = -1;}
        return lucas(n, res);
    }
    
    public static int lucas(int n, int res[])
    {
        if(res[n] != -1)
        {
            return res[n];
        }else{
            
             if(n == 0 || n == 1)
            {
                res[n] = 0;
                return res[n];
            }
            if(n == 2)
            {
                res[n] = 1;
                return res[n];
            }
            
            res[n] = lucas(n-1, res) + lucas(n-2, res) + lucas(n-3, res);
            return res[n];
        }
    }

     public static void main(String args[]){
        for(int i = 0; i <= 10; i++)
        {
            System.out.println(lucas(i));
		//0,0,1,1,2,4,7,13,24,44,81
        }
     }

1.So basically the solution could be the recursive function, which takes N as argument, and then makes this N a divisior of a fraction. And then inside, there would be a while loop. And every repetition of the while loop would represent one fraction from 1/N to N-1/N {if N = 4 then 1/4;2/4;3/4}. During every repetition of while loop we check if the fraction is reducable. If its not reducable we increase the counter by one. Counter will track every valid fraction that we need to count. After while loop we return another call to our function with N reduced by one. The base case of recursion would occur when N == 1. In that case we return the counter. So for example if N = 4, then every repetition of while loop represent 1/4, 2/4, 3/4.

EDIT:<s> (But in cases when N is an odd number we don't need to run while loop because every fraction in that case would not be reducable, so in this case we would just increment our counter by current N -1. For example if N = 5 then 1/5, 2/5, 3/5, and 4/5 are all not reducable so we don't need to check that and just increment counter by N-1.)</s>.Unfortunately i was wrong in this one. The fraction is irreducible only if divisor is a prime number not odd number:(

2. To check if fraction is reducable we would need to check if Greatest Common Divisor of Dividend and Divisor of our fraction is bigger than 1. If it's bigger than a fraction is reducable and we do not count it.

3. In my code Greatest Common Divisior function is named NWD(int a, int b), divident of a fraction = l, and divisor = m.

public static int countFractions(int n, int counter)
    {
	if(n < 1)return -1; //error
        if(n == 1)return counter;
        int l = 1;//dividend
        int m = n;//divisor
            while(l < m)
            {
                if(!isReducable(l++, m))counter++;
            }
        return countFractions(n - 1, counter);
    }

	private static boolean isReducable(int l, int m)
    {
        return (NWD(m,l) > 1);
    }
	//NWD function is Just Greatest Common Divisor
	private static int NWD(int a, int b)
    {
        if(b == 0)
        {
            return a;
        }else
        {
            return NWD(b, a % b);
        }
    }