Longest Substring Without Repeating Characters

Problem Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/

What to Do:

• Go to folder: "\CP\LeetCode\Longest Substring Without Repeating Characters"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".cpp" in this issue.

Problem:

Given a string s, find the length of the longest substring without repeating characters.

Constraints

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Template Function :

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};

Bitwise Tuples

Problem Code: BITTUP

LINK : https://www.codechef.com/JUNE21B/problems/BITTUP

What to Do?

• Go to folder: "\CP\LeetCode\Longest Substring Without Repeating Characters"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".py" in this issue.

Problem:

Chef has two numbers N and M. Help Chef to find number of integer N-tuples (A1,A2,…,AN) such that 0≤A1,A2,…,AN≤2^M−1 and A1&A2&…&AN=0, where & denotes the bitwise AND operator.

Since the number of tuples can be large, output it modulo 10^9+7.

Input:

• The first line contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains two integers N and M

Output:

For each test case, output in a single line the answer to the problem modulo 10^9+7

Constraints:

• 1≤T≤10^5
• 1≤N,M≤10^6

Sample Input 1:

4
1 2
2 2
4 2
8 4

Sample Output1:

1
9
225
228250597

Explamnation:

• Test Case 1 : The only possible tuple is (0).
• test Case 2 : The tuples are (0,0), (0,1), (0,2), (0,3), (1,0), (2,0), (3,0), (1,2), (2,1).

Partition to K Equal Sum Subsets

Problem Link: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

What to Do:

• Go to folder: ".\CP\LeetCode\Partition to K Equal Sum Subsets"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".py" in this issue.

Problem:

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Constraints

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 10^4
• The frequency of each element is in the range [1, 4].

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

Template Function :

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        

Minimum Dual Area

Problem Code: DAREA

Problem Link: https://www.codechef.com/JUNE21B/problems/DAREA

What to Do:

• Go to folder: "./CP/CodeChef/DAREA"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".cpp" in this issue.

Problem:

Given N points in a 2D space, find the minimum sum of areas of rectangles required to cover all the points given that we can use at most 2 non-overlapping rectangles whose sides can touch. The rectangles must be axis-aligned, meaning the sides are vertical and horizontal.

Input:

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• Each test case contains N+1 lines of input.
• The first line contains a single integer N, the number of points.
• The next N lines each contain two integers xi, yi, the coordinates of the i-th point.

Note: Points need not be distinct.

Output

• For each test case, output in a single line the answer to the problem.

Constraints

• 1≤T≤105
• 1≤N≤105
• 0≤xi,yi≤109
• The sum of N over all test cases is at most 105.

Sample Input 1 :

3
1
100 100
4
1 100
100 100
100 1
1 1
5
1 100
100 100
100 1
1 1
50 50

Sample Output 1 :

0
0
4851

Explanation :

• Case 1: Since there is only one point, the minimum area of a rectangle to cover this point is 0.
• Case 2: We can have rectangles as 2 opposite sides of the square. Since the width of the rectangles is 0, the total area is also 0.
  
• Case 3: The optimal solution is with the rectangles having endpoints {(1,1),(100,1),(1,50),(100,50)} and {(1,100),(1,100),(100,100),(100,100)}. Therefore the total area is 49⋅99+0⋅99=4851
  

Partition to K Equal Sum Subsets

Problem Link: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

What to Do:

• Go to folder: ".\CP\LeetCode\Partition to K Equal Sum Subsets"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".cpp" in this issue.

Problem:

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Constraints

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 10^4
• The frequency of each element is in the range [1, 4].

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

Template Function :

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        
    }
};

Edit ./CD/README.md

Edit it according to how many problems are solved till now

Template:

CodeChef

• DAREA

• Link : https://www.codechef.com/JUNE21B/problems/DAREA

  • Language:

    • C++
    • Python
    • Java

• ABC

• Link : https://www.codechef.com/JUNE21B/problems/DAREA

  • Language:

    • C++
    • Python
    • Java

LeetCode

• DAREA

• Link : https://www.codechef.com/JUNE21B/problems/DAREA

  • Language:

    • C++
    • Python
    • Java

• ABC

• Link : https://www.codechef.com/JUNE21B/problems/DAREA

  • Language:

    • C++
    • Python
    • Java

What to Do?

Location

• Go to folder /CP/LeetCode/Container With Most Water/

File name

• Take your GitHub username id like "hrithik339", "hacker-boy", etc or anything which you have.
• Then add programming language extension after this (link for C++ add .cpp and for python add.py)
• Only files with the correct file name will be accepted

Problem - Container With Most Water

Link : https://leetcode.com/problems/container-with-most-water/

Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Exmple 2

Input: height = [1,1]
Output: 1

Constrains

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 10

Minimum Dual Area

Problem Code: DAREA

Problem Link: https://www.codechef.com/JUNE21B/problems/DAREA

What to Do:

• Go to folder: "./CP/CodeChef/DAREA"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".py" in this issue.

Problem:

Given N points in a 2D space, find the minimum sum of areas of rectangles required to cover all the points given that we can use at most 2 non-overlapping rectangles whose sides can touch. The rectangles must be axis-aligned, meaning the sides are vertical and horizontal.

Input:

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• Each test case contains N+1 lines of input.
• The first line contains a single integer N, the number of points.
• The next N lines each contain two integers xi, yi, the coordinates of the i-th point.

Note: Points need not be distinct.

Output

• For each test case, output in a single line the answer to the problem.

Constraints

• 1≤T≤105
• 1≤N≤105
• 0≤xi,yi≤109
• The sum of N over all test cases is at most 105.

Sample Input 1 :

3
1
100 100
4
1 100
100 100
100 1
1 1
5
1 100
100 100
100 1
1 1
50 50

Sample Output 1 :

0
0
4851

Explanation :

• Case 1: Since there is only one point, the minimum area of a rectangle to cover this point is 0.
• Case 2: We can have rectangles as 2 opposite sides of the square. Since the width of the rectangles is 0, the total area is also 0.
  
• Case 3: The optimal solution is with the rectangles having endpoints {(1,1),(100,1),(1,50),(100,50)} and {(1,100),(1,100),(100,100),(100,100)}. Therefore the total area is 49⋅99+0⋅99=4851
  

What to Do?

Location

• Go to folder /CP/LeetCode/Letter Combination of a Phone Number

File name

• Take your GitHub username id like "hrithik339", "hacker-boy", etc or anything which you have.
• Then add programming language extension after this (link for C++ add .cpp and for python add.py)
• Only files with the correct file name will be accepted

Letter Combinations of a Phone Number

Link : https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Problem Statement:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "2"
Output: ["a","b","c"]

Example 3:

Input: digits = ""
Output: []

Constrain:

Constraints:

• 0<= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

What to Do?

Location

• Go to folder CP/LeetCode/Longest Palindromic Substring

File name

• Take your GitHub username id like "hrithik339", "hacker-boy", etc or anything which you have.
• Then add a programming language extension after this (link for C++ add .cpp and for python add.py)
  Only files with the correct file name will be accepted

Problem - Longest Palindromic Substring

Link : https://leetcode.com/problems/longest-palindromic-substring/

Problem

Given a string s, return the longest palindromic substring in s.

A string is called a palindrome string if the reverse of that string is the same as the original string.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

What to Do?

Location

• Go to folder /CP/LeetCode/Regular Expression Matching

File name

• Take your GitHub username id like "hrithik339", "hacker-boy", etc or anything which you have.
• Then add programming language extension after this (link for C++ add .cpp and for python add.py)
• Only files with the correct file name will be accepted

Problem - Regular Expression Matching

Link: https://leetcode.com/problems/regular-expression-matching/

Problem

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.​​​​
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints

• 1 <= s.length <= 20
• 1 <= p.length <= 30
• p contains only lowercase English letters, '.', and '*'.
• s contains only lowercase English letters.
• It is guaranteed for each appearance of the character '', there will be a previous valid character to match.

Count Complete Tree Nodes

Problem Link: https://leetcode.com/problems/count-complete-tree-nodes/

What to Do?

• Go to folder: "/CP/LeetCode/Count Complete Tree Nodes/"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".py" in this issue.

Problem:

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Constraints

The number of nodes in the tree is in the range [0, 5 * 104].
0 <= Node.val <= 5 * 104
The tree is guaranteed to be complete.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Template Function :

• C++:

class Solution {
public:
    int countNodes(TreeNode* root) {
        
    }
};

What to Do?

Location

• Go to folder /CP/LeetCode/Integer To Roman

File name

