Given integers L and R, the task for this problem is to find a number of integers in the range L to R whose sum of digits is divisible by bitwise XOR of digits. print the answer. ( L <= R <= 1018)
Note: Bitwise XOR sum zero never divides any other number.
Examples:
Input: L = 10, R = 15
Output: 4
Explanation:
- Number 10 : digitSum = 1 + 0 = 1, xorSum = 1 ^ 0 = 1, included in answer, 1 % 1 = 0
- Number 11: digitSum = 1 + 1 = 2, xorSum = 1 ^ 1 = 0, not included in answer since bitwise XOR sum is zero.
- Number 12: digitSum = 1 + 2 = 3, xorSum = 1 ^ 2 = 3, included in answer since 2 % 1 = 0
- Number 13: digitSum = 1 + 3 = 4, xorSum = 1 ^ 3 = 2, included in answer since 4 % 2 = 0
- Number 14: digitSum = 1 + 4 = 5, xorSum = 1 ^ 4 = 5, included in answer since 5 % 5 = 0
- Number 15: digitSum = 1 + 5 = 6, xorSum = 1 ^ 5 = 4, not included in answer since 6 % 4 != 0
10, 12, 13 and 14 are the numbers whose sum of digits are divisible by bitwise XOR sum of digits
Input: L = 1, R = 100
Output: 67
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(18N), Where N is the number of digits to be filled.
Auxiliary Space: O(1)
Efficient Approach: Dynamic programming can be used to solve this problem:
- dp[i][j][k][l] represents numbers in the range with i digits, j represents tight condition, k represents current sum and l represents bitwise XOR sum.
- It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly.
- So the idea is to store the value of each state. This can be done using by storing the value of a state and whenever the function is called, returning the stored value without computing again.
- First answer will be calculated for 0 to L – 1 and then calculated for 0 to R then the latter one is subtracted from the prior one to get answer for range [L, R].
Follow the steps below to solve the problem:
- Create a recursive function that takes four parameters i representing the position to be filled, j representing a tight condition, k representing the sum of digits, and finally l containing bitwise XOR sum of digits.
- Call the recursive function for choosing all digits from 0 to 9.
- Base case if the size of the digit is N and the sum is divisible by bitwise XOR sum return 1 else returns 0.
- Create a 4d array dp[20][2][180][16] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j][k][l].
- if the answer for a particular state is already computed then just return dp[i][j][k][l].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// dp table initialized with -1int dp[20][2][180][16];// recursive Function to find numbers// in the range L to R such that digit// sum is divisible by xor sum of digits.int recur(int i, int j, int k, int l, string& a){ // Base case if (i == a.size()) { // Sum of digits is divisible by // xor of digits return 1 if (l != 0 and k % l == 0) return 1; // Otherwise return 0 else return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k][l] if (dp[i][j][k][l] != -1) return dp[i][j][k][l]; // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int digit = 0; digit <= ((int)a[i] - 48); digit++) { // When digit is at max tight // condition remains even in // next state if (digit == ((int)a[i] - 48)) // Calling recursive function // for tight digit ans += recur(i + 1, 1, k + digit, l ^ digit, a); // Tight condition drops else // calling recursive function // for digits less than tight // condition digit ans += recur(i + 1, 0, k + digit, l ^ digit, a); } } // Tight condition false else { // iterating for all digits for (int digit = 0; digit <= 9; digit++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, 0, k + digit, l ^ digit, a); } } // save and return dp value return dp[i][j][k][l] = ans;}// Function to find numbers in the// range L to R such that digit sum// is divisible by xor sum of digits.int countInRange(int A, int B){ // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); A--; string L = to_string(A), R = to_string(B); // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to L int ans1 = recur(0, 1, 0, 0, L); // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to R int ans2 = recur(0, 1, 0, 0, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1;}// Driver Codeint main(){ // Input 1 int L = 10, R = 15; // Function Call cout << countInRange(L, R) << endl; // Input 2 int L1 = 1, R1 = 100; // Function Call cout << countInRange(L1, R1) << endl; return 0;} |
Java
// java code to implement the approachimport java.io.*;import java.util.*;class GFG { // recursive Function to find numbers // in the range L to R such that digit // sum is divisible by xor sum of digits. public static int recur(int[][][][] dp, int i, int j, int k, int l, StringBuilder a) { // Base Case if (i == a.length()) { // Sum of digits is divisible by // xor of digits return 1 if (l != 0 && k % l == 0) return 1; // Otherwise return 0 else return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k][l] if (dp[i][j][k][l] != -1) return dp[i][j][k][l]; // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int digit = 0; digit <= ((int)a.charAt(i) - 48); digit++) { // When digit is at max tight // condition remains even in // next state if (digit == ((int)a.charAt(i) - 48)) // Calling recursive function // for tight digit ans += recur(dp, i + 1, 1, k + digit, (l ^ digit), a); // Tight condition drops else // calling recursive function // for digits less than tight // condition digit ans += recur(dp, i + 1, 0, k + digit, (l ^ digit), a); } } // Tight condition false else { // iterating for all digits for (int digit = 0; digit <= 9; digit++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(dp, i + 1, 0, k + digit, (l ^ digit), a); } } // save and return dp value return dp[i][j][k][l] = ans; } // Function to find numbers in the // range L to R such that digit sum // is divisible by xor sum of digits. public static int countInRange(int[][][][] dp, int A, int B) { // Initializing dp array with - 1 for (int i = 0; i < 20; i++) { for (int j = 0; j < 2; j++) { for (int a = 0; a < 180; a++) { for (int b = 0; b < 16; b++) { dp[i][j][a][b] = -1; } } } } A--; StringBuilder L = new StringBuilder(Integer.toString(A)); StringBuilder R = new StringBuilder(Integer.toString(B)); // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to L int ans1 = recur(dp, 0, 1, 0, 0, L); // Initializing dp array with - 1 for (int i = 0; i < 20; i++) { for (int j = 0; j < 2; j++) { for (int a = 0; a < 180; a++) { for (int b = 0; b < 16; b++) { dp[i][j][a][b] = -1; } } } } // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to R int ans2 = recur(dp, 0, 1, 0, 0, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1; } // Driver Code public static void main(String[] args) { int[][][][] dp = new int[20][2][180][16]; // Input 1 int L = 10, R = 15; // Function Call System.out.println(countInRange(dp, L, R)); // Input 2 int L1 = 1, R1 = 100; // Function Call System.out.println(countInRange(dp, L1, R1)); }} |
Python3
# Python code to implement the approach # dp table initialized with -1dp = [[[[-1 for l in range(16)] for k in range(180)] for j in range(2)] for i in range(20)]# recursive Function to find numbers# in the range L to R such that digit# sum is divisible by xor sum of digits.def recur(i, j, k, l, a): # Base case if i == len(a): # Sum of digits is divisible by # xor of digits return 1 if l != 0 and k % l == 0: return 1 # Otherwise return 0 else: return 0 # If answer for current state is # already calculated then just # return dp[i][j][k][l] if dp[i][j][k][l] != -1: return dp[i][j][k][l] # Answer initialized with zero ans = 0 # Tight condition true if j == 1: # Iterating from 0 to max value # of tight condition for digit in range(0, int(a[i])+1): # When digit is at max tight # condition remains even in # next state if digit == int(a[i]): # Calling recursive function # for tight digit ans += recur(i + 1, 1, k + digit, l ^ digit, a) # Tight condition drops else: # calling recursive function # for digits less than tight # condition digit ans += recur(i + 1, 0, k + digit, l ^ digit, a) # Tight condition false else: # iterating for all digits for digit in range(0, 10): # Calling recursive function # for all digits from 0 to 9 ans += recur(i + 1, 0, k + digit, l ^ digit, a) # save and return dp value dp[i][j][k][l] = ans return ans # Function to find numbers in the# range L to R such that digit sum# is divisible by xor sum of digits.def countInRange(A, B): # Initializing dp array with - 1 for i in range(20): for j in range(2): for k in range(180): for l in range(16): dp[i][j][k][l] = -1 A -= 1 L = str(A) R = str(B) # Numbers with sum of digits divisible # by xor sum of digits # in the range 0 to L ans1 = recur(0, 1, 0, 0, L) # Initializing dp array with - 1 for i in range(20): for j in range(2): for k in range(180): for l in range(16): dp[i][j][k][l] = -1 # Numbers with sum of digits divisible # by xor sum of digits # in the range 0 to R ans2 = recur(0, 1, 0, 0, R) # Difference of ans2 and ans1 # will generate answer for # required range return ans2 - ans1 # Driver Code# Input 1L = 10R = 15# Function Callprint(countInRange(L, R))# Input 2L1 = 1R1 = 100# Function Callprint(countInRange(L1, R1))# This code is contributed by Prasad kandekar(prasad264) |
C#
// C# code to implement the approachusing System;using System.Text;public class GFG { // recursive Function to find numbers // in the range L to R such that digit // sum is divisible by xor sum of digits. public static int recur(int[, , , ] dp, int i, int j, int k, int l, StringBuilder a) { // Base Case if (i == a.Length) { // Sum of digits is divisible by // xor of digits return 1 if (l != 0 && k % l == 0) return 1; // Otherwise return 0 else return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k][l] if (dp[i, j, k, l] != -1) return dp[i, j, k, l]; // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int digit = 0; digit <= (a[i] - 48); digit++) { // When digit is at max tight // condition remains even in // next state if (digit == (a[i] - 48)) // Calling recursive function // for tight digit ans += recur(dp, i + 1, 1, k + digit, (l ^ digit), a); // Tight condition drops else // calling recursive function // for digits less than tight // condition digit ans += recur(dp, i + 1, 0, k + digit, (l ^ digit), a); } } // Tight condition false else { // iterating for all digits for (int digit = 0; digit <= 9; digit++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(dp, i + 1, 0, k + digit, (l ^ digit), a); } } // save and return dp value return dp[i, j, k, l] = ans; } // Function to find numbers in the // range L to R such that digit sum // is divisible by xor sum of digits. public static int countInRange(int[, , , ] dp, int A, int B) { // Initializing dp array with - 1 for (int i = 0; i < 20; i++) { for (int j = 0; j < 2; j++) { for (int a = 0; a < 180; a++) { for (int b = 0; b < 16; b++) { dp[i, j, a, b] = -1; } } } } A--; StringBuilder L = new StringBuilder(A.ToString()); StringBuilder R = new StringBuilder(B.ToString()); // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to L int ans1 = recur(dp, 0, 1, 0, 0, L); // Initializing dp array with - 1 for (int i = 0; i < 20; i++) { for (int j = 0; j < 2; j++) { for (int a = 0; a < 180; a++) { for (int b = 0; b < 16; b++) { dp[i, j, a, b] = -1; } } } } // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to R int ans2 = recur(dp, 0, 1, 0, 0, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1; } static public void Main() { // Code int[, , , ] dp = new int[20, 2, 180, 16]; // Input 1 int L = 10, R = 15; // Function Call Console.WriteLine(countInRange(dp, L, R)); // Input 2 int L1 = 1, R1 = 100; // Function Call Console.WriteLine(countInRange(dp, L1, R1)); }}// This code is contributed by lokesh. |
Javascript
// Javascript code to implement the approach// dp table initialized with -1let dp=new Array(20);for(let i=0; i<20; i++){ dp[i]=new Array(2); for(let j=0; j<2; j++) { dp[i][j]=new Array(180); for(let k=0; k<180; k++) dp[i][j][k]=new Array(16); }}// recursive Function to find numbers// in the range L to R such that digit// sum is divisible by xor sum of digits.function recur( i, j, k, l, a){ // Base case if (i == a.length) { // Sum of digits is divisible by // xor of digits return 1 if (l != 0 && k % l == 0) return 1; // Otherwise return 0 else return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k][l] if (dp[i][j][k][l] != -1) return dp[i][j][k][l]; // Answer initialized with zero let ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (let digit = 0; digit <= parseInt(a[i]); digit++) { // When digit is at max tight // condition remains even in // next state if (digit == parseInt(a[i])) // Calling recursive function // for tight digit ans += recur(i + 1, 1, k + digit, l ^ digit, a); // Tight condition drops else // calling recursive function // for digits less than tight // condition digit ans += recur(i + 1, 0, k + digit, l ^ digit, a); } } // Tight condition false else { // iterating for all digits for (let digit = 0; digit <= 9; digit++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, 0, k + digit, l ^ digit, a); } } // save and return dp value return dp[i][j][k][l] = ans;}// Function to find numbers in the// range L to R such that digit sum// is divisible by xor sum of digits.function countInRange( A, B){ // Initializing dp array with - 1 for(let i=0; i<20; i++) { for(let j=0; j<2; j++) { for(let k=0; k<180; k++) { for(let l=0; l<16; l++) dp[i][j][k][l]=-1; } } } A--; let L = A.toString(), R = B.toString(); // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to L let ans1 = recur(0, 1, 0, 0, L); // Initializing dp array with - 1 for(let i=0; i<20; i++) { for(let j=0; j<2; j++) { for(let k=0; k<180; k++) { for(let l=0; l<16; l++) dp[i][j][k][l]=-1; } } } // Numbers with sum of digits divisible // by xor sum of digits // in the range 0 to R let ans2 = recur(0, 1, 0, 0, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1;}// Driver Code// Input 1let L = 10, R = 15;// Function Calldocument.write(countInRange(L, R));// Input 2let L1 = 1, R1 = 100;// Function Calldocument.write(countInRange(L1, R1)); |
Output
4 67
Time Complexity: O(log(R) * M * N), where M is the maximum sum of digits and N is the maximum bitwise XOR sum of digits
Auxiliary Space: O(log(R) * M * N)
Another Approach:
- Define a function countInRange(L, R) that takes two integers L and R as input, and returns the count of numbers in the range L to R such that the digit sum is divisible by the XOR sum of digits.
- Define a nested function digitSums(n) that takes an integer n as input and returns two integers s and x, where s is the digit sum of n and x is the XOR sum of digits of n.
- Initialize a variable ans to 0.
- Iterate over all numbers in the range L to R using a for loop.
- For each number i, compute its digit sum and XOR sum of digits using the digitSums() function.
- Check if the XOR sum of digits is non-zero and the digit sum is divisible by the XOR sum of digits.
- If the conditions are satisfied, increment the ans variable by 1.
- Return the value of ans.
In short, the function iterates over all numbers in the range L to R, checks the digit sum and XOR sum of digits of each number, and increments a counter if the conditions are satisfied. Finally, it returns the count of such numbers.
C++
#include <iostream>using namespace std;// Function to compute digit sum and xor sum of digits of a numberpair<int, int> digitSums(int n) { int s = 0, x = 0; while (n > 0) { s += n % 10; x ^= n % 10; n /= 10; } return make_pair(s, x);}// Function to count numbers in the range L to R// such that digit sum is divisible by xor sum of digitsint countInRange(int L, int R) { int ans = 0; // Check all numbers in the range L to R for (int i = L; i <= R; i++) { pair<int, int> ds = digitSums(i); // Check if digit sum is divisible by xor sum of digits if (ds.second != 0 && ds.first % ds.second == 0) { ans++; } } return ans;}int main() { // Input 1 int L = 10; int R = 15; cout << countInRange(L, R) << endl; // Input 2 L = 1; R = 100; cout << countInRange(L, R) << endl; return 0;} |
Java
import java.util.*;public class GFG { // Function to compute digit sum and XOR sum of digits // of a number public static Pair<Integer, Integer> digitSums(int n) { int s = 0, x = 0; while (n > 0) { s += n % 10; x ^= n % 10; n /= 10; } return new Pair<>(s, x); } // Function to count numbers in the range L to R // such that digit sum is divisible by XOR sum of digits public static int countInRange(int L, int R) { int ans = 0; // Check all numbers in the range L to R for (int i = L; i <= R; i++) { Pair<Integer, Integer> ds = digitSums(i); // Check if digit sum is divisible by XOR sum of // digits if (ds.getValue() != 0 && ds.getKey() % ds.getValue() == 0) { ans++; } } return ans; } public static void main(String[] args) { // Input 1 int L = 10; int R = 15; System.out.println(countInRange(L, R)); // Input 2 L = 1; R = 100; System.out.println(countInRange(L, R)); } // Pair class for storing pair of values static class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } }}// This Code is Contributed by Shivam Tiwari |
Python3
# Function to count numbers in the range L to R # such that digit sum is divisible by xor sum of digits.def countInRange(L, R): # Function to compute digit sum and xor sum of digits of a number def digitSums(n): s, x = 0, 0 while n > 0: s += n % 10 x ^= n % 10 n //= 10 return s, x ans = 0 # Check all numbers in the range L to R for i in range(L, R+1): s, x = digitSums(i) # Check if digit sum is divisible by xor sum of digits if x != 0 and s % x == 0: ans += 1 return ans#Input 1L = 10R = 15print(countInRange(L, R)) #input 2L=1R=100print(countInRange(L, R)) #Code is contributed by siddharth aher |
C#
using System;public class Program{ // Function to compute digit sum and xor sum of digits of a number public static Tuple<int, int> DigitSums(int n) { int s = 0, x = 0; while (n > 0) { s += n % 10; x ^= n % 10; n /= 10; } return new Tuple<int, int>(s, x); } // Function to count numbers in the range L to R // such that digit sum is divisible by xor sum of digits public static int CountInRange(int L, int R) { int ans = 0; // Check all numbers in the range L to R for (int i = L; i <= R; i++) { Tuple<int, int> ds = DigitSums(i); // Check if digit sum is divisible by xor sum of digits if (ds.Item2 != 0 && ds.Item1 % ds.Item2 == 0) { ans++; } } return ans; } public static void Main() { // Input 1 int L = 10; int R = 15; Console.WriteLine(CountInRange(L, R)); // Input 2 L = 1; R = 100; Console.WriteLine(CountInRange(L, R)); // This code is contributed by Shivam Tiwari }} |
Javascript
// Function to calculate the sum of digits and XOR of digits of a numberfunction digitSums(n) { let s = 0, x = 0; while (n > 0) { s += n % 10; // Calculate the sum of digits x ^= n % 10; // Calculate the XOR of digits n = Math.floor(n / 10); // Remove the last digit from the number } return [s, x]; // Return the sum and XOR of digits as an array}// Function to count the numbers in the range [L, R] that satisfy the given conditionfunction countInRange(L, R) { let ans = 0; // Loop through each number in the range [L, R] for (let i = L; i <= R; i++) { const [sum, xor] = digitSums(i); // Calculate the sum and XOR of digits of the current number // Check if the XOR of digits is not zero and the sum is divisible by the XOR if (xor !== 0 && sum % xor === 0) { ans++; // Increment the count of numbers that satisfy the condition } } return ans; // Return the total count of numbers that satisfy the condition}// Input 1let L = 10;let R = 15;console.log(countInRange(L, R)); // Output: 1 (The only number in the range [10, 15] that satisfies the condition is 10)// Input 2L = 1;R = 100;console.log(countInRange(L, R)); // Output: 6 (The numbers in the range [1, 100] that satisfy the condition are 10, 12, 18, 21, 27, and 84)// This code is contributed by Shivam Tiwari |
Output
4 67
Time Complexity: The time complexity of the given Python code is O((R-L)*log(R)) because we are iterating over all numbers in the range [L,R] and for each number, we are computing the digit sum and xor sum of digits which takes log(R) time. The loop runs (R-L+1) times.
Auxiliary Space: The auxiliary space complexity of the given code is O(1) because we are using constant space for storing the variables s, x, and ans.
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
