Dada una string binaria S de tamaño N y tres números enteros positivos L , R y K , la tarea es encontrar el número mínimo de intercambios necesarios para que la substring {S[L], .. S[R]} consista en exactamente K 1 s. Si no es posible hacerlo, imprima “-1” .
Ejemplos:
Entrada: S = “110011111000101”, L = 5, R = 8, K = 2
Salida: 2
Explicación:
Inicialmente, la substring {S[5], .. S[8]} = “1111” consta de 4 1s.
Intercambiar (S[5], S[3]) y (S[6], S[4]).
String modificada S = “111100111000101” y {S[5], .. S[8]} = “0011”.
Por lo tanto, se requieren 2 intercambios.Entrada: S = “01010101010101”, L = 3, R = 7, K = 8
Salida: -1
Enfoque: la idea es contar el número de 1 y 0 presentes en la substring y fuera de la substring, {S[L], …, S[R]} . Luego, verifique si hay suficientes 1 s o 0 s fuera de ese rango que se puedan intercambiar de modo que la substring contenga exactamente K 1 s.
Siga los pasos a continuación para resolver el problema:
- Almacene la frecuencia de 1 y 0 en la string S en cntOnes y cntZeros respectivamente.
- Además, almacene la frecuencia de 1 s y 0 s en la substring S[L, R] en unos y ceros respectivamente.
- Encuentre la frecuencia de 1 y 0 fuera de la substring S[L, R] usando la fórmula: (rem_ones = cntOnes – ones) y rem_zero = (cntZeros – zeros) .
- Si k ≥ unos , entonces haga lo siguiente:
- Inicialice rem = (K – ones) , que denota el número de 1 necesarios para que la suma sea igual a K .
- Si ceros ≥ rem y rem_ones ≥ rem , imprime el valor de rem como resultado.
- De lo contrario, si K < unos , haga lo siguiente:
- Inicialice rem = (unos – K) , que denota el número de 0 necesarios para que la suma sea igual a K.
- Si unos ≥ rem y rem_zeros ≥ rem , imprime el valor de rem como resultado.
- En todos los demás casos, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of swaps required such that the
// substring {s[l], .., s[r]} consists
// of exactly k 1s
int minimumSwaps(string s, int l, int r, int k)
{
// Store the size of the string
int n = s.length();
// Store the total number of 1s
// and 0s in the entire string
int tot_ones = 0, tot_zeros = 0;
// Traverse the string S to find
// the frequency of 1 and 0
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '1')
tot_ones++;
else
tot_zeros++;
}
// Store the number of 1s and
// 0s in the substring s[l, r]
int ones = 0, zeros = 0, sum = 0;
// Traverse the substring S[l, r]
// to find the frequency of 1s
// and 0s in it
for (int i = l - 1; i < r; i++)
{
if (s[i] == '1')
{
ones++;
sum++;
}
else
zeros++;
}
// Store the count of 1s and
// 0s outside substring s[l, r]
int rem_ones = tot_ones - ones;
int rem_zeros = tot_zeros - zeros;
// Check if the sum of the
// substring is at most K
if (k >= sum)
{
// Store number of 1s required
int rem = k - sum;
// Check if there are enough 1s
// remaining to be swapped
if (zeros >= rem && rem_ones >= rem)
return rem;
}
// If the count of 1s in the substring exceeds k
else if (k < sum)
{
// Store the number of 0s required
int rem = sum - k;
// Check if there are enough 0s
// remaining to be swapped
if (ones >= rem && rem_zeros >= rem)
return rem;
}
// In all other cases, print -1
return -1;
}
// Driver Code
int main()
{
string S = "110011111000101";
int L = 5, R = 8, K = 2;
cout<<minimumSwaps(S, L, R, K);
}
// This code is contributed bgangwar59.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the minimum number
// of swaps required such that the
// substring {s[l], .., s[r]} consists
// of exactly k 1s
static int minimumSwaps(
String s, int l, int r, int k)
{
// Store the size of the string
int n = s.length();
// Store the total number of 1s
// and 0s in the entire string
int tot_ones = 0, tot_zeros = 0;
// Traverse the string S to find
// the frequency of 1 and 0
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1')
tot_ones++;
else
tot_zeros++;
}
// Store the number of 1s and
// 0s in the substring s[l, r]
int ones = 0, zeros = 0, sum = 0;
// Traverse the substring S[l, r]
// to find the frequency of 1s
// and 0s in it
for (int i = l - 1; i < r; i++) {
if (s.charAt(i) == '1') {
ones++;
sum++;
}
else
zeros++;
}
// Store the count of 1s and
// 0s outside substring s[l, r]
int rem_ones = tot_ones - ones;
int rem_zeros = tot_zeros - zeros;
// Check if the sum of the
// substring is at most K
if (k >= sum) {
// Store number of 1s required
int rem = k - sum;
// Check if there are enough 1s
// remaining to be swapped
if (zeros >= rem && rem_ones >= rem)
return rem;
}
// If the count of 1s in the substring exceeds k
else if (k < sum) {
// Store the number of 0s required
int rem = sum - k;
// Check if there are enough 0s
// remaining to be swapped
if (ones >= rem && rem_zeros >= rem)
return rem;
}
// In all other cases, print -1
return -1;
}
// Driver Code
public static void main(String[] args)
{
String S = "110011111000101";
int L = 5, R = 8, K = 2;
System.out.println(
minimumSwaps(S, L, R, K));
}
}
Python3
# Python3 program for the above approach
# Function to find the minimum number
# of swaps required such that the
# substring {s[l], .., s[r]} consists
# of exactly k 1s
def minimumSwaps(s, l, r, k) :
# Store the size of the string
n = len(s)
# Store the total number of 1s
# and 0s in the entire string
tot_ones, tot_zeros = 0, 0
# Traverse the string S to find
# the frequency of 1 and 0
for i in range(0, len(s)) :
if (s[i] == '1') :
tot_ones += 1
else :
tot_zeros += 1
# Store the number of 1s and
# 0s in the substring s[l, r]
ones, zeros, Sum = 0, 0, 0
# Traverse the substring S[l, r]
# to find the frequency of 1s
# and 0s in it
for i in range(l - 1, r) :
if (s[i] == '1') :
ones += 1
Sum += 1
else :
zeros += 1
# Store the count of 1s and
# 0s outside substring s[l, r]
rem_ones = tot_ones - ones
rem_zeros = tot_zeros - zeros
# Check if the sum of the
# substring is at most K
if (k >= Sum) :
# Store number of 1s required
rem = k - Sum
# Check if there are enough 1s
# remaining to be swapped
if (zeros >= rem and rem_ones >= rem) :
return rem
# If the count of 1s in the substring exceeds k
elif (k < Sum) :
# Store the number of 0s required
rem = Sum - k
# Check if there are enough 0s
# remaining to be swapped
if (ones >= rem and rem_zeros >= rem) :
return rem
# In all other cases, print -1
return -1
S = "110011111000101"
L, R, K = 5, 8, 2
print(minimumSwaps(S, L, R, K))
# This code is contributed by divyeshrabadiya07.
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the minimum number
// of swaps required such that the
// substring {s[l], .., s[r]} consists
// of exactly k 1s
static int minimumSwaps(string s, int l, int r, int k)
{
// Store the size of the string
int n = s.Length;
// Store the total number of 1s
// and 0s in the entire string
int tot_ones = 0, tot_zeros = 0;
// Traverse the string S to find
// the frequency of 1 and 0
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '1')
tot_ones++;
else
tot_zeros++;
}
// Store the number of 1s and
// 0s in the substring s[l, r]
int ones = 0, zeros = 0, sum = 0;
// Traverse the substring S[l, r]
// to find the frequency of 1s
// and 0s in it
for (int i = l - 1; i < r; i++)
{
if (s[i] == '1')
{
ones++;
sum++;
}
else
zeros++;
}
// Store the count of 1s and
// 0s outside substring s[l, r]
int rem_ones = tot_ones - ones;
int rem_zeros = tot_zeros - zeros;
// Check if the sum of the
// substring is at most K
if (k >= sum)
{
// Store number of 1s required
int rem = k - sum;
// Check if there are enough 1s
// remaining to be swapped
if (zeros >= rem && rem_ones >= rem)
return rem;
}
// If the count of 1s in the substring exceeds k
else if (k < sum)
{
// Store the number of 0s required
int rem = sum - k;
// Check if there are enough 0s
// remaining to be swapped
if (ones >= rem && rem_zeros >= rem)
return rem;
}
// In all other cases, print -1
return -1;
}
// Driver Code
public static void Main(String[] args)
{
string S = "110011111000101";
int L = 5, R = 8, K = 2;
Console.Write(minimumSwaps(S, L, R, K));
}
}
// This code is contributed by splevel62.
Javascript
<script>
// javascript program for the above approach
// Function to find the minimum number
// of swaps required such that the
// substring {s[l], .., s[r]} consists
// of exactly k 1s
function minimumSwaps(s , l , r , k)
{
// Store the size of the string
var n = s.length;
// Store the total number of 1s
// and 0s in the entire string
var tot_ones = 0, tot_zeros = 0;
// Traverse the string S to find
// the frequency of 1 and 0
for (i = 0; i < s.length; i++) {
if (s.charAt(i) == '1')
tot_ones++;
else
tot_zeros++;
}
// Store the number of 1s and
// 0s in the substring s[l, r]
var ones = 0, zeros = 0, sum = 0;
// Traverse the substring S[l, r]
// to find the frequency of 1s
// and 0s in it
for (var i = l - 1; i < r; i++) {
if (s.charAt(i) == '1') {
ones++;
sum++;
}
else
zeros++;
}
// Store the count of 1s and
// 0s outside substring s[l, r]
var rem_ones = tot_ones - ones;
var rem_zeros = tot_zeros - zeros;
// Check if the sum of the
// substring is at most K
if (k >= sum) {
// Store number of 1s required
var rem = k - sum;
// Check if there are enough 1s
// remaining to be swapped
if (zeros >= rem && rem_ones >= rem)
return rem;
}
// If the count of 1s in the substring exceeds k
else if (k < sum) {
// Store the number of 0s required
var rem = sum - k;
// Check if there are enough 0s
// remaining to be swapped
if (ones >= rem && rem_zeros >= rem)
return rem;
}
// In all other cases, print -1
return -1;
}
// Driver Code
var S = "110011111000101";
var L = 5, R = 8, K = 2;
document.write(
minimumSwaps(S, L, R, K));
// This code is contributed by 29AjayKumar
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kunalsg18elec y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA