IMMERSION CODES IN CP CLASS
Question :- 191. Number of 1 Bits
Level -->> Easy
Write a function that takes the binary representation of a positive integer and returns the number of
set bits
it has (also known as the Hamming weight).
Example 1:
Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.
Example 2:
Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.
Example 3:
Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
Constraints:
1 <= n <= 231 - 1
class Solution {
public int hammingWeight(int n) {
int count = 0;
int mask = 1;
for(int i=0;i<32;i++){
if((n&mask) != 0){
count++;
}
mask<<=1;
}
return count;
}
}
Question :- 389. Find the Difference
Level -->>Easy
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
Example 1:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.
Example 2:
Input: s = "", t = "y"
Output: "y"
Constraints:
0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lowercase English letters.
class Solution {
public char findTheDifference(String s, String t) {
char c =0;
for(int i=0;i<s.length();++i){
c^=s.charAt(i);
}
for(int i=0;i<t.length();++i){
c^=t.charAt(i);
}
return c;
}
}
Question :- 461. Hamming Distance
Level -->> Easy
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.
Example 1:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
Example 2:
Input: x = 3, y = 1
Output: 1
Constraints:
0 <= x, y <= 231 - 1
class Solution {
public int hammingDistance(int x, int y) {
int count = 0;
int xor = x^y;
int mask = 1;
for(int i=0;i<32;i++){
if((xor & mask) != 0){
count++;
}
mask<<=1;
}
return count;
}
}
Date : 18-06-2024
Question : 509. Fibonacci Number
Easy
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
Constraints:
0 <= n <= 30
1. By using Recursion
lass Solution {
public int fib(int n)
if(n<=1){
return n;
}
if(n==2){
return 1;
}
return fib(n-1)+fib(n-2);
}
}
Time Complexity ==>> 11-13ms
2. Memoization Chache {Top Down NAIVE Approch}
class Solution {
private int[] dp = new int[31];
public int fib(int n) {
if(n<=1){
return n;
}
if(n==2){
return 1;
}
memoize(n);
return dp[n];
}
public int memoize(int n){
if(dp[n] != 0){
return dp[n];
}
if(n<3){
return 1;
}
else{
dp[n] = memoize(n-1) + memoize(n-2);
}
return memoize(n);
}
}
3.Tabulation {Buttom up Approch}
class Solution {
public int fib(int n) {
if(n==0) return 0;
int[] dp = new int[n+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[dp.length-1];
}
}
4. Button up DP (Optimized) Approch
class Solution {
public int fib(int n) {
if(n <= 1){
return n;
}
if(n == 2){
return 1;
}
int curr = 0;
int prev1 = 1;
int prev2 = 1;
for(int i =3;i<=n;i++){
curr = prev1 + prev2;
prev1 = prev2;
prev2 = curr;
}
return curr;
}
}
70. Climbing Stairs
Easy
Hint
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
class Solution {
public int climbStairs(int n) {
if(n==1 ){
return 1;
}
int curr = 0;
int prev1 = 1;
int prev2 = 1;
for(int i =2;i<=n;i++){
curr = prev1 + prev2;
prev1 = prev2;
prev2 = curr;
}
return curr;
}
}
Date : 19-06-2024
Question :- 22. Generate
MediumGiven n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
: Backtraking Solution
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans,"",0,0,n);
return ans;
}
public void backtrack(List<String> ans, String cur,int open, int close,int max){
if(cur.length() == max*2){
ans.add(cur);
return;
}
if(open < max ){
backtrack(ans,cur+"(",open+1,close,max);
}
if(close < open){
backtrack(ans,cur+")",open,close+1,max);
}
}
}
Question : 78. Subsets
MediumGiven an integer array nums of unique elements, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.
Code Left:::::::::::::+========
Date : 20-06-2024
Question: 17. Letter Combinations of a Phone Number
Medium
Link ==>> Click HereGiven 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 = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
class Solution {
Map<String, String> phone = new HashMap<String, String>(){{
put("2","abc");
put("3","def");
put("4","ghi");
put("5","jkl");
put("6","mno");
put("7","pqrs");
put("8","tuv");
put("9","wxyz");
}};
List<String> output = new ArrayList<String>();
public void backtrack(String combination, String next_digits){
if(next_digits.length()==0){
output.add(combination);
}
else{
String digit = next_digits.substring(0,1);
String letters = phone.get(digit);
for(int i=0;i<letters.length();i++){
String letter = letters.substring(i,i+1);
backtrack(combination + letter,next_digits.substring(1));
}
}
}
public List<String> letterCombinations(String digits) {
if(digits.length() != 0){
backtrack("",digits);
}
return output;
}
}
last::::::::::::------------>>>>>>>
Comments
Post a Comment