DEV Community: Shalom Steinmetz

Multiplication Without Multiplication Operators

Shalom Steinmetz — Wed, 17 Jan 2024 16:40:03 +0000

A problem I learned about from the book Cracking The Coding Interview is how to multiply two numbers without using multiplication and division operators. I decided to write down what I learned from the solution since I find it to be a fascinating solution.

Naive Approach

The most straightforward method involves repeatedly adding the multiplicand by the value of the multiplier (e.g., for 3 * 5, it would be calculated as 5 + 5 + 5). However, while this naive approach is conceptually simple, it is not the most efficient solution, as it necessitates the use of the addition operator multiple times. In exploring more optimized strategies, we aim to minimize the frequency of addition operations and enhance computational efficiency.

Divide and Conquer

To minimize the use of addition operations, we use a divide-and-conquer approach. Calculating half of the multiplication and then doubling the result (e.g., 4 * 5 = (2 * 5 + 2 * 5)) becomes the key strategy. This involves dividing the smaller half successively until reaching one or zero. For each division, we calculate the multiplication by dividing the smallest multiplicand in half and doubling the result.

function minProduct(a, b) {
    let bigger = a < b ? b : a;
    let smaller = a < b ? a : b;
    return minProductHelper(smaller, bigger);
}

function minProductHelper(smaller, bigger) {
    if (smaller === 0) {
        return 0;
    } else if (smaller === 1) {
        return bigger;
    }

    let s = smaller >> 1; // Divide by 2
    let side1 = minProductHelper(s, bigger);
    let side2 = side1;

    if (smaller % 2 === 1) {
        side2 = minProductHelper(smaller - s, bigger);
    }

    return side1 + side2;
}

This technique will only work if the result of half of the multiplication is an even number. If it's an odd number, we will do the same thing we did for the first half. We divide it until we reach zero or one and then double it.

In conclusion, the divide-and-conquer technique provides a fascinating solution to multiply two numbers efficiently without using multiplication and division operators. It shows the beauty of algorithmic thinking and helps to explore unconventional computational strategies.

Exploring Unique Character Detection

Shalom Steinmetz — Sun, 22 Oct 2023 18:34:33 +0000

A question that you may get asked in a technical interview is to write a function that will determine if all characters in a string our unique. In this blog post, we'll examine multiple approaches to solving this problem using JavaScript. We'll start with a simple solution using a Set object, then dive into more efficient techniques involving bit manipulation.

The Problem

The task is to write a function that checks if all characters in a given string are unique. For instance, isCharactersUnique('foo') should return false, while isCharactersUnique('bar') should return true.

The Set Approach

Let's begin with a straightforward solution using a Set object to keep track of the characters we have already seen.

function isCharactersUnique(characters) {
  const foundCharacters = new Set();
  for (let character of characters) {
    if (foundCharacters.has(character)) {
      return false;
    }
    foundCharacters.add(character);
  }
  return true;
}

This approach is intuitive and easy to understand, making it suitable for most cases.

Bit Array Technique

For a potentially more efficient method, we can employ a bit array.


function isCharactersUnique(string) {
  string = string.toLowerCase();
  let counterTable = Number();
  for (const character of string) {
    const characterCode = character.charCodeAt() - "a".charCodeAt();
    const mask = 1 << characterCode;
    if (counterTable & mask) return false;
    counterTable |= mask;
  }
  return true;
}

Here, we assume that all characters in the string are lowercase. This technique involves using a bit array to keep track of the characters encountered, toggling bits based on character codes. This method can be more efficient in terms of space compared to the Set approach.

Handling a Larger Character Set

What if you need to handle a wider character set, such as the entire ASCII character set? The previous solution wouldn't work since we would get an integer overflow when shifting more than 32 bits. Instead, you can use an array containing four bit arrays.

function isCharactersUnique(string) {
  const counterTable = new Array(4).fill(0);
  for (const character of string) {
    const characterCode = character.charCodeAt();
    if (characterCode < 0 || characterCode > 127) {
      throw new Error("Invalid character code");
    }
    const bucketIndex = Math.floor(characterCode / 32);
    const index = characterCode % 32;

    const mask = 1 << index;
    if (counterTable[bucketIndex] & mask) {
      return false;
    }
    counterTable[bucketIndex] |= mask;
  }
  return true;
}

This approach efficiently handles the entire ASCII character set by organizing the characters into different bit arrays. We use floor division to determine which index in our array of bit arrays to use and then use the modulo operator to determine which bit to flip.

Conclusion

In this blog post, we delved into different techniques for determining if all characters in a string are unique. We discussed the Set approach, bit manipulation, and handling a broader character set. Depending on your specific requirements and constraints, you can choose the method that best suits your needs. By exploring various solutions, you enhance your problem-solving skills and open your mind to innovative ways to tackle challenges.

Extracting Ones from an Integer Using the Modulo Operator

Shalom Steinmetz — Wed, 11 Oct 2023 20:58:12 +0000

In this post, I'll discuss an uncommon use case for the modulo operator: extracting ones from an integer. Let's say we have a variable that is of type Integer and we we want to know how many ones there are. For example, the number 12 has 2 ones. How do we extract the ones digit? The inefficient way to do this would be to convert the integer to a string, grab the last character from the string, and then convert it back to an integer like this:

integer = 555

# Inefficient way - don't do this
ones_string = str(integer)[-1]
ones = int(ones_string)

Fortunately, there's a more elegant and efficient solution. You can use the modulo operator to obtain the ones digit directly, as follows:

# Efficient way - do this
ones = integer % 10

By taking the remainder when dividing the integer by 10, we effortlessly isolate the ones digit. This method not only simplifies the task but also improves code readability and performance.