537. Complex Number Multiplication

MediumMathStringSimulation
Leetcode Link

Problem Description

In this problem, we are given two complex numbers in the form of strings, where the format of each string is "real+imaginaryi". The task is to multiply these two complex numbers and output the result as a string in the same format. Complex numbers are numbers that include a real part and an imaginary part. The imaginary part is represented by 'i', and by definition, i^2 = -1. Multiplication of two complex numbers follows the distributive property from algebra and the special rule of i^2.

The inputs:

  • num1: a string representation of the first complex number.
  • num2: a string representation of the second complex number.

Each part of the complex numbers (real and imaginary) are within the range of [-100, 100].

The output:

  • A string that represents the multiplication of num1 and num2 following the structure "real+imaginaryi".

Intuition

To solve this problem, we can break it down by:

  1. Parsing the input strings to extract the real and imaginary parts as integers.
  2. Performing the multiplication of two complex numbers using the following formula from complex number arithmetic: (a+bi)(c+di) = ac + adi + bci + bdi^2
  3. Simplifying the equation by considering that i^2 = -1. This will give us: (a+bi)(c+di) = (ac - bd) + (ad + bc)i
  4. The terms ac - bd and ad + bc give us the real and imaginary parts of the result, respectively.
  5. Convert these parts back into the string format, following the required output format.

The implementation of this intuition is straightforward algebra. Given this structure, we split the real and imaginary parts of each input number, perform the arithmetic, and combine the results into a string formatted as a complex number.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The implementation of the solution follows the mathematical approach detailed in the previous section. Here, we discuss how the provided Python code adheres to the formula (a+bi)(c+di) = ac - bd + (ad + bc)i for multiplication of complex numbers.

  1. Parsing the Input: The first step in the solution is to parse the input strings num1 and num2. We want to extract the real part (a or c) and the imaginary part (b or d) separately for each number.
  • We use the split('+') function to separate the real and imaginary parts from the num1 and num2 strings since they follow the format "real+imaginaryi". It splits the string into two parts wherever the '+' sign appears.
  • To ignore the imaginary unit 'i' at the end of the string, we use the slicing operation [:-1] which gives us all the characters in the string except the last one.
  • The map function is then applied to convert both parts into integers. The real and imaginary parts are stored in variables a, b for num1 and c, d for num2.
  1. Multiplying the Complex Numbers: Next, we calculate the multiplication of the complex numbers using the distributive property and by considering i^2 = -1. The actual multiplication is performed using the following components:
  • a * c - b * d is the real part of the result. This comes from multiplying the real parts and subtracting the product of the imaginary parts (since i^2 = -1).
  • a * d + b * c is the imaginary part of the result. This represents the sum of the products of the real part of one number with the imaginary part of the other.
  1. Formatting the Result: Finally, we need to format the result into the required string format "real+imaginaryi". Using an f-string (formatted string literal) in Python, we can directly embed expressions inside a string literal:
  • The expression f'{a * c - b * d}+{a * d + c * b}i' converts the real and imaginary parts back into the required string format. The placeholders {} are replaced with the evaluated result of the expressions inside them.

In conclusion, the algorithm doesn't use complex data structures or patterns as the solution is a direct application of the formula for multiplying complex numbers. The parsing of strings and arithmetic operations are the main aspects of the solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's illustrate the solution approach with an example. Consider the two complex numbers represented by the strings num1 = "1+3i" and num2 = "2+4i". We want to multiply these two complex numbers as per the formula and return the result in the standard complex number format.

  1. Parsing the Input:

    • We split num1 and num2 by '+' to get the real and imaginary parts separately.
      • num1: "1+3i" -> real part 1 and imaginary part "3i".
      • num2: "2+4i" -> real part 2 and imaginary part "4i".
    • We remove the trailing 'i' from the imaginary parts.
      • Imaginary part of num1: "3i" -> "3".
      • Imaginary part of num2: "4i" -> "4".
    • Convert these strings into integers.
      • num1: real part a = 1, imaginary part b = 3.
      • num2: real part c = 2, imaginary part d = 4.

  2. Multiplying the Complex Numbers:

    • We use the distributive property: (a+bi)(c+di) = ac - bd + (ad + bc)i.
    • Multiply the real parts and subtract the product of the imaginary parts, since i^2 = -1: 1 * 2 - 3 * 4 = 2 - 12 = -10.
    • Add the product of the real part of one number with the imaginary part of the other: 1 * 4 + 3 * 2 = 4 + 6 = 10.
    • The resulting real part is -10 and the imaginary part is +10i.

  3. Formatting the Result:

    • We combine the real and imaginary parts into one string: "-10+10i".
    • This string follows the format "real+imaginaryi", which is our final output.

Therefore, multiplying num1 = "1+3i" and num2 = "2+4i" using the given approach yields the result "-10+10i". This demonstrates the implementation of the mathematical multiplication of complex numbers in the provided Python code, and how the parsed parts are used in the distributive property to get the desired output.

Solution Implementation

