Given three Integers num1, num2, and k, the task is to find the count of numbers between these two numbers such that the xor of the digit is exactly k.
Examples:
Input: num1 = 100, num2 = 500, k = 3
Output: 36
Explanation: 102 113 120 131 146 157 164 175 201 210 223 232 245 254 267 276 289 298 300 311 322 333 344 355 366 377 388 399 407 416 425 434 443 452 461 470Input: num1 = 10, num2 = 100, k = 2
Output: 7
Solving problem using linear Iteration:
- Initialize count with 0 to count the number of digits.
- Then, iterates through each number from num1 to num2.
- Inside the loop, it calculates the XOR of the digits of the current number.
- If xor = k then Increase the counter, count++.
- Return the value of the count.
Below is the Implementation of the above approach:
C++
// C++ code for the above approach:#include <iostream>#include <vector>using namespace std;// Function to count numbersint countNumbers(int num1, int num2, int k){ int count = 0; for (int num = num1; num <= num2; num++) { int currXOR = 0; int temp = num; while (temp > 0) { currXOR ^= (temp % 10); temp /= 10; } if (currXOR == k) { count++; } } return count;}// Drivers codeint main(){ int num1 = 100; int num2 = 500; int k = 3; // Function Call int result = countNumbers(num1, num2, k); cout << "Count of numbers = " << result << endl; return 0;} |
Java
// Java code for the above approach:import java.util.*;public class GFG { // Function to count numbers public static int countNumbers(int num1, int num2, int k) { int count = 0; for (int num = num1; num <= num2; num++) { int currXOR = 0; int temp = num; while (temp > 0) { currXOR ^= (temp % 10); temp /= 10; } if (currXOR == k) { count++; } } return count; } // Drivers code public static void main(String[] args) { int num1 = 100; int num2 = 500; int k = 3; // Function Call int result = countNumbers(num1, num2, k); System.out.println("Count of numbers = " + result); }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
# Function to count numbersdef countNumbers(num1, num2, k): count = 0 for num in range(num1, num2+1): # variable to store current xor currXOR = 0 temp = num while temp > 0: currXOR ^= (temp % 10) temp //= 10 if currXOR == k: count += 1 return count# Drivers codenum1 = 100num2 = 500k = 3result = countNumbers(num1, num2, k)print("Count of numbers =", result) |
Count of numbers = 36
Time complexity: O(N), where N is the difference.
Auxiliary Space: O(1) as constant space is used.
Solving problem Using Dynamic Programming:
In the dynamic programming approach, we use memoization to avoid redundant calculations and store the results in the dp array. By building up the solution incrementally, we can compute the count efficiently.
Steps for function: CountNumbers
- Check if the ind is equal to the size of the digits vector. If yes, return 1 if currXOR=k, else 0
- Check if the state for the ind, flag, and currXOR value has value. If yes, return the value.
- Determine the limit for the current digit based on the flag and the value at the current index.
- Initialize count=0
- Iterate from 0 to the lower limit.
- Update the newCurrXOR value by taking the XOR of currXOR and the digit.
- Recursively call the countNumbers function.
- Store the calculated count in the state, smaller flag, and currXOR value.
- Return the count value.
Steps for function: countNumbersWithXOR
- Convert num1 into a vector and store them in reverse order.
- Call the countNumbers function for the digits vector, with the initial index as 0, the smaller flag as false, the initial currXOR as 0, and the target XOR k.
- Store the count in count1.
- Do the same for finding count2
- Store the count in count2.
- Return count2 – count1
Below is the Implementation of the above approach:
C++
// C++ code for the above approach:#include <algorithm>#include <iostream>#include <vector>using namespace std;vector<vector<vector<int> > > dp;int countNumbers(vector<int>& digits, int index, bool smaller, int currXOR, int k){ if (index == digits.size()) { return (currXOR == k) ? 1 : 0; } if (dp[index][smaller][currXOR] != -1) { return dp[index][smaller][currXOR]; } int limit = (smaller || digits[index] < 1) ? 9 : digits[index]; int count = 0; for (int digit = 0; digit <= limit; digit++) { int newCurrXOR = currXOR ^ digit; count += countNumbers( digits, index + 1, smaller || (digit < digits[index]), newCurrXOR, k); } return dp[index][smaller][currXOR] = count;}int countNumbersWithXOR(int num1, int num2, int k){ vector<int> digits; int temp = num1; while (temp > 0) { digits.push_back(temp % 10); temp /= 10; } reverse(digits.begin(), digits.end()); dp.assign(digits.size(), vector<vector<int> >( 2, vector<int>(1024, -1))); int count1 = countNumbers(digits, 0, false, 0, k); digits.clear(); temp = num2; while (temp > 0) { digits.push_back(temp % 10); temp /= 10; } reverse(digits.begin(), digits.end()); dp.assign(digits.size(), vector<vector<int> >( 2, vector<int>(1024, -1))); int count2 = countNumbers(digits, 0, false, 0, k); return count2 - count1;}// C++ code for the above approach:int main(){ int num1 = 100; int num2 = 500; int k = 3; // Drivers code int result = countNumbersWithXOR(num1, num2, k); cout << "Count of numbers = " << result << endl; return 0;} |
Count of numbers = 36
Time complexity: O(10^N), where N is the number of digits in the larger of the two numbers (num1 and num2). The reason for the exponential time complexity is the recursive nature of the countNumbers function. It considers all possible combinations of digits for each position in the number, resulting in a branching factor of 10 at each level of recursion.
Auxiliary Space: O(log10(num2)). It depends on the number of digits in num2.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
