Given an integer N and the task is to find the size of the largest group in a range 1 to N, where two numbers belong to the same group if xor of its digits is the same.
Examples:
Input: N = 13
Output: 2
Explanation:
There are 10 groups in total, they are grouped according to the xor of its digits of numbers from 1 to 13: [11] [1, 10] [2, 13] [3, 12] [4] [5] [6] [7] [8] [9].
Out of these, 3 groups have the largest size that is 2.Input: N = 2
Output: 1
Explanation:
There are 2 groups in total, they are grouped according to the xor of its digits of numbers from 1 to 2: [1] [2].
Out of these, both groups have the largest size that is 1.
Approach:
To solve the problem mentioned above we have to store the xor of digit of every element from 1 to N using a hash map and increment its frequency if it repeats. Then find the maximum frequency within the hash map, which would be the largest size of the group. And finally, count all the groups who have the same frequency count as the largest group and return the count.
Below is the implementation of above the approach:
C++14
// c++ implementation to Find the// size of largest group, where groups// are according to the xor of its digits.#include <bits/stdc++.h>using namespace std;// Function to find out xor of digitint digit_xor(int x){ int xorr = 0; // calculate xor digitwise while (x) { xorr ^= x % 10; x = x / 10; } // return xor return xorr;}// Function to find the// size of largest groupint find_count(int n){ // hash map for counting frequency map<int, int> mpp; for (int i = 1; i <= n; i++) { // counting freq of each element mpp[digit_xor(i)] += 1; } int maxm = 0; for (auto x : mpp) { // find the maximum if (x.second > maxm) maxm = x.second; } return maxm;}// Driver codeint main(){ // initialise N int N = 13; cout << find_count(N); return 0;} |
Java
// Java implementation to Find the// size of largest group, where groups// are according to the xor of its digits.import java.util.*;class GFG{// Function to find out xor of digitstatic int digit_xor(int x){ int xorr = 0; // calculate xor digitwise while (x > 0) { xorr ^= x % 10; x = x / 10; } // return xor return xorr;}// Function to find the// size of largest groupstatic int find_count(int n){ // hash map for counting frequency HashMap<Integer, Integer> mpp = new HashMap<Integer, Integer>(); for (int i = 1; i <= n; i++) { // counting freq of each element if(mpp.containsKey(digit_xor(i))) mpp.put(digit_xor(i), mpp.get(digit_xor(i)) + 1); else mpp.put(digit_xor(i), 1); } int maxm = 0; for (Map.Entry<Integer, Integer> x : mpp.entrySet()) { // find the maximum if (x.getValue() > maxm) maxm = x.getValue(); } return maxm;}// Driver codepublic static void main(String[] args){ // initialise N int N = 13; System.out.print(find_count(N));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 implementation to find the# size of largest group, where groups# are according to the xor of its digits.# Function to find out xor of digitdef digit_xor(x): xorr = 0 # Calculate xor digitwise while (x != 0): xorr ^= x % 10 x = x // 10 # Return xor return xorr# Function to find the# size of largest groupdef find_count(n): # Hash map for counting frequency mpp = {} for i in range(1, n + 1): # Counting freq of each element if digit_xor(i) in mpp: mpp[digit_xor(i)] += 1 else: mpp[digit_xor(i)] = 1 maxm = 0 for x in mpp: # Find the maximum if (mpp[x] > maxm): maxm = mpp[x] return maxm# Driver code# Initialise NN = 13print(find_count(N))# This code is contributed by divyeshrabadiya07 |
C#
// C# implementation to Find the// size of largest group, where groups// are according to the xor of its digits.using System;using System.Collections.Generic;class GFG{// Function to find out xor of digitstatic int digit_xor(int x){ int xorr = 0; // calculate xor digitwise while (x > 0) { xorr ^= x % 10; x = x / 10; } // return xor return xorr;}// Function to find the// size of largest groupstatic int find_count(int n){ // hash map for counting frequency Dictionary<int, int> mpp = new Dictionary<int, int>(); for (int i = 1; i <= n; i++) { // counting freq of each element if(mpp.ContainsKey(digit_xor(i))) mpp[digit_xor(i)] = mpp[digit_xor(i)] + 1; else mpp.Add(digit_xor(i), 1); } int maxm = 0; foreach (KeyValuePair<int, int> x in mpp) { // find the maximum if (x.Value > maxm) maxm = x.Value; } return maxm;}// Driver codepublic static void Main(String[] args){ // initialise N int N = 13; Console.Write(find_count(N));}} // This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript implementation to Find the// size of largest group, where groups// are according to the xor of its digits.// Function to find out xor of digitfunction digit_xor(x){ let xorr = 0; // calculate xor digitwise while (x) { xorr ^= x % 10; x = x / 10; } // return xor return xorr;}// Function to find the// size of largest groupfunction find_count(n){ // hash map for counting frequency let mpp = new Map(); for(let i = 1; i <= n; i++) { // Counting freq of each element let t = digit_xor(i); if (mpp.has(t)) { mpp.set(t, mpp.get(t) + 1) } else { mpp.set(t, 1) } } let maxm = 0; for(let x of mpp) { // Find the maximum if (x[1] > maxm) maxm = x[1]; } return maxm;}// Driver code// initialise Nlet N = 13;document.write(find_count(N));// This code is contributed by Dharanendra L V.</script> |
Output
2
Time complexity: O(NlogN)
Space complexity: O(N)
Approach(Using brute force):To solve this problem using brute force approach, we can follow the steps given below:
- Create a helper function to calculate the XOR of digits of a given number. This function takes an integer as input and returns the XOR of its digits.
- Loop through all numbers from 1 to N and calculate the XOR of their digits using the helper function.
- For each XOR value, create a list of numbers that have the same XOR value.
- Find the list with the maximum length and return its length as the answer.
Below is the implementation of above the approach:
C++
#include <iostream>#include <unordered_map>using namespace std;int findXor(int n) { // Helper function to calculate XOR of digits int xorSum = 0; while (n > 0) { xorSum ^= (n % 10); n /= 10; } return xorSum;}int largestGroup(int n) { // Loop through all numbers and find XOR of digits unordered_map<int, int> groups; for (int i = 1; i <= n; i++) { int xorSum = findXor(i); if (groups.find(xorSum) != groups.end()) { groups[xorSum]++; } else { groups[xorSum] = 1; } } // Find the group with maximum size int maxSize = 0; for (auto it = groups.begin(); it != groups.end(); it++) { int size = it->second; if (size > maxSize) { maxSize = size; } } return maxSize;}int main() { int n = 13; cout << largestGroup(n) << endl; // Output: 2 return 0;} |
Java
import java.util.HashMap;import java.util.Map;public class GFG { public static int findXor(int n) { // Helper function to calculate XOR of digits int xorSum = 0; while (n > 0) { xorSum ^= (n % 10); n /= 10; } return xorSum; } public static int largestGroup(int n) { // Loop through all numbers and find XOR of digits Map<Integer, Integer> groups = new HashMap<>(); for (int i = 1; i <= n; i++) { int xorSum = findXor(i); if (groups.containsKey(xorSum)) { groups.put(xorSum, groups.get(xorSum) + 1); } else { groups.put(xorSum, 1); } } // Find the group with maximum size int maxSize = 0; for (Map.Entry<Integer, Integer> entry : groups.entrySet()) { int size = entry.getValue(); if (size > maxSize) { maxSize = size; } } return maxSize; } public static void main(String[] args) { int n = 13; System.out.println(largestGroup(n)); // Output: 2 }} |
Python
def findXor(n): # Helper function to calculate XOR of digits xorSum = 0 while n > 0: xorSum ^= n % 10 n //= 10 return xorSumdef largestGroup(n): # Loop through all numbers and find XOR of digits groups = {} for i in range(1, n + 1): xorSum = findXor(i) if xorSum in groups: groups[xorSum] += 1 else: groups[xorSum] = 1 # Find the group with maximum size maxSize = 0 for size in groups.values(): if size > maxSize: maxSize = size return maxSizen = 13print(largestGroup(n)) # Output: 2# by phasing17 |
C#
using System;using System.Collections.Generic;class GFG{ public static int FindXor(int n) { // Helper function to calculate XOR of digits int xorSum = 0; while (n > 0) { xorSum ^= (n % 10); n /= 10; } return xorSum; } public static int LargestGroup(int n) { // Loop through all numbers and find XOR of digits Dictionary<int, int> groups = new Dictionary<int, int>(); for (int i = 1; i <= n; i++) { int xorSum = FindXor(i); if (groups.ContainsKey(xorSum)) { groups[xorSum] = groups[xorSum] + 1; } else { groups[xorSum] = 1; } } // Find the group with maximum size int maxSize = 0; foreach (var entry in groups) { int size = entry.Value; if (size > maxSize) { maxSize = size; } } return maxSize; } public static void Main(string[] args) { int n = 13; Console.WriteLine(LargestGroup(n)); // Output: 2 }} |
Javascript
// JavaScript code to implement the approachfunction findXor(n) { // Helper function to calculate XOR of digits let xorSum = 0; while (n > 0) { xorSum ^= n % 10; n = Math.floor(n / 10); } return xorSum;}function largestGroup(n) { // Loop through all numbers and find XOR of digits let groups = {}; for (let i = 1; i <= n; i++) { let xorSum = findXor(i); if (xorSum in groups) { groups[xorSum] += 1; } else { groups[xorSum] = 1; } } // Find the group with maximum size let maxSize = 0; for (let size of Object.values(groups)) { if (size > maxSize) { maxSize = size; } } return maxSize;}// Driver codelet n = 13;console.log(largestGroup(n)); // Output: 2// by phasing17 |
Output
2
Time complexity: O(N * D), where N is the input number and D is the number of digits in the largest number in the range. This is because the largestGroup() function loops through all numbers from 1 to N and calculates the XOR of digits for each number using the findXor() function. The time complexity of findXor() is O(D), as it loops through each digit in the number.
Space complexity:O(N), which is the size of the unordered map used to store the groups. In the worst case, all numbers in the range may have a unique XOR value, resulting in N groups. However, in practice, the number of unique XOR values is likely to be much smaller than N.
Approach:(Digit sum approach):
- Initialize an array count of size 19 (to represent all possible XORs of two digits from 0 to 9) with all elements set to 0.
- Iterate from 1 to N and for each number:
a. Calculate the XOR of its digits by repeatedly taking the XOR of the number with 10 and adding it to a sum variable until the number becomes 0. This can be done using a while loop.
b. Increment the value of count[sum] by 1. - Find the maximum value in the count array and return it as the size of the largest group.
Below is the implementation of above the approach:
C++
#include <iostream>#include <algorithm>using namespace std;int largestGroup(int N) { int count[19] = {0}; // Initialize count array int maxCount = 0; // Initialize maximum count to 0 for (int i = 1; i <= N; i++) { int sum = 0; int num = i; while (num > 0) { sum ^= num % 10; num /= 10; } count[sum]++; maxCount = max(maxCount, count[sum]); // Update maximum count } return maxCount;}int main() { int N=13; cout << largestGroup(N) << endl; return 0;} |
Java
import java.util.Arrays;class GFG { public static int largestGroup(int N) { int[] count = new int[19]; // Initialize count array int maxCount = 0; // Initialize maximum count to 0 for (int i = 1; i <= N; i++) { int sum = 0; int num = i; while (num > 0) { sum ^= num % 10; num /= 10; } count[sum]++; maxCount = Math.max(maxCount, count[sum]); // Update maximum count } return maxCount; } // Driver code public static void main(String[] args) { int N = 13; // Function call System.out.println(largestGroup(N)); }}// contributed by phasing17 |
Python3
def largestGroup(N): # Initialize an array to count the occurrences of each possible digit sum (0 to 9) count = [0] * 10 # Initialize the maximum count to 0 maxCount = 0 # Iterate through numbers from 1 to N for i in range(1, N + 1): num = i sum_val = 0 # Calculate the digit sum of the current number while num > 0: sum_val += num % 10 # Extract the last digit and add it to the sum num //= 10 # Remove the last digit # Increment the count of numbers with the same digit sum count[sum_val] += 1 # Update the maximum count if needed maxCount = max(maxCount, count[sum_val]) return maxCountif __name__ == "__main__": N = 13 print(largestGroup(N)) |
C#
using System;class Program{ // Function to calculate the largest group based on XOR sum of digits static int LargestGroup(int N) { int[] count = new int[19]; // Initialize count array to // store counts for each XOR sum int maxCount = 0; // Initialize maximum count to 0 for (int i = 1; i <= N; i++) { int sum = 0; int num = i; // Calculate the XOR sum of digits of the current number while (num > 0) { sum ^= num % 10; // Extract the last digit and XOR it with the current sum num /= 10; // Remove the last digit } count[sum]++; // Increment the count for the calculated XOR sum maxCount = Math.Max(maxCount, count[sum]); // Update maximum count } return maxCount; // Return the maximum count (largest group) } static void Main(string[] args) { int N = 13; // Define the value of N // Calculate and print the largest group Console.WriteLine("Largest Group: " + LargestGroup(N)); }} |
Javascript
function largestGroup(N) { let count = new Array(19).fill(0); // Initialize count array let maxCount = 0; // Initialize maximum count to 0 for (let i = 1; i <= N; i++) { let sum = 0; let num = i; while (num > 0) { sum ^= num % 10; num /= 10; } count[sum]++; maxCount = Math.max(maxCount, count[sum]); // Update maximum count } return maxCount;}let N=13;document.write(largestGroup(N)); |
Output
2
Time complexity: O(N log N) due to the XOR calculation inside the loop, which takes log N time.
Space complexity: The space complexity is O(1) since we only use a constant amount of extra memory to store the count array.
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!