1class Solution:
2    def complexNumberMultiply(self, num1: str, num2: str) -> str:
3        # Split the real and imaginary parts of the first complex number 'num1'
4        real1, imaginary1 = map(int, num1[:-1].split('+'))
5        # Split the real and imaginary parts of the second complex number 'num2'
6        real2, imaginary2 = map(int, num2[:-1].split('+'))
7      
8        # Perform multiplication of two complex numbers using the formula:
9        # (a + bi) * (c + di) = (ac - bd) + (ad + bc)i
10        # Calculate the real part as (real1 * real2 - imaginary1 * imaginary2)
11        real_part = real1 * real2 - imaginary1 * imaginary2
12        # Calculate the imaginary part as (real1 * imaginary2 + real2 * imaginary1)
13        imaginary_part = real1 * imaginary2 + real2 * imaginary1
14      
15        # Return the result as a string in the format 'real_part+imaginary_parti'
16        result = f'{real_part}+{imaginary_part}i'
17        return result
18
1class Solution {
2
3    // Function to multiply two complex numbers given as strings
4    public String complexNumberMultiply(String num1, String num2) {
5        // Split each input string into real and imaginary parts
6        String[] complexOneComponents = num1.split("\\+|i");
7        String[] complexTwoComponents = num2.split("\\+|i");
8
9        // Parse the real and imaginary parts of the first complex number
10        int realPartOne = Integer.parseInt(complexOneComponents[0]);
11        int imaginaryPartOne = Integer.parseInt(complexOneComponents[1]);
12
13        // Parse the real and imaginary parts of the second complex number
14        int realPartTwo = Integer.parseInt(complexTwoComponents[0]);
15        int imaginaryPartTwo = Integer.parseInt(complexTwoComponents[1]);
16
17        // Apply the formula for multiplication of two complex numbers:
18        // (a + bi) * (c + di) = ac + adi + bci - bd = (ac - bd) + (ad + bc)i
19        int realResult = realPartOne * realPartTwo - imaginaryPartOne * imaginaryPartTwo;
20        int imaginaryResult = realPartOne * imaginaryPartTwo + imaginaryPartOne * realPartTwo;
21
22        // Construct the resulting complex number as a string and return it
23        return String.format("%d+%di", realResult, imaginaryResult);
24    }
25}
26
1#include <string>
2using namespace std;
3
4class Solution {
5public:
6    // Function to multiply two complex numbers given as strings
7    string complexNumberMultiply(string num1, string num2) {
8        // Initializing integer variables to contain real and imaginary parts
9        int real1, imag1, real2, imag2;
10      
11        // Parse the first complex number string and extract real and imaginary parts
12        sscanf(num1.c_str(), "%d+%di", &real1, &imag1);
13        // Parse the second complex number string and extract real and imaginary parts
14        sscanf(num2.c_str(), "%d+%di", &real2, &imag2);
15      
16        // Calculate the real part of the product of the two complex numbers
17        int realProduct = real1 * real2 - imag1 * imag2;
18        // Calculate the imaginary part of the product of the two complex numbers
19        int imagProduct = real1 * imag2 + real2 * imag1;
20      
21        // Construct the result string in the format "real+imagi"
22        string result = to_string(realProduct) + "+" + to_string(imagProduct) + "i";
23      
24        // Return the resulting string of the complex number multiplication
25        return result;
26    }
27};
28
1function complexNumberMultiply(num1: string, num2: string): string {
2    // Split the complex numbers into real and imaginary parts.
3    let partsOfNum1 = num1.split('+'),
4        partsOfNum2 = num2.split('+');
5  
6    // Parse the real parts of the complex numbers from the strings.
7    let realPart1 = Number(partsOfNum1[0]),
8        realPart2 = Number(partsOfNum2[0]);
9  
10    // Parse the imaginary parts of the complex numbers from the strings.
11    // The 'i' character is stripped from the end of the string.
12    let imaginaryPart1 = Number(partsOfNum1[1].slice(0, -1)),
13        imaginaryPart2 = Number(partsOfNum2[1].slice(0, -1));
14  
15    // Calculate the real part of the product by using the formula:
16    // (a + bi) * (c + di) = (ac - bd) + (ad + bc)i
17    // where a and b are the real and imaginary parts of the first complex number,
18    // and c and d are the same for the second number.
19    let productReal = realPart1 * realPart2 - imaginaryPart1 * imaginaryPart2;
20  
21    // Calculate the imaginary part of the product.
22    let productImaginary = realPart1 * imaginaryPart2 + realPart2 * imaginaryPart1;
23  
24    // Construct the string representation of the complex product.
25    return `${productReal}+${productImaginary}i`;
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

Time complexity

The time complexity of the code is O(1). This is because the code involves a constant number of operations regardless of the input size. Splitting the strings and performing arithmetic operations does not depend on the length of the input, as the format of the input is fixed (it represents a complex number).

Space complexity

The space complexity of the code is also O(1). Only a fixed number of additional variables are used for storing the parsed integers (a, b, c, d) and for constructing the final result. The storage required does not scale with input size, confirming that the space complexity is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