• Take your GitHub username id like "hrithik339", "hacker-boy", etc or anything which you have.
• Then add programming language extension after this (link for C++ add .cpp and for python add.py)
• Only files with the correct file name will be accepted

Integer to Roman

Link : https://leetcode.com/problems/integer-to-roman/

Problem Statement

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Shortest Route

Problem Code: SHROUTE

Problem Link: https://www.codechef.com/JUNE21B/problems/SHROUTE

What to Do:

• Go to folder: ".\CP\CodeChef\SHROUTE"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".cpp" in this issue.

Problem:

There are N cities in Chefland numbered from 1 to N and every city has a railway station. Some cities have a train and each city has at most one train originating from it. The trains are represented by an array A, where Ai=0 means the i-th city doesn't have any train originating from it, Ai=1 means the train originating from the i-th city is moving right (to a higher numbered city), and Ai=2 means the train originating from the i-th city is moving left (to a lower numbered city).

Each train keeps on going forever in its direction and takes 1 minute to travel from the current station to the next one. There is a special station at city 1 which lets travellers instantaneously teleport to any other station that currently has a train. Teleportation and getting on a train once in the city both take 0 minutes and all trains start at time 0.

There are M travellers at city 1, and the i-th traveller has destination city Bi. They ask Chef to guide them to teleport to a particular station from which they can catch a train to go to their destination in the least time possible. In case it's not possible for a person to reach his destination, print −1.

Note: The input and output of this problem are large, so prefer using fast input/output methods.

Input:

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• Each test case contains three lines of input.
• The first line contains two integers N, M
• The second line contains N integers A1,A2,…,AN.
• The third line contains M integers B1,B2,…,BM

Output

• For each test case, output M space-separated integers C1,C2,…,CM, where Ci is the minimum time required by the i-th traveller to reach his destination and if the i-th traveller can't reach his destination, Ci=−1.

Constraints

• 1≤N,M≤10^5
• 0≤Ai≤2
• 1≤Bi≤N
• The sum of N over all test cases is at most 10^6
• The sum of M over all test cases is at most 10^6

Sample Input 1 :

3
5 1
1 0 0 0 0
5
5 1
1 0 0 0 2
4
5 2
2 0 0 0 1
3 1

Sample Output 1 :

4
1
-1 0

Explanation :

• Case 1: The only person takes the train from station 1 and hence takes |5−1|=4 minutes to reach his destination.
• Case 2: The only person takes the train from station 5 and hence takes |5−4|=1 minute to reach his destination.
• Case 3: Since no train passes station 3, it's impossible for the first person to reach his destination and since the second person is already at station 1, it takes him 0 minutes to reach his destination.

Please put a hacktoberfest-accepted label on my commit of Code Code to store informations of employees is added using structure #119.

I want to add the number system conversion code like binary to decimal,octal and hexadecimal and vice versa code in cpp language.

What to Do?

Location

• Go to folder /CP/LeetCode/4SUM

File name

• Take your GitHub username id like "hrithik339", "hacker-boy", etc or anything which you have.
• Then add programming language extension after this (link for C++ add .cpp and for python add.py)
• Only files with the correct file name will be accepted

4Sum

Link : https://leetcode.com/problems/4sum/

Problem Statement:

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

Bitwise Tuples

Problem Code: BITTUP

LINK : https://www.codechef.com/JUNE21B/problems/BITTUP

What to Do?

• Go to folder: "\CP\LeetCode\Longest Substring Without Repeating Characters"
• Take your GitHUB username id like "hrithik339", "hacker-boy", etc or anything which you have.
• File extension = ".cpp" in this issue.

Problem:

Chef has two numbers N and M. Help Chef to find number of integer N-tuples (A1,A2,…,AN) such that 0≤A1,A2,…,AN≤2^M−1 and A1&A2&…&AN=0, where & denotes the bitwise AND operator.

Since the number of tuples can be large, output it modulo 10^9+7.

Input:

• The first line contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains two integers N and M

Output:

For each test case, output in a single line the answer to the problem modulo 10^9+7

Constraints:

• 1≤T≤10^5
• 1≤N,M≤10^6

Sample Input 1:

4
1 2
2 2
4 2
8 4

Sample Output1:

1
9
225
228250597

Explamnation:

• Test Case 1 : The only possible tuple is (0).
• test Case 2 : The tuples are (0,0), (0,1), (0,2), (0,3), (1,0), (2,0), (3,0), (1,2), (2,1).