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: trueExample 2:
Input: [1,2,3,4]
Output: falseExample 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: trueOne 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. …
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"…
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 != j0 <= i, j < arr.lengtharr[i] == 2 * arr[j]
Example 1:
Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5. …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). …
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). …
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). …
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. …
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 : 100
There 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. …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. …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: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 =…
