Problems
December 3, 2022
Number of subarrays with lcm equal to k
We will take every possible subarray of the input array and calculate the lcm of the subarray. If the lcm is equal to k, we will increment the count of such subarrays. Time complexity:...
ReadDecember 2, 2022
Previous permutation with one swap
We will iterate through the array from the end. We will keep track of the index of the first element that is smaller than the previous element. We will then iterate through the array from the end. We...
ReadDecember 2, 2022
Minimum cost to reach city with discounts
We will use Dijkstra's algorithm to solve this problem. We will create a graph with the cities as the nodes and the edges as the roads. We will then use Dijkstra's algorithm to find the shortest path...
ReadDecember 2, 2022
Nth digit
Integers can be divided into groups 1-9, 10-99, 100-999, 1000-9999, etc. Every number in the i-th group has i digits. First we want to find the group which contains the number where does the digit...
ReadDecember 2, 2022
Determine if two strings are close
We will check if the two strings are equal. If they are not equal, then we will return false. If they are equal, then we will check if the frequency of each character in the two strings are equal. If...
ReadDecember 2, 2022
Connecting cities with minimum cost
We will use Kruskal's algorithm to solve this problem. We will sort the edges in ascending order of their weights. Then we will use Union Find data structure to construct the graph. We will then...
ReadDecember 2, 2022
Search in a sorted array of unknown size
We will use binary search to find the index of the target. We will start with the index 1. If the element at the index is smaller than the target, then we will double the index. If the element at the...
ReadDecember 1, 2022
Path sum IV
We will convert the given array into a tree using Node objects. Afterwards, for each path from root to leaf, we can add the sum of that path to our answer. There are two steps, the tree...
ReadDecember 1, 2022
Determine if string halves are alike
We will itrerate over the string, for first half we increase the count and for second half we decrease the count. At the end if the count is 0, then the string halves are alike. Time complexity:...
ReadDecember 1, 2022
Majority element II
We will count the frequency of each element in the array and return the elements whose frequency is greater than n//3
. We will use a hashmap to store the frequency of each element, and a...