Dada una string binaria S de tamaño N y una array arr[] de M enteros, la tarea es encontrar la string final después de invertir los caracteres en los índices que son múltiplos de los factores primos de todos los elementos de la array. Tenga en cuenta que este problema utiliza la indexación basada en 1.
Ejemplos:
Entrada: S = “000000”, arr[] = {2, 4, 6}
Salida: 011100
Explicación:
- Los factores primos de 2 son {2}. Por lo tanto, la string después de invertir los valores de todos los índices que son múltiplos de 2 es S = «010101».
- Los factores primos de 4 son {2}. Por lo tanto, la string después de invertir los valores de todos los índices que son múltiplos de 2 es S = «000000».
- Los factores primos de 6 son {2, 3}. Por lo tanto, la string después de voltear los valores de todos los índices que son múltiplos de 2 es S = «010101» y la string después de voltear los valores de todos los índices que son múltiplos de 3 es S = «011100».
Entrada: S = “001100”, arr[] = {2, 3, 5}
Salida: 010010
Enfoque: el problema dado se puede resolver con la ayuda de la criba de Eratóstenes almacenando la frecuencia de los factores primos de todos los elementos de la array. Se puede observar que los factores primos con frecuencias pares no contribuirán al volteo. Por lo tanto, la string resultante se puede obtener invirtiendo los bits de índices que son múltiplos de factores primos con frecuencia impar. Siga los pasos a continuación para resolver el problema dado:
- Cree una función getFactorization() , que devuelva todos los factores primos de cualquier número .
- Inicialice una array, frecuencia[] que almacena la frecuencia de todos los factores primos distintos de todos los elementos de la array arr[] .
- Recorra la array dada arr[] y para cada elemento de la array arr[i] , encuentre el factor primo usando getFactorization( arr[i] ) e incremente la frecuencia de los factores primos en la array de frecuencia[] .
- Para todos los valores impares de frecuencia[i] en la array, repita todos los factores de i y voltee los bits de los índices respectivos en la string S dada.
- La string almacenada en S es la string requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
#define MAXN 100001
// Stores smallest prime factor
int spf[MAXN];
// Function to find the smallest prime
// factor for every number till MAXN
void sieve()
{
spf[1] = 1;
// Marking smallest prime factor for
// every number to be itself
for (int i = 2; i < MAXN; i++)
spf[i] = i;
// Separately marking spf for every
// even number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
// Checking if i is prime
if (spf[i] == i) {
// Marking SPF for all numbers
// divisible by i
for (int j = i * i;
j < MAXN; j += i) {
if (spf[j] == j)
spf[j] = i;
}
}
}
}
// Function to find all the distinct prime
// factors of the given number x
vector<int> getFactorization(int x)
{
vector<int> ret;
// Find the prime factors for X
while (x != 1) {
ret.push_back(spf[x]);
// Find the spf[] of x
int value = spf[x];
while (x % value == 0)
x = x / value;
}
// Return the prime factors for x
return ret;
}
// Function to find string after flipping
// the characters at indices of prime
// factors of array elements arr[]
string flipString(string S, int arr[],
int M)
{
// Precalculating Smallest Prime Factor
sieve();
// Stores the frequency of each
// prime factor
int frequency[MAXN] = { 0 };
// Iterate over all elements of
// the array arr[]
for (int i = 0; i < M; i++) {
// Stores prime factors of arr[i]
vector<int> primeFactors
= getFactorization(arr[i]);
// Increment the frequency of all
// prime factors of arr[i]
for (auto& factors : primeFactors) {
frequency[factors]++;
frequency[factors] %= 2;
}
}
int N = S.length();
// Iterate over all elements of
// the array frequency[]
for (int i = 0; i < MAXN; i++) {
// If frequency[i] is odd
if (frequency[i] & 1) {
// Flip bits of all indices
// that are multiple of i
for (int j = i; j <= N; j += i) {
S[j - 1] = (S[j - 1]
== '1'
? '0'
: '1');
}
}
}
// Return Answer
return S;
}
// Driver Code
int main()
{
string S = "000000";
int arr[] = { 2, 4, 6 };
int M = sizeof(arr) / sizeof(arr[0]);
cout << flipString(S, arr, M);
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
import java.util.Arrays;
class GFG {
public static int MAXN = 100001;
// Stores smallest prime factor
public static int[] spf = new int[MAXN];
// Function to find the smallest prime
// factor for every number till MAXN
public static void sieve() {
spf[1] = 1;
// Marking smallest prime factor for
// every number to be itself
for (int i = 2; i < MAXN; i++)
spf[i] = i;
// Separately marking spf for every
// even number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
// Checking if i is prime
if (spf[i] == i) {
// Marking SPF for all numbers
// divisible by i
for (int j = i * i; j < MAXN; j += i) {
if (spf[j] == j)
spf[j] = i;
}
}
}
}
// Function to find all the distinct prime
// factors of the given number x
public static ArrayList<Integer> getFactorization(int x) {
ArrayList<Integer> ret = new ArrayList<Integer>();
// Find the prime factors for X
while (x != 1) {
ret.add(spf[x]);
// Find the spf[] of x
int value = spf[x];
while (x % value == 0)
x = x / value;
}
// Return the prime factors for x
return ret;
}
// Function to find string after flipping
// the characters at indices of prime
// factors of array elements arr[]
public static String flipString(String S, int arr[], int M) {
// Precalculating Smallest Prime Factor
sieve();
// Stores the frequency of each
// prime factor
int[] frequency = new int[MAXN];
Arrays.fill(frequency, 0);
// Iterate over all elements of
// the array arr[]
for (int i = 0; i < M; i++) {
// Stores prime factors of arr[i]
ArrayList<Integer> primeFactors = getFactorization(arr[i]);
// Increment the frequency of all
// prime factors of arr[i]
for (int factors : primeFactors) {
frequency[factors]++;
frequency[factors] %= 2;
}
}
int N = S.length();
// Iterate over all elements of
// the array frequency[]
for (int i = 0; i < MAXN; i++) {
// If frequency[i] is odd
if ((frequency[i] & 1) > 0) {
// Flip bits of all indices
// that are multiple of i
for (int j = i; j <= N; j += i)
{
// S.replace(S.charAt(j - 1), (S.charAt(j - 1) == '1' ? '0' : '1'));
S = S.substring(0, j - 1) + (S.charAt(j - 1) == '1' ? '0' : '1') + S.substring(j);
}
}
}
// Return Answer
return S;
}
// Driver Code
public static void main(String args[]) {
String S = "000000";
int arr[] = { 2, 4, 6 };
int M = arr.length;
System.out.println(flipString(S, arr, M));
}
}
// This code is contributed by gfgking.
Python3
# Python program for the above approach
MAXN = 100001
# Stores smallest prime factor
spf = [0] * MAXN
# Function to find the smallest prime
# factor for every number till MAXN
def sieve():
spf[1] = 1
# Marking smallest prime factor for
# every number to be itself
for i in range(2, MAXN):
spf[i] = i
# Separately marking spf for every
# even number as 2
for i in range(4, MAXN, 2):
spf[i] = 2
i = 3
while(i * 8 < MAXN):
i += 1
# Checking if i is prime
if (spf[i] == i):
# Marking SPF for all numbers
# divisible by i
for j in range(i * i, MAXN, i):
if (spf[j] == j):
spf[j] = i
# Function to find all the distinct prime
# factors of the given number x
def getFactorization (x):
ret = []
# Find the prime factors for X
while (x != 1):
ret.append(spf[x])
# Find the spf[] of x
value = spf[x]
while (x % value == 0):
x = x // value
# Return the prime factors for x
return ret
# Function to find string after flipping
# the characters at indices of prime
# factors of array elements arr[]
def flipString (S, arr, M):
# Precalculating Smallest Prime Factor
sieve();
# Stores the frequency of each
# prime factor
frequency = [0] * MAXN
# Iterate over all elements of
# the array arr[]
for i in range(0, M):
# Stores prime factors of arr[i]
primeFactors = getFactorization(arr[i])
# Increment the frequency of all
# prime factors of arr[i]
for factors in primeFactors :
frequency[factors] += 1
frequency[factors] %= 2
N = len(S)
# Iterate over all elements of
# the array frequency[]
for i in range(0, MAXN):
# If frequency[i] is odd
if (frequency[i] & 1):
# Flip bits of all indices
# that are multiple of i
for j in range(i, N + 1, i):
S[j - 1] = ('0' if S[j - 1] == '1' else '1')
# Return Answer
return S
# Driver Code
S = "000000"
S = list(S)
arr = [2, 4, 6]
M = len(arr)
print("".join(flipString(S, arr, M)))
# This code is contributed by gfgking.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
public static int MAXN = 100001;
// Stores smallest prime factor
public static int[] spf = new int[MAXN];
// Function to find the smallest prime
// factor for every number till MAXN
public static void sieve()
{
spf[1] = 1;
// Marking smallest prime factor for
// every number to be itself
for (int i = 2; i < MAXN; i++)
spf[i] = i;
// Separately marking spf for every
// even number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all numbers
// divisible by i
for (int j = i * i; j < MAXN; j += i)
{
if (spf[j] == j)
spf[j] = i;
}
}
}
}
// Function to find all the distinct prime
// factors of the given number x
public static List<int> getFactorization(int x)
{
List<int> ret = new List<int>();
// Find the prime factors for X
while (x != 1)
{
ret.Add(spf[x]);
// Find the spf[] of x
int value = spf[x];
while (x % value == 0)
x = x / value;
}
// Return the prime factors for x
return ret;
}
// Function to find string after flipping
// the characters at indices of prime
// factors of array elements arr[]
public static String flipString(String S, int[] arr, int M)
{
// Precalculating Smallest Prime Factor
sieve();
// Stores the frequency of each
// prime factor
int[] frequency = new int[MAXN];
Array.Fill(frequency, 0);
// Iterate over all elements of
// the array arr[]
for (int i = 0; i < M; i++)
{
// Stores prime factors of arr[i]
List<int> primeFactors = getFactorization(arr[i]);
// Increment the frequency of all
// prime factors of arr[i]
foreach (int factors in primeFactors)
{
frequency[factors]++;
frequency[factors] %= 2;
}
}
int N = S.Length;
// Iterate over all elements of
// the array frequency[]
for (int i = 0; i < MAXN; i++)
{
// If frequency[i] is odd
if ((frequency[i] & 1) > 0)
{
// Flip bits of all indices
// that are multiple of i
for (int j = i; j <= N; j += i)
{
// S.replace(S.charAt(j - 1), (S.charAt(j - 1) == '1' ? '0' : '1'));
S = S.Substring(0, j - 1) + (S[j - 1] == '1' ? '0' : '1') + S.Substring(j);
}
}
}
// Return Answer
return S;
}
// Driver Code
public static void Main()
{
String S = "000000";
int[] arr = { 2, 4, 6 };
int M = arr.Length;
Console.Write(flipString(S, arr, M));
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript program for the above approach
const MAXN = 100001;
// Stores smallest prime factor
let spf = new Array(MAXN).fill(0);
// Function to find the smallest prime
// factor for every number till MAXN
const sieve = () => {
spf[1] = 1;
// Marking smallest prime factor for
// every number to be itself
for (let i = 2; i < MAXN; i++)
spf[i] = i;
// Separately marking spf for every
// even number as 2
for (let i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (let i = 3; i * i < MAXN; i++) {
// Checking if i is prime
if (spf[i] == i) {
// Marking SPF for all numbers
// divisible by i
for (let j = i * i;
j < MAXN; j += i) {
if (spf[j] == j)
spf[j] = i;
}
}
}
}
// Function to find all the distinct prime
// factors of the given number x
const getFactorization = (x) => {
let ret = [];
// Find the prime factors for X
while (x != 1) {
ret.push(spf[x]);
// Find the spf[] of x
let value = spf[x];
while (x % value == 0)
x = parseInt(x / value);
}
// Return the prime factors for x
return ret;
}
// Function to find string after flipping
// the characters at indices of prime
// factors of array elements arr[]
const flipString = (S, arr, M) => {
// Precalculating Smallest Prime Factor
sieve();
// Stores the frequency of each
// prime factor
let frequency = new Array(MAXN).fill(0);
// Iterate over all elements of
// the array arr[]
for (let i = 0; i < M; i++) {
// Stores prime factors of arr[i]
let primeFactors = getFactorization(arr[i]);
// Increment the frequency of all
// prime factors of arr[i]
for (let factors in primeFactors) {
frequency[primeFactors[factors]]++;
frequency[factors] %= 2;
}
}
let N = S.length;
// Iterate over all elements of
// the array frequency[]
for (let i = 0; i < MAXN; i++) {
// If frequency[i] is odd
if (frequency[i] & 1) {
// Flip bits of all indices
// that are multiple of i
for (let j = i; j <= N; j += i) {
S[j - 1] = (S[j - 1] == '1' ? '0' : '1');
}
}
}
// Return Answer
return S;
}
// Driver Code
let S = "000000";
S = S.split("");
let arr = [2, 4, 6];
let M = arr.length;
document.write(flipString(S, arr, M).join(''));
// This code is contributed by rakeshsahni
</script>
Producción:
011100
Complejidad de tiempo: O(N*log N + K*log K), donde K es el número entero máximo en la array arr[].
Espacio Auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA