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 index before the A.length-K .
- 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 e concatenated with 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!