# CoDEVIANT #14 (9/30/20) — The 2020 Terrorscape

Hey everyone…miss me? I was gone for a long-ass time. I’ve been doing some streaming, sang some opera, coded with a company for a nice chunk of time, and now I’m out of a job due to COVID and am looking for the next gig to learn and grow in.

I found a list of interesting problems and I’m going to try and solve them as best as I can and break down my thought process. Then I’ll find better solutions from people who are much smarter than I am, and try to break that process down.

Problem 1:

— — — — — — — — — — — — — — — — — — — — — — — — — — -

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);

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].

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — -

My answer:

`function solution(N) {`

let array = N.toString(2).split("")

let counter = 0

let max = 0

let spareArray = []

array.forEach(i => {

if(Number(i) === 1) {

spareArray.push(max)

counter = 0

} else {

counter++

max = counter

}

})

return spareArray.sort()[spareArray.length - 1]

}

My approach was something like:

- Turn the number into a binary:

I accomplish this by using*toString(2)*on the*N*argument passed into the function. - I then turn the binary number into an array

I accomplish this by chaining the*split(‘’)*method onto binary derived from the step above - And we package that guy into the variable named
*array*

- I set
*counter*and*max*to equal 0 - I create an empty array called
*spareArray.*

Then I use the *forEach *array method on the *array* variable and basically if the element in the array being iterated over is 1, then we push what *max* is into the spare array and set the *counter *to 0. However, if it is **not **1, then

*counter*is augmented by 1 and

*max*takes on the value of

*counter*

Finally I return the last element of *spareArray* after it has been sorted.

For the test case values of *1041*, *15*, and *32*, my solution passes!

Now let’s see how the really smart people did it.

The smart person’s solution comes from hhsadiq.

`export function solution(N) { `

const binaryString = N.toString(2);

const start = '10'; const end = '01';

let startIndex = binaryString.indexOf(start);

let endIndex = -1;

let binaryGap = 0;

// Remember that N is the

// input number, and when you iterate over its binary representation, its always

// log(N).

while (startIndex >= 0) {

endIndex = binaryString.indexOf(end, startIndex);

if (endIndex < 0) {

break;

}

const tempGap = endIndex - startIndex;

binaryGap = tempGap > binaryGap ? tempGap : binaryGap;

startIndex = binaryString.indexOf(start, endIndex + 1);

endIndex = -1;

}

return binaryGap;

}

*start*is ‘10’*end*is ‘01’*binaryString*is like how we handled*N*in our solution.- We have
*startIndex*equal the indexOf where ‘10’ (aka*start*) is at in the*binaryString.*

If *startIndex* is more than or equal to 0, *endIndex *becomes the result of the *indexOf* method being run on the *binaryString* variable with the arguments **‘01’ ( end) <WHAT WE ARE SEEKING> **and

**0**(

**<**

*startIndex)***Index of the string from which to start searching**>

Assuming we pass in the number **154**, the binaryString is going to be *10011010*. We find the first instance of ‘01’, at position 2 [*we count from 0 onwards looking for the start of ‘01’*] so we get a 2 for the *endIndex.*

In the following if-statement, we see whether or not

if(endIndex < 0 ) {

break;

}

We just said that *endIndex *is **2**, so this doesn’t apply…

We state that *tempGap* should equal *endIndex {2} *minus *startIndex {0}, *which equals **2.**

Then *binaryGap* is evaluated by using a ternary operator to compare whether *tempGap* is larger than *binaryGap. *If *tempGap* is larger than *binaryGap*, then *tempGap* will equal the value we calculated for *tempGap*. And if what is already present for *binaryGap* is larger than *tempGap, binaryGap *stays what it is.

Then we set *startIndex* to equal the index of *binaryString* where we find *start* {which remains ‘10’} and the place where we begin starting our search again will equal what *endIndex* became plus 1.

Then *endIndex* equals -1* *and we continue with what our while loop does so long as the *startIndex* is more than or equal to 0.

Ultimately, we return the *binaryGap* variable which will always be the largest *tempGap* value that was returned.

//On the second go around, the *startIndex* is 4 and the *endIndex* is 5. *tempGap* equals *endIndex{5}- startIndex{4} // 1. *One is not larger than the *binaryGap* we established the first go around {2}, so the *binaryGap *stays the same {2}….

I hate this solution. I don’t know if it’s my ADHD, but this has so many moving parts that are hard for my brain to hang on to at any one given second. I see how the *startIndex* and the *endIndex *use some simple arithmetic to give us the *tempGap* and potentially our *binaryGap*. I think my solution, while making extraneous extra arrays in the code-block, was a more simple to understand solution.

=================================

Problem 2:

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

function solution(A, K);

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

A = [3, 8, 9, 7, 6] K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7] [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9] [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0] K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4] K = 4

the function should return [1, 2, 3, 4]

Assume that:

- N and K are integers within the range [0..100];
- each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

— — — — — — — — — — — — — — — — — — — — — -

My solution:

`function solution(A, K) {`

let arr = []

if(K === A.length) {

arr = A

} else {

A.forEach((i, index) => {

let numba = index - K

if(numba < 0) {

numba = index + (K - 1)

}

arr.push(A[numba])

})

}

return arr

}

My thought process:

- We make an empty array called
*arr*. - If
*K*equals the length of the*A*array,*arr*will be the*A*array. - If
*K*isn’t the same as*A*’s length, then for each element in*A*, we’ll have*numba*equal the index of the A-element being looped through at that moment**minus***K.* - If
*numba*is less than 0, numba is going to equal {*index + (K — 1)*} - Then we push
*A*[*numba*] into the*arr*array. - Then we return the
*arr*array.

Basically the idea is that we swap around the placement of the elements in an array.

[3, 8, 9, 7, 6] , K = 3.

So we’re trying to re-arrange the place of the elements by counting 0 to K from the start of a given element.

[9, 7, 6, 3, 8]

Anyways, my solution worked with simple arguments, however, it’s not a fool-proof solution. Let’s checkout a more robust solution.

`function solution(A, K) { `

K = (A.length > K) ? K : K % A.length;

var d = A.slice(0, A.length - K);

var e = A.splice(A.length - K);

return e.concat(d);

}

Okay…in the first line we determine what K is going to be.

- If the length of A is more than the argument passed in for
*K*at the outset, then*K*stays as it is. Otherwise,*K*is going to be the**remainder**of*K*divided by*A’s*length. *d*equals a slice of the A-array starting at the zero-index position ending at the indexthe A.length-K .*before**e*equals a**splice**of the A-array passing in A.length — K.

This means that we will get the values of A from the zero-index position of the argument forward.- We return
concatenated with*e*.*d*

Basically, we’re figuring out what parts of the array we are divvying up and then we are arranging them backwards. :)

Come back tomorrow!