Dada una array circular binaria de N elementos de tamaño y dos números enteros positivos x e y que indican los índices en la array circular. La tarea es comprobar en qué camino, en el sentido de las agujas del reloj o en el sentido contrario, del índice x al índice y, nos enfrentamos al número mínimo de cambios de bits. Salida «En el sentido de las agujas del reloj» o «En el sentido contrario a las agujas del reloj» y el valor de cambio de bit mínimo, en caso de salida de conteo igual «En el sentido de las agujas del reloj».
Ejemplos:
Input : arr[] = { 0, 0, 0, 1, 1, 0 }
x = 0, y = 5
Output : Anti-clockwise 0
The path 0 -> 1 -> 2 -> 3 -> 4 -> 5, we have only 1 value change i.e from index 2 to 3.
The path 0 -> 5 have 0 value change.
So, the answer is Anti-clockwise 0.
Input : s = { 1, 1, 0, 1, 1 }
x = 2, y = 0
Output : Clockwise 1
La idea es comprobar yendo una vez en el sentido de las agujas del reloj y almacenar la cuenta 1 y luego ir en sentido contrario a las agujas del reloj y almacenar la cuenta 2. Luego salida comparando count1 y count2.
¿Cómo viajar en sentido horario o antihorario?
Será difícil viajar en el sentido de las agujas del reloj en la array donde x > y y lo mismo en el caso contrario a las agujas del reloj donde y > x. Entonces, almacenaremos la array binaria dada en la string «S». Y para hacerlo circular, agregaremos S a S, es decir, S = S + S. Haremos el ajuste en xey para viajar en sentido horario o antihorario.
Ahora, si y > x y para ir en el sentido de las agujas del reloj, será fácil iterar de x a y y calcular el número de flip bits.
Si y > x y para ir en sentido contrario a las agujas del reloj, sumaremos |S| a x luego iterar de y a x y calcular el número de flip bits.
Ahora, si x > y, intercambiaremos x e y y calcularemos la respuesta utilizando el enfoque anterior. Luego emite lo contrario del resultado.
Para calcular el número de flip bits, simplemente almacene el bit de índice actual y verifique si el siguiente índice tiene el mismo bit que el actual. En caso afirmativo, no haga nada más, cambie el bit actual al bit del siguiente índice e incremente el bit mínimo en 1.
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to find direction with minimum flips
#include <bits/stdc++.h>
using namespace std;
// finding which path have minimum flip bit and
// the minimum flip bits
void minimumFlip(string s, int x, int y)
{
// concatenating given string to itself,
// to make it circular
s = s + s;
// check x is greater than y.
// marking if output need to
// be opposite.
bool isOpposite = false;
if (x > y) {
swap(x, y);
isOpposite = true;
}
// iterate Clockwise
int valClockwise = 0;
char cur = s[x];
for (int i = x; i <= y; i++) {
// if current bit is not equal
// to next index bit.
if (s[i] != cur) {
cur = s[i];
valClockwise++;
}
}
// iterate Anti-Clockwise
int valAnticlockwise = 0;
cur = s[y];
x += s.length();
for (int i = y; i <= x; i++) {
// if current bit is not equal
// to next index bit.
if (s[i] != cur) {
cur = s[i];
valAnticlockwise++;
}
}
// Finding whether Clockwise or Anti-clockwise
// path take minimum flip.
if (valClockwise <= valAnticlockwise) {
if (!isOpposite)
cout << "Clockwise "
<< valClockwise << endl;
else
cout << "Anti-clockwise "
<< valAnticlockwise << endl;
}
else {
if (!isOpposite)
cout << "Anti-clockwise "
<< valAnticlockwise << endl;
else
cout << "Clockwise "
<< valClockwise << endl;
}
}
// Driven Program
int main()
{
int x = 0, y = 8;
string s = "000110";
minimumFlip(s, x, y);
return 0;
}
Java
// Java program to find direction
// with minimum flips
class GFG
{
// finding which path have
// minimum flip bit and
// the minimum flip bits
static void minimumFlip(String s,
int x, int y)
{
// concatenating given string to
// itself, to make it circular
s = s + s;
// check x is greater than y.
// marking if output need to
// be opposite.
boolean isOpposite = false;
if (x > y)
{
swap(x, y);
isOpposite = true;
}
// iterate Clockwise
int valClockwise = 0;
char cur = s.charAt(x);
for (int i = x; i <= y; i++)
{
// if current bit is not equal
// to next index bit.
if (s.charAt(i) != cur)
{
cur = s.charAt(i);
valClockwise++;
}
}
// iterate Anti-Clockwise
int valAnticlockwise = 0;
cur = s.charAt(y);
x += s.length();
for (int i = y; i < x; i++)
{
// if current bit is not equal
// to next index bit.
if (s.charAt(i) != cur)
{
cur = s.charAt(i);
valAnticlockwise++;
}
}
// Finding whether Clockwise
// or Anti-clockwise path
// take minimum flip.
if (valClockwise <= valAnticlockwise)
{
if (!isOpposite)
{
System.out.println("Clockwise " +
valClockwise);
}
else
{
System.out.println("Anti-clockwise " +
valAnticlockwise);
}
}
else if (!isOpposite)
{
System.out.println("Anti-clockwise " +
valAnticlockwise);
}
else
{
System.out.println("Clockwise " +
valClockwise);
}
}
static void swap(int a, int b)
{
int c = a;
a = b;
b = c;
}
// Driver code
public static void main(String[] args)
{
int x = 0, y = 8;
String s = "000110";
minimumFlip(s, x, y);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to find direction
# with minimum flips
# finding which path have minimum flip bit
# and the minimum flip bits
def minimumFlip(s, x, y):
# concatenating given string to itself,
# to make it circular
s = s + s
# check x is greater than y.
# marking if output need to
# be opposite.
isOpposite = False
if (x > y):
temp = y
y = x;
x = temp
isOpposite = True
# iterate Clockwise
valClockwise = 0
cur = s[x]
for i in range(x, y + 1, 1):
# if current bit is not equal
# to next index bit.
if (s[i] != cur):
cur = s[i]
valClockwise += 1
# iterate Anti-Clockwise
valAnticlockwise = 0
cur = s[y]
x += len(s) - 1
for i in range(y, x + 1, 1):
# if current bit is not equal
# to next index bit.
if (s[i] != cur):
cur = s[i]
valAnticlockwise += 1
# Finding whether Clockwise or Anti-clockwise
# path take minimum flip.
if (valClockwise <= valAnticlockwise):
if (isOpposite == False):
print("Clockwise", valClockwise)
else:
print("Anti-clockwise",
valAnticlockwise)
else:
if (isOpposite == False):
print("Anti-clockwise",
valAnticlockwise)
else:
print("Clockwise", valClockwise)
# Driver Code
if __name__ == '__main__':
x = 0
y = 8
s = "000110"
minimumFlip(s, x, y)
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find direction
// with minimum flips
using System;
class GFG
{
// finding which path have
// minimum flip bit and
// the minimum flip bits
static void minimumFlip(String s,
int x, int y)
{
// concatenating given string to
// itself, to make it circular
s = s + s;
// check x is greater than y.
// marking if output need to
// be opposite.
bool isOpposite = false;
if (x > y)
{
swap(x, y);
isOpposite = true;
}
// iterate Clockwise
int valClockwise = 0;
char cur = s[x];
for (int i = x; i <= y; i++)
{
// if current bit is not equal
// to next index bit.
if (s[i] != cur)
{
cur = s[i];
valClockwise++;
}
}
// iterate Anti-Clockwise
int valAnticlockwise = 0;
cur = s[y];
x += s.Length;
for (int i = y; i < x; i++)
{
// if current bit is not equal
// to next index bit.
if (s[i] != cur)
{
cur = s[i];
valAnticlockwise++;
}
}
// Finding whether Clockwise
// or Anti-clockwise path
// take minimum flip.
if (valClockwise <= valAnticlockwise)
{
if (!isOpposite)
{
Console.WriteLine("Clockwise " +
valClockwise);
}
else
{
Console.WriteLine("Anti-clockwise " +
valAnticlockwise);
}
}
else if (!isOpposite)
{
Console.WriteLine("Anti-clockwise " +
valAnticlockwise);
}
else
{
Console.WriteLine("Clockwise " +
valClockwise);
}
}
static void swap(int a, int b)
{
int c = a;
a = b;
b = c;
}
// Driver code
public static void Main(String[] args)
{
int x = 0, y = 8;
String s = "000110";
minimumFlip(s, x, y);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find direction with minimum flips
// finding which path have minimum flip bit and
// the minimum flip bits
function minimumFlip(s, x, y)
{
// concatenating given string to itself,
// to make it circular
s = s + s;
// check x is greater than y.
// marking if output need to
// be opposite.
var isOpposite = false;
if (x > y) {
swap(x, y);
isOpposite = true;
}
// iterate Clockwise
var valClockwise = 0;
var cur = s[x];
for (var i = x; i <= y; i++) {
// if current bit is not equal
// to next index bit.
if (s[i] != cur) {
cur = s[i];
valClockwise++;
}
}
// iterate Anti-Clockwise
var valAnticlockwise = 0;
cur = s[y];
x += s.length;
for (var i = y; i <= x; i++) {
// if current bit is not equal
// to next index bit.
if (s[i] != cur) {
cur = s[i];
valAnticlockwise++;
}
}
// Finding whether Clockwise or Anti-clockwise
// path take minimum flip.
if (valClockwise <= valAnticlockwise) {
if (!isOpposite)
document.write( "Clockwise "
+ valClockwise + "<br>");
else
document.write( "Anti-clockwise "
+ valAnticlockwise + "<br>");
}
else {
if (!isOpposite)
document.write( "Anti-clockwise "
+ valAnticlockwise + "<br>");
else
document.write( "Clockwise "
+ valClockwise + "<br>");
}
}
// Driven Program
var x = 0, y = 8;
var s = "000110";
minimumFlip(s, x, y);
// This code is contributed by rrrtnx.
</script>
Producción:
Clockwise 2
Complejidad de tiempo: O(yx) + O(xy), donde x e y son proporcionados por el usuario
Espacio auxiliar: O(1), ya que no se usó espacio adicional