Given an integer N, the task is to find the total count of N-Digit numbers such that the Bitwise XOR of the digits of the numbers is a single digit.
Examples:
Input: N = 1
Output: 9
Explanation:
1, 2, 3, 4, 5, 6, 7, 8, 9 are the numbers.Input: N = 2
Output: 66
Explanation:
There are 66 such 2-digit numbers whose Xor of digits is a single digit number.
Approach: The naive approach will be to iterate over all the N-digit numbers and check if the Bitwise XOR of all the digits of the number is a single digit. If yes then include this in the count, otherwise, check for the next number.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find count of N-digit // numbers with single digit XOR void countNums(int N) { // Range of numbers int l = (int)pow(10, N - 1); int r = (int)pow(10, N) - 1; int count = 0; for(int i = l; i <= r; i++) { int xorr = 0, temp = i; // Calculate XOR of digits while (temp > 0) { xorr = xorr ^ (temp % 10); temp /= 10; } // If XOR <= 9, // then increment count if (xorr <= 9) count++; } // Print the count cout << count; } // Driver Code int main(){ // Given number int N = 2; // Function call countNums(N); } // This code is contributed by code_hunt |
Java
// Java program for the above approach class GFG { // Function to find count of N-digit // numbers with single digit XOR public static void countNums(int N) { // Range of numbers int l = (int)Math.pow(10, N - 1), r = (int)Math.pow(10, N) - 1; int count = 0; for (int i = l; i <= r; i++) { int xor = 0, temp = i; // Calculate XOR of digits while (temp > 0) { xor = xor ^ (temp % 10); temp /= 10; } // If XOR <= 9, // then increment count if (xor <= 9) count++; } // Print the count System.out.println(count); } // Driver Code public static void main(String[] args) { // Given Number int N = 2; // Function Call countNums(N); } } |
Python3
# Python3 program for the above approach # Function to find count of N-digit # numbers with single digit XOR def countNums(N): # Range of numbers l = pow(10, N - 1) r = pow(10, N) - 1 count = 0 for i in range(l, r + 1): xorr = 0 temp = i # Calculate XOR of digits while (temp > 0): xorr = xorr ^ (temp % 10) temp //= 10 # If XOR <= 9, # then increment count if (xorr <= 9): count += 1 # Print the count print(count)# Driver Code # Given number N = 2# Function call countNums(N) # This code is contributed by code_hunt |
C#
// C# program for the above approach using System;class GFG{ // Function to find count of N-digit // numbers with single digit XOR public static void countNums(int N) { // Range of numbers int l = (int)Math.Pow(10, N - 1), r = (int)Math.Pow(10, N) - 1; int count = 0; for(int i = l; i <= r; i++) { int xor = 0, temp = i; // Calculate XOR of digits while (temp > 0) { xor = xor ^ (temp % 10); temp /= 10; } // If XOR <= 9, // then increment count if (xor <= 9) count++; } // Print the count Console.WriteLine(count); } // Driver Code public static void Main() { // Given number int N = 2; // Function call countNums(N); } }// This code is contributed by code_hunt |
Javascript
<script>// JavaScript program for the above approach // Function to find count of N-digit // numbers with single digit XOR function countNums(N) { // Range of numbers let l = Math.floor(Math.pow(10, N - 1)); let r = Math.floor(Math.pow(10, N)) - 1; let count = 0; for(let i = l; i <= r; i++) { let xorr = 0, temp = i; // Calculate XOR of digits while (temp > 0) { xorr = xorr ^ (temp % 10); temp = Math.floor(temp / 10); } // If XOR <= 9, // then increment count if (xorr <= 9) count++; } // Print the count document.write(count); } // Driver Code // Given number let N = 2; // Function call countNums(N); // This code is contributed by Surbhi Tyagi.</script> |
Output:
66
Time Complexity: O(N*10N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use Dynamic Programming. Observe that the maximum Bitwise XOR that can be obtained is 15.
- Create a table dp[][], where dp[i][j] stores the count of i-digit numbers such that their XOR is j.
- Initialize the dp[][] for i = 1 and for each i from 2 to N iterate for every digit j from 0 to 9.
- For every possible previous XOR k from 0 to 15, find the value by doing XOR of previous XOR k and the digit j, and increment the count of dp[i][value] by dp[i – 1][k].
- The total count of N-digit numbers with a single-digit XOR can be found by summing the dp[N][j] where j ranges from 0 to 9.
Below is the implementation of the above approach:
C++
// C++ program for // the above approach #include<bits/stdc++.h>using namespace std;// Function to find // count of N-digit // numbers with single // digit XOR void countNums(int N) { // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j int dp[N][16]; memset(dp, 0, sizeof(dp[0][0]) * N * 16); // For 1-9 store the value for (int i = 1; i <= 9; i++) dp[0][i] = 1; // Iterate till N for (int i = 1; i < N; i++) { for (int j = 0; j < 10; j++) { for (int k = 0; k < 16; k++) { // Calculate XOR int xo = j ^ k; // Store in DP table dp[i][xo] += dp[i - 1][k]; } } } // Initialize count int count = 0; for (int i = 0; i < 10; i++) count += dp[N - 1][i]; // Print the answer cout << (count) << endl; } // Driver Code int main() { // Given number N int N = 1; // Function Call countNums(N); } // This code is contributed by Chitranayal |
Java
// Java program for the above approach class GFG { // Function to find count of N-digit // numbers with single digit XOR public static void countNums(int N) { // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j int dp[][] = new int[N][16]; // For 1-9 store the value for (int i = 1; i <= 9; i++) dp[0][i] = 1; // Iterate till N for (int i = 1; i < N; i++) { for (int j = 0; j < 10; j++) { for (int k = 0; k < 16; k++) { // Calculate XOR int xor = j ^ k; // Store in DP table dp[i][xor] += dp[i - 1][k]; } } } // Initialize count int count = 0; for (int i = 0; i < 10; i++) count += dp[N - 1][i]; // Print the answer System.out.println(count); } // Driver Code public static void main(String[] args) { // Given number N int N = 1; // Function Call countNums(N); } } |
Python3
# Python3 program for the# above approach# Function to find count of # N-digit numbers with single# digit XORdef countNums(N): # dp[i][j] stores the number # of i-digit numbers with # XOR equal to j dp = [[0 for i in range(16)] for j in range(N)]; # For 1-9 store the value for i in range(1, 10): dp[0][i] = 1; # Iterate till N for i in range(1, N): for j in range(0, 10): for k in range(0, 16): # Calculate XOR xor = j ^ k; # Store in DP table dp[i][xor] += dp[i - 1][k]; # Initialize count count = 0; for i in range(0, 10): count += dp[N - 1][i]; # Print answer print(count);# Driver Codeif __name__ == '__main__': # Given number N N = 1; # Function Call countNums(N);# This code is contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;class GFG{// Function to find count of N-digit// numbers with single digit XORpublic static void countNums(int N){ // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j int [,]dp = new int[N, 16]; // For 1-9 store the value for(int i = 1; i <= 9; i++) dp[0, i] = 1; // Iterate till N for(int i = 1; i < N; i++) { for(int j = 0; j < 10; j++) { for (int k = 0; k < 16; k++) { // Calculate XOR int xor = j ^ k; // Store in DP table dp[i, xor] += dp[i - 1, k]; } } } // Initialize count int count = 0; for(int i = 0; i < 10; i++) count += dp[N - 1, i]; // Print the answer Console.Write(count);}// Driver Codepublic static void Main(string[] args){ // Given number N int N = 1; // Function call countNums(N);}}// This code is contributed by rutvik_56 |
Javascript
<script>// javascript program for the above approach // Function to find count of N-digit // numbers with single digit XOR function countNums(N) { // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j var dp = Array(N); for(var i =0;i<N;i++) dp[i] = Array(16).fill(0); // For 1-9 store the value for (i = 1; i <= 9; i++) dp[0][i] = 1; // Iterate till N for (i = 1; i < N; i++) { for (j = 0; j < 10; j++) { for (k = 0; k < 16; k++) { // Calculate XOR var xor = j ^ k; // Store in DP table dp[i][xor] += dp[i - 1][k]; } } } // Initialize count var count = 0; for (i = 0; i < 10; i++) count += dp[N - 1][i]; // Print the answer document.write(count); } // Driver Code // Given number N var N = 1; // Function Call countNums(N);// This code contributed by umadevi9616 </script> |
Output:
9
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Space optimization
In previous approach we use a 2d Dp of size N+1*16 but the computation of current value is only depend upon the previous and current row of DP. So to optimize the space we can use the single 1D array of size 16 to store the computations of subproblems
Implementation Steps:
- Create a DP of size 16 and initialize it with 0.
- Set base case for values from 1 to 9 , dp[] = 1.
- Now iterate over subproblems and get the current value from previous computations.
- Create a temp vector to store the current value and after every iteration assign values of temp to DP.
- Create a variable count and iterate the Dp and add value to count
- At last print the final answer stored in count.
Implementation:
C++
// C++ code for above approach#include<bits/stdc++.h>using namespace std;// Function to find// count of N-digit// numbers with single// digit XORvoid countNums(int N){ // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j int dp[16]; memset(dp, 0, sizeof(dp)); // For 1-9 store the value for (int i = 1; i <= 9; i++) dp[i] = 1; // Iterate till N for (int i = 1; i < N; i++) { int temp[16]; memset(temp, 0, sizeof(temp)); for (int j = 0; j < 10; j++) { for (int k = 0; k < 16; k++) { // Calculate XOR int xo = j ^ k; // Store in temporary table temp[xo] += dp[k]; } } memcpy(dp, temp, sizeof(dp)); } // Initialize count int count = 0; for (int i = 0; i < 10; i++) count += dp[i]; // Print the answer cout << (count) << endl;}// Driver Codeint main(){ // Given number N int N = 1; // Function Call countNums(N);}// this code is contributed by bhardwajji |
Java
import java.util.Arrays;public class Main { // Function to find // count of N-digit // numbers with single // digit XOR static void countNums(int N) { // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j int[] dp = new int[16]; Arrays.fill(dp, 0); // For 1-9 store the value for (int i = 1; i <= 9; i++) dp[i] = 1; // Iterate till N for (int i = 1; i < N; i++) { int[] temp = new int[16]; Arrays.fill(temp, 0); for (int j = 0; j < 10; j++) { for (int k = 0; k < 16; k++) { // Calculate XOR int xo = j ^ k; // Store in temporary table temp[xo] += dp[k]; } } System.arraycopy(temp, 0, dp, 0, dp.length); } // Initialize count int count = 0; for (int i = 0; i < 10; i++) count += dp[i]; // Print the answer System.out.println(count); } // Driver Code public static void main(String[] args) { // Given number N int N = 1; // Function Call countNums(N); }} |
Python3
# Function to find# count of N-digit# numbers with single# digit XORdef countNums(N): # dp[i][j] stores the number # of i-digit numbers with # XOR equal to j dp = [0] * 16 # For 1-9 store the value for i in range(1, 10): dp[i] = 1 # Iterate till N for i in range(1, N): temp = [0] * 16 for j in range(10): for k in range(16): # Calculate XOR xo = j ^ k # Store in temporary table temp[xo] += dp[k] dp = temp # Initialize count count = 0 for i in range(10): count += dp[i] # Print the answer print(count)# Driver Codeif __name__ == '__main__': # Given number N N = 1 # Function Call countNums(N) |
C#
using System;class Program { // Function to find count of N-digit // numbers with single digit XOR static void CountNums(int N) { // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j int[] dp = new int[16]; Array.Fill(dp, 0); // For 1-9 store the value for (int i = 1; i <= 9; i++) { dp[i] = 1; } // Iterate till N for (int i = 1; i < N; i++) { int[] temp = new int[16]; Array.Fill(temp, 0); for (int j = 0; j < 10; j++) { for (int k = 0; k < 16; k++) { // Calculate XOR int xo = j ^ k; // Store in temporary table temp[xo] += dp[k]; } } Array.Copy(temp, dp, dp.Length); } // Initialize count int count = 0; for (int i = 0; i < 10; i++) { count += dp[i]; } // Print the answer Console.WriteLine(count); } // Driver Code static void Main(string[] args) { // Given number N int N = 1; // Function Call CountNums(N); }} |
Javascript
function countNums(N) { // dp[i][j] stores the number // of i-digit numbers with // XOR equal to j let dp = new Array(16).fill(0); // For 1-9 store the value for (let i = 1; i <= 9; i++) { dp[i] = 1; } // Iterate till N for (let i = 1; i < N; i++) { let temp = new Array(16).fill(0); for (let j = 0; j < 10; j++) { for (let k = 0; k < 16; k++) { // Calculate XOR let xo = j ^ k; // Store in temporary table temp[xo] += dp[k]; } } dp = temp; } // Initialize count let count = 0; for (let i = 0; i < 10; i++) { count += dp[i]; } // Print the answer console.log(count);}// Driver Codeconst N = 1;// Function CallcountNums(N); |
Output
9
Time Complexity: O(N*10*16) => O(N)
Auxiliary Space: O(16) => O(1)
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!
