Dado un número entero N , la tarea es encontrar el tamaño del grupo más grande en un rango de 1 a N , donde dos números pertenecen al mismo grupo si xor de sus dígitos es el mismo.
Ejemplos:
Entrada: N = 13
Salida: 2
Explicación:
Son 10 grupos en total, se agrupan según el xor de sus dígitos de números del 1 al 13: [11] [1, 10] [2, 13] [3, 12] [4] [5] [6] [7] [8] [9].
De estos, 3 grupos tienen el tamaño más grande que es 2.Entrada: N = 2
Salida: 1
Explicación:
Son 2 grupos en total, se agrupan según el xor de sus dígitos de números del 1 al 2: [1] [2].
De estos, ambos grupos tienen el tamaño más grande que es 1.
Enfoque:
para resolver el problema mencionado anteriormente, tenemos que almacenar el xor de dígitos de cada elemento de 1 a N usando un mapa hash e incrementar su frecuencia si se repite. Luego encuentre la frecuencia máxima dentro del mapa hash, que sería el tamaño más grande del grupo. Y finalmente, cuente todos los grupos que tienen el mismo conteo de frecuencia que el grupo más grande y devuelva el conteo.
A continuación se muestra la implementación del enfoque anterior:
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 digit
int 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 group
int 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 code
int 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 digit
static 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 group
static 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 code
public 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 digit
def 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 group
def 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 N
N = 13
print(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 digit
static 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 group
static 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 code
public 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 digit
function 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 group
function 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 N
let N = 13;
document.write(find_count(N));
// This code is contributed by Dharanendra L V.
</script>
2
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA