Blog

Leetcode 2275: Largest Combination With Bitwise AND Greater Than Zero

Nov 5, 2024

About

This problem focuses on finding combinations of numbers from the given array such that the bitwise & AND of all numbers are greater than or equal to 1. Out of all combinations of elements, we return the size of the largest possible combination length.

For example, [1,2,3,4,5] = 3, since the greatest combination length possible would be 1,3,5. This is because 1&3&5 is equal to 1.

Thoughts

An important thing to note about using the bitwise AND & operator is that between two numbers, only the ON (1) bits locations can stay one when performing the AND & bitwise operation. For example, 1 AND 2 would equal zero since they do not share any ON (1) bit locations, but 1 AND 3 would equal 1 since both 1 and 3 have the 1 bit turned on.

1 = 01, 2 = 10, 01 & 10 = 00
1 = 01, 3 = 11, 01 & 11 = 01

With this property noted, we can say that for a combination of numbers bitwise AND together have to share ON (1) bit locations among all of them to be greater than zero. In other words, as soon as we reach a number with a bit location that is off, said bit location in the ending result is also turned off.

Seeing this, I decided an optimal way to organize these array elements into valid combinations would be using a hashmap data structure. A hashmap can assign elements into groups based on what bit locations they have flipped on. All elements in a group are in common, as they would all share a specific ON (1) bit location.

Implementation

To solve this problem, I used the built-in Javascript Map() object to record the frequencies of elements in the array that share a specific bit location. To update both myMap and the answer variable, I created a function named “nya” on each candidate in the candidates’ array. The function nya can check each ON(1) bit location a candidate has and update the frequency of that bitmask location if it is on. Lastly, nya can update my ans variable with the maximal length of a valid combination.

For example, for test case [1,2,3,4,5], these are all my valid combinations. To save on memory space, I can update the frequency at a given bit location key instead of maintaining an array of elements at that key. In other words, sorting into buckets, but instead, I keep track of the buckets’ lengths.

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

ans = 3

Closing Thoughts

This is a pretty fun bitwise & hashmap combo problem. While coding this solution, I almost did not go with a frequency map, but instead went with keeping track of all elements in an array inside of the hashmap. Switching to keeping track of the frequency of all elements that shared an ON bit location instead of all the elements in that combo saved my bacon for sure time complexity and memory space-wise.

Leetcode 3011: Find if Array Can Be Sorted

Nov 4, 2024

DevGod

Elf Vtuber

About

There are two main parts to this problem. First, we need to be able to preform a sort on the array of values. Second, we must evaluate whether two elements in the array need to be swapped, and whether they are swappable given their count of on (1) in their binary representation of themselves. If the given array is already sorted, we can return true. If the given array is unsorted, then we must return whether it can become sorted by swapping elements when their bit counts are equal to each other. Returning false means that we have reached a point where the array is unsorted, and elements are different bit counts from each other, meaning it’s impossible to complete the swap operation.

For example:

[1,5,2] = false, 5 and 2 can’t be swapped, even though they need to be swapped
[1,2,3,4,5] = true, sure some numbers can’t be swapped, but since its already sorted we don’t need to worry

Thoughts

Since this is a bitwise problem, a while loop can find the number of on (1) bits a number has. Also, an ideal sorting algorithm to use would be bubble sort, since the problem specifies you are preforming swaps between elements. Since the main idea is to test for bit counts and whether elements in the array are less than each other, bubble sort is the first thing that popped into my head. With bubble sort, I could check how elements values differ from each other, as well as how their bit counts differ from each other.

Implementation

For my solution I went with a bubble sort approach, since bubble sort is well known for being a sort algorithm that preforms a bunch of swaps between a left and right pointer. By using a bubble sort to implement a solution, I could also include a check during swaps to check if the two elements I’m swapping at the time are different bit counts. If at any point they are different bit counts and need to be swapped, I can simply exit early and return false. Otherwise, I continue on with my business until the array is fully sorted and return true.

For finding the bit count of on (1) bits of a number, I simply use a while loop that counts the & of each first bit. Then to iterate down, I just do an arithmetic shift right, >> 1, to effectively half and floor the number each iteration until the number I am checking reaches zero.

Closing Thoughts

After rereading the question, I noticed that leetcode did specify that only two ADJACENT elements can be swapped in one operation. While my solution passes all test cases, my solution does technically break the only ADJACENT elements rule. https://www.geeksforgeeks.org/bubble-sort-algorithms-by-using-javascript/ The bubble sort algorithm template on geeksforgeeks actually follows this rule a bit better, but at the end of the day still gets the job done :p

Leetcode 1106: Parsing A Boolean Expression

Oct 18, 2024

DevGod

Elf Vtuber

About

The goal of this problem is to take a string representation of booleans and functions, then return the expected boolean value after completing the function. For example, we could have a “t” symbol for a true boolean, a “f” symbol for a false boolean, a ! for a not function, and a & and | for functions that take all elements inside of a () and return the boolean of bitwise anding and bitwise or ing all elements respectively.

For example:

