3209. Number of Subarrays With AND Value of K (Leetcode Hard)

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!
Problem: leetcode.com/problems/number-...
Twitch: / larryny
Discord: / discord
Instagram: / larrysomewhere
#leetcode #coding #programming

[@Algorithmist]

Were you able to get through the subarrays?

[@user-ym1nv1pw8i]

Thanks!

[@RichyRich18]

Hey Larry,
I'm new to LeetCode and have been learning and growing by watching your videos. They are really good compared to others on UA-cam .
i appreciate your approaches they are really good and are commendable.
I need some help understanding approaches better. I often spend a lot of time trying to grasp them. For example, I still feel that your solution will take O(n^2), but you mentioned it would take O(32*n). I implemented the same logic as yours using two for loops i know its O(n^2):
class Solution {
public:
long long countSubarrays(vector& nums, int k) {
int ad = INT_MAX;
int n = nums.size();
long long total = 0;
|for (int i = 0; i < n; i++) {
| long long cnt = 0;
| ad = INT_MAX;
| |for (int j = i; j < n; j++) {
| | ad &= nums[j];
| | if (ad < k) break;
| | if (ad == k) {
| | cnt++;
| | }
| |}
| total += cnt;
|}
|return total;
}
};
But it gives TLE, while yours does not.
the only suggestion is that, if you could give some more time to explain the logic behind your approaches, it will be grate help for me and others.
Thank you
Love from India🫡

[@Algorithmist]

Try the discord - it is easier to get feedback there!

[@Parth-y8o]

Great Solution Larry! What was the previous problem that you were talking about in the video, that helped you solve this?

[@Algorithmist]

It was this one - leetcode.com/problems/find-subarray-with-bitwise-or-closest-to-k/

[@user-cy6dv3ks3y]

I was too dumb to think about dp had done it in n*logn*32 time using binary search and was able to submit in java but failed in cpp. don't know why leetcode is weird!!