For those who are wondering, why I did not use DP, I could but it will be a very slow solution. Constraints are high. You can simple do a take and not take approach. Refer to the code below : class Solution { public: int solve(vector& candidates, int i, int totalAnd, int count) { if (i == candidates.size()) { return (totalAnd > 0) ? count : 0; }
// Take the current element int take = solve(candidates, i + 1, totalAnd & candidates[i], count + 1); // Not take pick the current element int not_take = solve(candidates, i + 1, totalAnd, count); // Return the maximum size of the subset with AND > 0 return max(take, not_take); } int largestCombination(vector& candidates) { return solve(candidates, 0, -1, 0); } }; Feel free to memoize it as well.
@@ShresthBhattacharjee-xz7ih This happens frequently with me, I guess the more you solve complex problem then you see it from only a Complex problem perspective. haha you're not the only one 🙌
class Solution { public: int largestCombination(vector& candidates) { int ans = INT_MIN; for(int i = 0;i < 32; i++){ int res = 0; for(int j = 0;j < candidates.size(); j++){ if (candidates[j] & (1
class Solution { public: int largestCombination(vector& candidates) { int n=*max_element(candidates.begin(),candidates.end()); n=log2(n)+1; int ans = 0; for(int i=0;i
MIK, I think I’ve started to develop a problem-solving approach like yours. Initially, I was looping over all 32 bits, but after checking the constraints, I reduced it to 24. 😊
Hi Mik, can you please tell me how you calculate bit representation of a number very quickly. 8/2=0 4/2=0 2/2=0 2/1 =1 {1000} I calculate like this in my head. Can you please tell me how you calculate very fast?
in approach 2, instead of shifting 1 to left i times and checking if AND result is not 0, we can also shift num to right by i and AND with 1, result will be always 0 or 1 , exactly what we need to add in curr counter, which removes inner if condition, making approach 2 clean and clear. public int largestCombination(int[] nums) { int ans = 0; for(int i = 0; i < 24; i++){ int curr = 0; for(int num : nums){ curr += (num >> i) & 1; } ans = Math.max(ans, curr); } return ans; }
Soution Based on Same Approach without extra space class Solution { public: int largestCombination(vector& candidates) { int max_count = 0; for (int i = 0; i > i) & 1; max_count = max(max_count, count); } return max_count; } }; class Solution { public: int largestCombination(vector& candidates) { int max_count = 0; for (int i = 0; i > i) & 1); }));
bhaiya pehele main apporoch nhi bana pata tha aur na hi code kar pata tha per dheere dheere maine practice karna suru ki ab mera apporch ban jata hai lekin code shi nhi hoo pata magar main consisty aur practice ke saaath dono cheezo ka accha kar lunga
The question is easy to program. But the intuition of thought process is hard to click in mind. If the logic comes then it is easy to program. sir, could you tell how we can get the logic to solve.
HEY Mik, if possible then please upload your bit masking notes on repo, I have checked there is no pdf notes of bit manipulation, please do it asap, it's a request 🙏🙏🙏
My solution: class Solution { public: int largestCombination(vector& candidates) { int ans = 0; for(int i=0; i 1; } ans = max(ans, cntOne); } return ans; } };
Okay so there is one issue that I am manipulating the array element, you can avoid it by changing the "if" condition to something like this (candidates[j] & (1
class Solution { public int largestCombination(int[] candidates) { int bit_count[] = new int[32]; int max = 0; for (int i = 0; i < 32; i++) { for (int j = 0; j < candidates.length; j++) { if (((candidates[j] & (1
My solution class Solution { public int largestCombination(int[] candidates) { int[]frequency= new int[28]; for(int i=0;i0){ if((i&1)==1){ frequency[position]++; } i>>=1; position++; } } }
class Solution { public int largestCombination(int[] candidates) { return solve(candidates,0,Integer.MAX_VALUE); } private int solve(int[] can,int index, int ans){ if(index>=can.length){ return 0; } int skip = 0; int take = 0; if((ans & can[index])==0){ skip = solve(can,index+1,ans); }else{ take = 1 + solve(can,index+1,ans&can[index]); } return Math.max(skip,take); } } I tried this but was not able to clear all testcases ... can you pls explain this
@@codestorywithMIK I was referring your fact video(hamming weight one), where you've used (num>>i) & 1, but this one is faster than that. I'm still unable to understand the concrete reason.
Guys my I'd got banned today without any reason, I donot use any tools for advance and I work with consistency and solve more than 400 question and 1700 + rating in contest . I grind for 10 months for this and at last what I get 😢😢😢😢😢, for me this is the biggest heartattack. Please help me 🙏🙏🙏
For those who are wondering, why I did not use DP, I could but it will be a very slow solution. Constraints are high. You can simple do a take and not take approach. Refer to the code below :
class Solution {
public:
int solve(vector& candidates, int i, int totalAnd, int count) {
if (i == candidates.size()) {
return (totalAnd > 0) ? count : 0;
}
// Take the current element
int take = solve(candidates, i + 1, totalAnd & candidates[i], count + 1);
// Not take pick the current element
int not_take = solve(candidates, i + 1, totalAnd, count);
// Return the maximum size of the subset with AND > 0
return max(take, not_take);
}
int largestCombination(vector& candidates) {
return solve(candidates, 0, -1, 0);
}
};
Feel free to memoize it as well.
tried it 29/80 tle, can anyone optimize it more?
class Solution {
public:
int solve(int i,int bit,vector &candidates,vector &dp){
if(i == candidates.size()) return 0;
if(dp[i][bit] != -1) return dp[i][bit];
int take = 0;
int setbit = 1
after watching your video for few minutes i realized that i overthought . ; ;
@@ShresthBhattacharjee-xz7ih This happens frequently with me, I guess the more you solve complex problem then you see it from only a Complex problem perspective. haha you're not the only one 🙌
@@ShresthBhattacharjee-xz7ih its overkill,same approach though
Interviewer Test Karega ❌ Interviewer cherega ✅
Maths wale part k lie thanks a lot. Itna hi depth knowledge me mujhe bhi study karna hai Sir.
Radhe radhe ❤
There is a reason why people call you legend. You put so much effort that even a beginner can understand tough things easily from you.
Video pause karke comment kar raha hu. 0:26 was 🔥🔥🔥🔥🔥
Best Motivation bhaiyya, Thank you so much .
class Solution {
public:
int largestCombination(vector& candidates) {
int ans = INT_MIN;
for(int i = 0;i < 32; i++){
int res = 0;
for(int j = 0;j < candidates.size(); j++){
if (candidates[j] & (1
thankyou sir for deep explanation especially for the last part of calculating bits.
Kya baat. Loved every second of the explanation
0:30 was much needed . Thanks
amazing explanation sir! and the motivation part was amazing . thank u sir
guruji aap dhanya ho.
Motivation and Maths wala part dekhkar maza agaya . thanks a lot
class Solution {
public:
int largestCombination(vector& candidates) {
int n=*max_element(candidates.begin(),candidates.end());
n=log2(n)+1;
int ans = 0;
for(int i=0;i
Perfect explanation
Great explanation sir
MIK, I think I’ve started to develop a problem-solving approach like yours. Initially, I was looping over all 32 bits, but after checking the constraints, I reduced it to 24. 😊
same
Thankyou bro for the Solution
Thank you for the motivation
please make a dedicated playlist for bit manipulation
class Solution {
public:
int largestCombination(vector& candidates) {
int ans = 0;
for(int i = 0; i < 32; i++) {
int temp = 0;
for(int j = 0; j < candidates.size(); j++)
if(candidates[j] & (1
Hi Mik, can you please tell me how you calculate bit representation of a number very quickly.
8/2=0 4/2=0 2/2=0 2/1 =1 {1000} I calculate like this in my head.
Can you please tell me how you calculate very fast?
Thank-You ❤
Sir i am able to solve the problem just because of your story and code concept. I have write the 2nd approach but i ran a loop to 31
awesome
First comment
🏅🏅
in approach 2, instead of shifting 1 to left i times and checking if AND result is not 0, we can also shift num to right by i and AND with 1, result will be always 0 or 1 , exactly what we need to add in curr counter, which removes inner if condition, making approach 2 clean and clear.
public int largestCombination(int[] nums) {
int ans = 0;
for(int i = 0; i < 24; i++){
int curr = 0;
for(int num : nums){
curr += (num >> i) & 1;
}
ans = Math.max(ans, curr);
}
return ans;
}
Bhai, can we check no. Of odd numbers directly kyuki usme bhi last bit 1 hogi saare ki ?
Thanks 🙂
Soution Based on Same Approach without extra space
class Solution {
public:
int largestCombination(vector& candidates) {
int max_count = 0;
for (int i = 0; i > i) & 1;
max_count = max(max_count, count);
}
return max_count;
}
};
class Solution {
public:
int largestCombination(vector& candidates) {
int max_count = 0;
for (int i = 0; i > i) & 1); }));
return max_count;
}
};
videos for OA please
Why not to solve this problem with recursion with pick and notPick way?
same, here is my solution which is giving tle
class Solution {
public:
int solve(int i, int currAnd, vector& candidates, vector& dp) {
if (i == candidates.size()) {
return 0;
}
if (currAnd != -1 && dp[i][currAnd] != -1) {
return dp[i][currAnd];
}
//take
int take = 0;
if (currAnd == -1 || (currAnd & candidates[i]) > 0) {
int newAnd = (currAnd == -1) ? candidates[i] : (currAnd & candidates[i]);
take = 1 + solve(i + 1, newAnd, candidates, dp);
}
//skip
int notTake = solve(i + 1, currAnd, candidates, dp);
int result = max(take, notTake);
if (currAnd != -1) {
dp[i][currAnd] = result;
}
return result;
}
int largestCombination(vector& candidates) {
int maxVal = *max_element(candidates.begin(), candidates.end());
vector dp(candidates.size(), vector(maxVal + 1, -1));
return solve(0, -1, candidates, dp);
}
};
constraints i think
bro n is 10 to power 5 it would give tle
please see my pinned comment
today's motivation hits harder than bit-manipulation
🔥🔥🔥🔥
bhaiya pehele main apporoch nhi bana pata tha aur na hi code kar pata tha per dheere dheere maine practice karna suru ki ab mera apporch ban jata hai lekin code shi nhi hoo pata magar main consisty aur practice ke saaath dono cheezo ka accha kar lunga
Great beast of luck
DP APPROACH
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
length = len(candidates)
self.memo = {}
return self.solve(0 , length , candidates , None)
def solve(self , idx , length , arr , prev):
if idx >= length:
if prev != 0 and prev != None:
return 0
return float('-inf')
if (idx , prev) in self.memo:
return self.memo[(idx , prev)]
if prev == None:
take = 1 + self.solve(idx+1 , length , arr , arr[idx])
else:
take = 1 + self.solve(idx+1 , length , arr , prev & arr[idx])
skip = self.solve(idx+1 , length , arr , prev)
self.memo[(idx , prev)] = max(take , skip)
return self.memo[(idx , prev)]
The question is easy to program. But the intuition of thought process is hard to click in mind. If the logic comes then it is easy to program.
sir, could you tell how we can get the logic to solve.
I did using backtracking but it is giving me TLE and only some test cases are passing
bhaiya decorder type question in bit manupulation wala yek baar karwa do
HEY Mik, if possible then please upload your bit masking notes on repo, I have checked there is no pdf notes of bit manipulation, please do it asap, it's a request 🙏🙏🙏
Already solved, still watching the video.
My solution:
class Solution {
public:
int largestCombination(vector& candidates) {
int ans = 0;
for(int i=0; i 1;
}
ans = max(ans, cntOne);
}
return ans;
}
};
Okay so there is one issue that I am manipulating the array element, you can avoid it by changing the "if" condition to something like this (candidates[j] & (1
class Solution {
public int largestCombination(int[] candidates) {
int bit_count[] = new int[32];
int max = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < candidates.length; j++) {
if (((candidates[j] & (1
My solution
class Solution {
public int largestCombination(int[] candidates) {
int[]frequency= new int[28];
for(int i=0;i0){
if((i&1)==1){
frequency[position]++;
}
i>>=1;
position++;
}
}
}
❤❤❤❤
class Solution {
public int largestCombination(int[] candidates) {
return solve(candidates,0,Integer.MAX_VALUE);
}
private int solve(int[] can,int index, int ans){
if(index>=can.length){
return 0;
}
int skip = 0;
int take = 0;
if((ans & can[index])==0){
skip = solve(can,index+1,ans);
}else{
take = 1 + solve(can,index+1,ans&can[index]);
}
return Math.max(skip,take);
}
}
I tried this but was not able to clear all testcases ... can you pls explain this
I'm not able to understand this clearly " (num & (1
When you write num & (1
Let me know if you guys need a short video on this.
Thanks
@@codestorywithMIK I was referring your fact video(hamming weight one), where you've used (num>>i) & 1, but this one is faster than that. I'm still unable to understand the concrete reason.
@@codestorywithMIK yes sir,we want the proper short for it,please
@@codestorywithMIKyes we want short for this trick
This is the region you become a millionaire with in next year, in terms of subscribers and financial both😂
bhaiya ye if(num &(1
When you write num & (1
why can't we use dp here??
my dp solution-
class Solution {
public:
int solve(int i,vector& candidates,int currAnd,vector&dp){
if(i==candidates.size()){
return 0;
}
if(dp[i]!=-1)return dp[i];
//take
int take=0,notTake=0;
if(currAnd==-1 || (currAnd&candidates[i])>0){
take=1+solve(i+1,candidates,currAnd&candidates[i],dp);
}
notTake=solve(i+1,candidates,currAnd,dp);
return dp[i]=max(take,notTake);
}
int largestCombination(vector& candidates) {
cout
please see my pinned comment
Guys my I'd got banned today without any reason, I donot use any tools for advance and I work with consistency and solve more than 400 question and 1700 + rating in contest . I grind for 10 months for this and at last what I get 😢😢😢😢😢, for me this is the biggest heartattack. Please help me 🙏🙏🙏
And it is permanent because due to a chrome extension, I got one month ban previously, But this time I donot have any extension and donot use any tool
@@BILLIONAIRE_BOY_HARSH which kind of extension???
@@BILLIONAIRE_BOY_HARSH can you tell if leetpush extension safe??
@@shivangisrivastava8732 i downloaded omega extension but after that I deleted it
Bcz it is not safe
bit manipulation nhi aata, seekhna hoga