Find The Smallest Positive Integer Not Occurring In An Array

Write a function:

function solution(A: number[]): number;

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000].

function solution(A: number[]): number {
    // Number has to be greater than zero
    let leastNumber = 1;
    // Get unique numbers only
    const uniqueSet = new Set(A);
 
    // Loop through the unique set and check if the number exists
    // If it does exist, increment by one
    // If not, return it since it's the least number
    while(uniqueSet.has(leastNumber)) {
        leastNumber++;
    }

    // Method 2
    const uniqueArray = A.filter((value: number, index: number, self: Array<number>) => self.indexOf(value) === index);

    while(uniqueArray.includes(uniqueInt)) {
        uniqueInt++;
    }

    // Method 3, not as perfomant
    A.filter(uniqueInt => uniqueInt >=1).sort((a, b) => a - b).map((val, i, self) => {
        if(uniqueInt < self[i]) return;
        uniqueInt = self[i] + 1;
    });
    return leastNumber;
   
}

Find unique items in an array

const array = [1, 2, 2, 3, 4, 4, 5]

// Method 1 (fastest)
const uniqueArray = array.filter((value, index, self) => self.indexOf(value) === index)

// Method 2
const uniqueArray = [...new Set(array)]

// Method 3
const uniqueArray = []
array.forEach(item => {
    if (!uniqueArray.includes(item)) {
        uniqueArray.push(item)
    }
})

Binary Gap

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

function solution(N: number): number;

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

function solution(N: number): number {
    // Implement your solution here
    // const solution = Math.max(...N.toString(2).split(/^0+|1+|0+$/).map(s=>s.length))

    const solution = N.toString(2).split(/^0+|1+|0+$/).sort().at(-1).length

    N.toString(2) // converts a positive integer into a binary string, 2 is the radix base

   /**
   * So 1054 would be 10000100110
   */    
    .split(/^0+|1+|0+$/ // Splits the binary string into an array of substrings, separating groups of consecutive 0s, 1s, and trailing 0s

    /**
     * So 1054 becomes ["1", "0000", "1", "001", "1"]
     * Sorting it in ascending order based on length you get ["1", "1", "001", "0000"]
     * .at(-1) gives you the largest value
     */

    return solution;
}

CyclicRotation (Rotate an array to the right by a given number of steps.)

function solution(A: number[], K: number): number[] {
    // Implement your solution here

    if(A.length === 0 || K ===0 || A.length === K) {
        return A;
    }

    K %= A.length;

    while(K > 0) {
        A.unshift(A.pop());
        K--;
    }
    return A;
}

Find unique values in an array

    const set = new Set(A);
    return Array.from(set).length;

Count numbers from a given range that are not divisible by any of the array elements

For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.

For example, consider integer N = 5 and array A such that:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6

For the following elements:

A[0] = 3, the non-divisors are: 2, 6, A[1] = 1, the non-divisors are: 3, 2, 3, 6, A[2] = 2, the non-divisors are: 3, 3, 6, A[3] = 3, the non-divisors are: 2, 6, A[4] = 6, there aren't any non-divisors. Write a function:

function solution(A: number[]): number[];

that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6

the function should return [2, 4, 3, 2, 0], as explained above.

function solution(A: number[]): number[] {
    // Implement your solution here

    const N = A.length;
    
    // Step 1: Count the frequency of each element in A
    const freq = new Map<number, number>();
    for (let num of A) {
        if (freq.has(num)) {
            freq.set(num, freq.get(num)! + 1);
        } else {
            freq.set(num, 1);
        }
    }

    // Step 2: Prepare an array to store results
    const result = new Array(N).fill(0);
    
    // Step 3: Precompute divisors and non-divisors for each element
    const maxElement = Math.max(...A);
    const divisorCount = new Map<number, number>();
    
    for (let num of A) {
        if (divisorCount.has(num)) continue; // Skip if already computed
        
        // Find all divisors of 'num'
        let divisors = 0;
        for (let d = 1; d * d <= num; d++) {
            if (num % d === 0) {
                if (freq.has(d)) divisors += freq.get(d)!;
                if (d !== num / d && freq.has(num / d)) divisors += freq.get(num / d)!;
            }
        }
        divisorCount.set(num, divisors);
    }

    // Step 4: Calculate non-divisors for each element in A
    for (let i = 0; i < N; i++) {
        const num = A[i];
        const divisors = divisorCount.get(num)!;
        result[i] = N - divisors;
    }
    
    return result;
}

The Fibonacci Series

F(n) = F(n-1) + F(n-2)

function fibonacciIterative(n) {
    if (n <= 1) return n;

    let a = 0, b = 1;
    
    for (let i = 2; i <= n; i++) {
        let temp = a + b;
        a = b;
        b = temp;
    }
    
    return b;
}