&(|(f)) = Return the bitwise or of one false, then return the bitwise & of one false
|(f,f,f,t) = Return the bitwise or of three falses and one true
!(&(f,t)) = Find the bitwise and of both false and true, then return the flipped / inverted result.

Thoughts

After reading the problem, I stopped panicking about its high difficulty rating and thought back to reading up on JSFuck and BrainFuck, so decided to just make an eval statement do the work for me. I knew this would be like implementing a very minimal programming language interpreter, since “t” and “f” are like boolean constants, and the !&| symbols are like functions that accept input and return an output value.

Implementation

First I use a series of replaceAll commands to slightly edit the given expression. A big reason for replacing these symbols is due to the fact that JS functions can not be just one special character like !&|, since those characters are reserved for bitwise operations. Once I have my expression edited, I then append some string representations of JS functions for returning the flipped value of a given boolean, as well as returning the bitwise OR / AND of all elements given in the function’s args. Lastly, I then return the result given by running the JS eval command with my slightly modified string.

Leetcode 962: Maximum Width Ramp

Oct 17, 2024

DevGod

Elf Vtuber

About

So this problem is basically asking about finding the longest distance between two indexs of an array such that the left index is lower then the right index, and that the value at the left index is smaller then the value at the right index.

Another way to look at this problem is to pick two indexs, I and J, such that the index I appears before index J, as well as the number at nums index of I being smaller then the value at nums index of J.

In other words, Number I must appear before J in the array, and number I must be smaller than number J in the array.

For example [(1),2,3,4,(5)] = Minimal distance between elements 5 and 1 is 4 [(1),0,2,(3)] = Minimal distance between elements 1 and 3 is 3 [6,3,(2),1,5,(3)] = Minimal distance between the last 3 and the middle 2 is 4

Thoughts

I immediately misread the questions and assumed it was talking about finding the largest increasing monotonic stack by traversing left to right in the test case array. However, even after realizing this wasn’t the case, I was still determined to use a monotomic stack for this problem.

Rethinking about the problem, I realized that for each right most index, the distance value that would be returned was the distance between itself and the leftmost index of any element that is smaller then the right most index’s value. For example, for a testcase like [200,5,4,3,2,1,100] at the index for element 100, you would consider only 5,4,3,2,1 since those are values that are smaller then 100. the 200 can then be ingnored.

Also I realized that the way to get a maximal distance would be using classic monostack popping until you reach a point where you can no longer pop. For example, with testcase [200,5,4,3,2,1,100], you could have a monostack like [200,5,4,3,2,1], and then pop elements 5,4,3,2,1 you are left with 200.

For testcases like [10,1,2,3,11], your monostack that you start with initally should just elements such that each element is less then its prevous elements. For example, you would only need to have [10,1] to evaluate from the 11 element. This is due to being 2 and 3 being larger then 1, but also appearing after 1 in the array. Since 1 is already smaller then the next elements, 2 and 3, and can greedily say that 2 and 3 are not good choices, since 1 is already smaller then thoose two values.

Lastly, with a problem like this I am sure that while my monoStack is going to use the values of the array for comparisons, I am storing indexs inside of the monoStack itself. This way, I am able to do a distance calculation between two different points in the array if certian conditions are meet.

Implementation

First, I use a for loop to form a decreasing monoStack in Javascript like I usually do. However, I dont preform any popping operations, only pushs when I find numbers that are smaller then the previous number on the top of the stack.

I then a second for loop, this time moving from right to left, to remove elements from my monoStack if they are smaller or equal to my current number. I also update my max varible with the max possible distance between the index. This is simply done my taking my current Rightmost index on my, and then subtracting the index on the top of the stack, which represents the rightmost index of the next element in the array that is smaller than my rightmost index’s value.

Finally, I just return max which after the second for loop runs, contains my maximal distance / maximal ramp width to leetcode.

Leetcode 921: Minimum Add To Make Parentheses Valid

Oct 7, 2024

DevGod

Elf Vtuber

About

This problem is very similar to yesterday’s problem. The main difference is instead of swapping characters that are already present in the string, we are appending either a ”(” or a ”)” anywhere we want in the string. However, we still have the same goal of finding the minimal number of operations needed to achieve a balanced string of () such that each opening symbol ( has a corresponding symbol ).

For example

((), needs 1 ) symbol at the end to become balanced
()()() is already balanced, so return 0
))) needs 3 opening symbols to become balanced

Thoughts

My thoughts immediately jumped to yesterday. The only difference is I ended up having two variables, one for the remainder of unmatched opening symbols, and one for the unmatched closing symbols. Once I was able to find these two values, at first I mistakenly thought it was some sort of find the max value between them. But in practice, it is the addition of both values together to get the minimal number of additions needed to balance the string.

Implementation

Here in JS, I use a for loop to iterate through the test case string, while also finding the leftmost character & the rightmost character. After I have these varibles, I am then able to move left to right to calculate the remainder of opening ( symbols, while also moving right to left to find the remainder of closing ) symbols. After my for loop is completed, I then return the amount of unmatched opening ( symbols plus the amount of matched closing symbols ) together.