Day 59 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/count-pairs-having-bitwise-xor-less-than-k/1

XOR Pairs less than K

Difficulty: Medium Accuracy: 70.84%

Given an array arr[] and an integer k, we need to count the number of pairs from the given array such that the Bitwise XOR of each pair is less than k.

Examples:
Input: arr = [1, 2, 3, 5], k = 5
Output: 4
Explanation: Bitwise XOR of all possible pairs that satisfy the given conditions are:
arr[0] ^ arr[1] = 1 ^ 2 = 3
arr[0] ^ arr[2] = 1 ^ 3 = 2
arr[0] ^ arr[3] = 1 ^ 5 = 4
arr[1] ^ arr[2] = 3 ^ 5 = 1
Therefore, the required output is 4.
Input: arr[] = [3, 5, 6, 8], k = 7
Output: 3
Explnation: Bitwise XOR of all possible pairs that satisfy the given conditions are:
arr[0] ^ arr[1] = 6
arr[0] ^ arr[2] = 5
arr[1] ^ arr[2] = 3
Therefore, the required output is 3.
Constraints:
1 ≤ arr.size(), k ≤ 5*104
1 ≤ arr[i] ≤ 5*104

Solution:
class Solution:
def cntPairs(self, arr, k):
class Node:
def init(self):
self.c = [None, None]
self.cnt = 0

    def insert(root, x):
        cur = root
        for i in range(15, -1, -1):
            b = (x >> i) & 1
            if not cur.c[b]:
                cur.c[b] = Node()
            cur = cur.c[b]
            cur.cnt += 1

    def query(root, x, k):
        cur = root
        ans = 0
        for i in range(15, -1, -1):
            if not cur:
                break
            xb = (x >> i) & 1
            kb = (k >> i) & 1
            if kb == 1:
                if cur.c[xb]:
                    ans += cur.c[xb].cnt
                cur = cur.c[1 - xb]
            else:
                cur = cur.c[xb]
        return ans

    root = Node()
    res = 0
    for x in arr:
        res += query(root, x, k)
        insert(root, x)
    return res