# ☕ Dynamic Programming in the Real World

### I break down the time complexity to yesterday's solution. Also, an awesome article on the Seam Carving Algorithm for Image Resizing. Plus, an introduction to how the online payments ecosystem works.

Hey Guys,

# Tech Snippets

Content-Aware Image Resizing in JavaScript

Content Aware resizing arises when you want to change the height and width of your image without distorting the picture.

One algorithm that solves this is the

**Seam Carving Algorithm**, where you find the seam (continuous sequence of pixels) with the lowest contribution to the image content and then carve (remove) it.Finding the best seam is a computationally expensive task, and can be implemented efficiently using

**dynamic programming**.This is a

*fantastic*article that goes through the algorithm and approach.

A cool introduction to how online payments work

This is by Google Developers, so it specifically covers Google Pay but the concepts translate over to other payment platforms / digital wallets.

# Previous Solution

**As a refresher, here’s the last question**

Write a function that adds two numbers.

**You cannot use + or any arithmetic operators!**

**Solution**

I got a *TON* of questions around how to calculate the time complexity for yesterday’s solution.

**Therefore, I’ll dedicate today’s solution to break the time complexity calculation down further.**

To reiterate, here’s the Python 3 solution to the interview question.

```
def add(a, b):
if a == 0: return b
if b == 0: return a
# Addition Part
addition = a ^ b
# Carry Over Part
carryOver = (a & b) << 1
return add(addition, carryOver)
```

If you’d like to see the explanation for why this code works, you can read yesterday’s email.

So, in terms of calculating the time complexity of this function, we first have to answer the question of when the function will terminate.

We can simplify the base case a bit by removing `if a == 0: return b`

.

So, here’s the new Python function for add…

```
def add(a, b):
if b == 0: return a
# Addition Part
addition = a ^ b
# Carry Over Part
carryOver = (a & b) << 1
return add(addition, carryOver)
```

This function will still work, since if `a == 0`

and `b != 0`

then

the Addition Part will result in the

`addition`

variable being equal to`b`

since (`0 ^ n) = n`

.the Carry Over Part will result in the

`carryOver`

variable being equal to 0 since`(0 & n) << 1`

will always result in 0.

Therefore, if we call our function with `add(0, n)`

where n is any integer, the next function call will be `add(n,0)`

which will hit our base case.

So, our function’s base case is that it will terminate when `b == 0`

where our function is called with `add(a, b)`

.

Also, the recursive call in our function (last line) is `add(addition, carryOver)`

.

In other words, our function will terminate when the `carryOver`

is 0.

**So, we can bound our time complexity by calculating the maximum number of carry overs our function will have to do!**

So, what kind of input results in a large number of carry overs?

Well, if we look at Base 10, that would be an input like 999 + 999.

This would result in a carry over for every digit (3 carryovers).

It is impossible to have *more* carry overs than 3 since we only have 3 digits in our largest input.

Therefore, the number of carry overs is bounded by the number of digits in `max(a, b)`

.

We can calculate the number of digits in a number by taking it’s logarithm. The number of digits in `n`

is equal to `floor(log(n)) + 1`

.

Therefore, our time complexity is `log(max(a, b)`

.

*Please feel free to reply if you have any further questions!*

# Interview Question

You are given a binary tree in which each node contains an integer value. The integer value can be positive or negative.

Write a function that counts the number of paths in the binary tree that sum to a given value (the value will be provided as a function parameter).

The path does *not* need to start or end at the root or a leaf, but it must only go downwards.

*We’ll send a detailed solution tomorrow, so make sure you move our emails to primary, so you don’t miss them!*

**Gmail users**—move us to your primary inbox

**On your phone?**Hit the 3 dots at the top right corner, click "Move to" then "Primary"**On desktop?**Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

**Apple mail users**—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

## Create your profile

## Only paid subscribers can comment on this post

Log in## Check your email

For your security, we need to re-authenticate you.

Click the link we sent to , or click here to log in.