Joint session: Tomiwa & I.md

Question One.

Find the sum of the first n numbers.. where 1 < n > 1000000.

Question Two.

Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers, each of which is in the range 2 to 100 inclusive. Since the answer can be large, return the answer modulo 10e9 + 7. Note: A partition that contains numbers with leading zeroes will be invalid and the initial string does not contain leading zeroes. Take for example the input string to be s = "11373", then this string can be split into 6 different ways as [11, 37, 3), [113, 7, 3), [11, 3, 73), [11, 37, 3), (113, 73) and [11, 373) where each one of them contains only prime numbers.

s = "11373"
[[11, 37, 3], [113, 7, 3], [11,3,73], [113, 73], [11. 373]]

if a partition is "03", it's invalid

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

def solution(X, Y, D)

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

X = 10
Y = 85
D = 30
the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Write an efficient algorithm for the following assumptions:

X, Y and D are integers within the range [1..1,000,000,000];
X ≤ Y.

Find the longest increasing or decreasing sequence in an array.

Input: [1,2,3,0,6,5,4,3,2,1]
Output: 6 i.e [6,5,4,3,2,1] is the longest sequence

Input: [1,2,3,4,2,1]
Output: 4 i.e [1,2,3,4] is the longest sequence

Input: [1,2,2,1]
Output; 2 i.e [1,2] or [2,1] is the longest sequence

Dynamic Programming solution

function sequence(arr){
    var dp = new Array(arr.length);
    for(var i = 0; i < dp.length; i++){
        dp[i] = new Array(2)
        dp[i].fill(1)
    }

    for(var i = 0; i < arr.length; i++){
        for(var j = i-1; j >= 0; j--){
            if(arr[j] < arr[i]){
                dp[i][0] = Math.max(dp[j][0]+1, dp[i][0]);
            }
            if(arr[j] > arr[i]){
                dp[i][1] = Math.max(dp[j][1]+1, dp[i][1]);
            }
        }
    }
    var maxRow = dp.map(function(row){ return Math.max.apply(null, row); });
    return Math.max.apply(null, maxRow)
}
}

Question 2 solution:

function allPrimes(s){
    var output = []
    helper([], s)
    return output.length % 10e9+7;

    function helper(curr, s){
        if(s.length == 0){
            output.push([...curr])
            return
        }
        for(var i = 0; i < s.length; i++){
            var substr = s.substring(0, i+1)
            if(substr[0] != '0' && checker(substr)){
                curr.push(substr);
                helper([...curr], s.slice(i+1))
                curr.pop();
            }
        }
    }
}

function checker(n){
    if(n == '1') return false
    for(var i = 2; i < Number(n); i++){
        if(Number(n)%i == 0) return false
    }
    return true;
}

function blah(s){
    var output = []
    helper([], s)
    return output.length % 10e9+7;

    function helper(curr, s){
        if(s.length == 0){
            output.push([...curr])
            return
        }
        for(var i = 0; i < s.length; i++){
            var substr = s.substring(0, i+1)
            if(substr[0] != '0' && checker(substr)){
                curr.push(substr);
                helper([...curr], s.slice(i+1))
                curr.pop();
            }
        }
    }
}

function checker(n){
    if(n == '1') return false
    for(var i = 2; i < Number(n); i++){
        if(Number(n)%i == 0) return false
    }
    return true;
}

Better rename that function well 😆

Question 3 solution

function jump(x, y, d){
    let counter = 0;
    while(x < y){
        counter++;
        x += d;
    }
    return counter
}


function jumpOptimize(x, y, d){
    return (y-x)%d == 0 ? (y-x)/d : Math.floor((y-x)/d)+1;
}

Updated Version - Longest Sequence

Find the longest sequence in a given array.

Input: [1,2,3,0,6,5,4,3,2,1]
Output: 6 i.e [6,5,4,3,2,1] is the longest sequence

Input: [1,2,3,4,2,1]
Output: 4 i.e [1,2,3,4] is the longest sequence

Input: [1,2,2,1]
Output; 2 i.e [1,2] or [2,1] is the longest sequence

"""
    Given an array of numbers in any order - sorted or not, return the length of the longest sequence..
    This is a variant to a stock question - longest price rise and drop.
    Original code by Adesanya Tomiwa [https://github.com/Tomesyy]
    What this code does is compute the longest sequence in increasing and decreasing order then returns the max length
"""

def longestSequence(array):
    dp = [[1 for _ in range(len(array))] for _ in range(2)]
    for i in range(len(array)):
        for j in range(i - 1, len(array)):
            if array[j] < array[i]:
                dp[0][i] = max(dp[0][j] + 1, dp[0][i])
            if array[j] > array[i]:
                dp[1][i] = max(dp[1][j] + 1, dp[1][i])

    # There should be a beautiful way to do this but ko kan aye.
    return max(max(dp[0]), max(dp[1]))

if __name__ == '__main__':
    print(longestSequence([1,2,3,0,6,5,4,3,2,1]))
    print(longestSequence([1,2,2,1]))
    print(longestSequence([1,2,4,0,-1,19,4,3,2,1]))
    print(longestSequence([1,2,3,4,2,1]))