# Contains Duplicate — Day 56(Python)

Today’s problem is an easy tagged question on leetcode. Let us look into the question.

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

`Input: [1,2,3,1]Output: true`

Example 2:

`Input: [1,2,3,4]Output: false`

Example 3:

`Input: [1,1,1,3,3,4,3,2,4,2]Output: true`

One of the easiest ways to solve this problem is by sorting. Using the sorting function, we can sort our array. After sorting, we can check if any of the adjacent elements are equal. …

# Fizz Buzz — Day 55(Python)

Today’s question is somewhat easy. I thought since we were learning dynamic programming for quite some time, It was good to have a change and learn something easy. Let us look into the question.

412. Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three, it should output “Fizz” instead of the number, and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

`n = 15,Return:[    "1",    "2",    "Fizz",    "4",    "Buzz",    "Fizz",    "7",    "8",    "Fizz",    "Buzz",    "11",    "Fizz",    "13",    "14",    "FizzBuzz"…`

# Check If N and It's Double Exist — Day 54(Python)

We have been working on dynamic programming for quite some time. Today let us work on some other type of problem. Today’s question is an easy tagged question in Leetcode.

1346. Check If N and Its Double Exist

Given an array `arr` of integers, check if there exist two integers `N` and `M` such that `N` is the double of `M` ( i.e. `N = 2 * M`).

More formally check if there exist two indices `i` and `j` such that :

• `i != j`
• `0 <= i, j < arr.length`
• `arr[i] == 2 * arr[j]`

Example 1:

`Input: arr = [10,2,5,3]Output: trueExplanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5. …`

# Longest Common Subsequence(Bottom-Up) — Day 53(Python)

Today’s article is the final part of the three-part series of Longest Common Subsequence(LCS) problem. You can follow this link if you need to understand how to solve the LCS problem using top-down.

1143. Longest Common Subsequence

Given two strings `text1` and `text2`, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). …

# Longest Common Subsequence (Top-Down)— Day 52(Python)

Today’s article is the second part of the three-part series of Longest Common Subsequence(LCS) problem. You can follow this link if you need to understand how to solve the LCS problem using recursion.

1143. Longest Common Subsequence

Given two strings `text1` and `text2`, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). …

# Longest Common Subsequence — Day 51(Python)

Today’s question is a famous question that is solved using Dynamic Programming. You will find many other questions that are variations of this question. Let us jump into the question without further ado. We will be solving this problem in a 3 part series. Today, we will be solving this problem using recursion.

1143. Longest Common Subsequence

Given two strings `text1` and `text2`, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). …

# Coin Change — Day 50(Python)

Today’s problem is a variation of the Unbounded Knapsack problem. We found the solution to the unbounded knapsack yesterday. In case you need a refresher, do follow this link. The question is pulled from Leetcode and is a medium tagged question. Let us look into the problem.

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`.

You may assume that you have an infinite number of each kind of coin. …

# Unbounded Knapsack — Day 49(Python)

Today’s problem is another variation of the Knapsack problem. In the earlier version of the knapsack problem, we had a limited number of items. In the current version of the problem, we have an unlimited number of item counts. Let’s jump into the question.

# Unbounded Knapsack (Repetition of items allowed)

Given a knapsack weight W and a set of n items with a certain value val[i] and weight wt[i], we need to calculate the maximum amount that could make up this quantity exactly. This is different from the classical Knapsack problem, here we are allowed to use an unlimited number of instances of an item.
Examples:

`Input : W = 100       val[]  = {1, 30}       wt[] = {1, 50}Output : 100There are many ways to fill knapsack.1) 2 instances of 50 unit weight item.2) 100 instances of 1 unit weight item.3) 1 instance of 50 unit weight item and 50   instances of 1 unit weight items. …`

# Target Sum — Day 48(Python)

Today’s problem is a variation of the Knapsack problem. The question is from leetcode and a “Medium” tagged question. Let us jump right into the question.

494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols `+` and `-`. For each integer, you should choose one from `+` and `-` as its new symbol.

Find out how many ways to assign symbols to make the sum of integers equal to target S.

Example 1:

`Input: nums is [1, 1, 1, 1, 1], S is 3. …`

# Minimum Sum Partition — Day 47(Python)

Today, we will be looking into another Dynamic Programming question. The problem statement is a variation of the Knapsack problem. Let us look into the problem statement. I used Aditya Verma’s video as a reference to solve this problem. I have included the link to his video at the end of the video.

# Partition a set into two subsets such that the difference of subset sums is minimum

Given an integer array arr of size N, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference

Example 1:

`Input: N = 4, arr[] = {1, 6, 11, 5} Output: 1Explanation: Subset1 = {1, 5, 6}, sum of Subset1 = 12 Subset2 = {11}, sum of Subset2 =…` 