Dada una array binaria, podemos voltear todos los 1 que están en la parte izquierda y todos los 0 en la parte derecha. Calcule los giros mínimos requeridos para hacer todos los 1 a la izquierda y todos los 0 a la derecha.
Ejemplos:
Input: 1011000 Output: 1 1 flip is required to make it 1111000. Input : 00001 Output : 2 2 flips required to make it 10000.
Para resolver este problema utilizamos el enmascaramiento de bits. Primero, convertimos esta array en una string, luego encontramos el número decimal equivalente de esa string binaria. Probamos todas las máscaras con todas las posibilidades de 1 a la izquierda y 0 a la derecha. Iteramos un bucle hasta que el número decimal se convierte en cero. Cada vez haremos XOR bit a bit del número con máscara y el número de unos en el valor XOR será el número de vueltas requeridas. Disminuimos n en 1 y actualizamos la máscara.
- Tomar array binaria como entrada
- Convierta la array en string y luego el número decimal equivalente (num)
- Tome el valor de máscara inicial e itere hasta que num <= 0
- Encuentre los giros requeridos usando (máscara num XOR)
- Encuentre los giros mínimos y disminuya el número y actualice la máscara
- Devolver el conteo mínimo
Implementación:
C++
// C++ program to find
// of flips till that
// all 1s in left
#include <bits/stdc++.h>
using namespace std;
int countones(long n);
// Function to count minimum
// number of flips
int findMiniFlip(int nums[], int n)
{
string s = "";
for (int i = 0; i < n; i++)
s += nums[i];
char *end;
char tmp[s.length()];
strcpy(tmp, s.c_str());
// This is converting string
// s into integer of base 2
// (if s = '100' then num = 4)
long num = strtol(tmp, &end, 2);
// Initialize minXor
// with n that can be
// maximum number of flips
int minXor = n;
// right shift 1 by (n-1) bits
long mask = (1 << (n - 1));
while (n - 1 > 0)
{
// Calculate bitwise
// XOR of num and mask
long temp = (num ^ mask);
// Math.min(a, b) returns
// minimum of a and b
// return minimum number
// of flips till that digit
minXor = min(minXor, countones(temp));
n--;
mask = (mask | (1 << (n - 1)));
}
return minXor;
}
// Function to count number of 1s
int countones(long n)
{
int c = 0;
while (n > 0)
{
n = n & (n - 1);
c++;
}
return c;
}
// Driver code
int main()
{
int nums[] = {1, 0, 1,
1, 0, 0, 0};
int size = sizeof(nums) /
sizeof(nums[0]);
int n = findMiniFlip(nums, size);
cout << n;
}
// This code is contributed by Rutvik_56
Java
// Java program to find minimum flips to make
// all 1s in left
import java.io.*;
class GFG {
// function to count minimum number of flips
public static int findMiniFlip(int[] nums)
{
int n = nums.length;
String s = "";
for (int i = 0; i < n; i++)
s += nums[i];
// This is converting string s into integer
// of base 2 (if s = '100' then num = 4)
long num = Integer.parseInt(s, 2);
// initialize minXor with n that can be maximum
// number of flips
int minXor = n;
// right shift 1 by (n-1) bits
long mask = (1 << (n-1));
while (n-1 > 0) {
// calculate bitwise XOR of num and mask
long temp = (num ^ mask);
// Math.min(a, b) returns minimum of a and b
// return minimum number of flips till that
// digit
minXor = Math.min(minXor, countones(temp));
n--;
mask = (mask | (1 << n -1));
}
return minXor;
}
// function to count number of 1s
public static int countones(long n)
{
int c = 0;
while (n > 0) {
n = n & (n-1);
c++;
}
return c;
}
public static void main(String[] args)
{
int[] nums = { 1, 0, 1, 1, 0, 0, 0 };
int n = findMiniFlip(nums);
System.out.println(n);
}
}
Python3
# Python3 program to find minimum flips to make # all 1s in left # Function to count minimum number of flips def findMiniFlip(nums): n = len(nums) s = '' for i in range(n): s += str(nums[i]) # This is converting string s into integer # of base 2 (if s='100' then num=4) num = int(s, 2) # Initialize minXor with n that can be maximum # number of flips minXor = n; # Right shift 1 by(n-1) bits mask = (1 << (n - 1)) while (n - 1 > 0): # Calculate bitwise XOR of num and mask temp = (num ^ mask) # Math.min(a, b) returns minimum of a and b # return minimum number of flips till that # digit minXor = min(minXor, countones(temp)) n -= 1 mask = (mask | (1 << n - 1)) return minXor # Function to count number of 1s def countones(n): c = 0 while (n > 0): n = n & (n - 1) c += 1 return c # Driver code if __name__ == "__main__": nums = [ 1, 0, 1, 1, 0, 0, 0 ] n = findMiniFlip(nums) print(n) # This code is contributed by chitranayal
C#
// C# program to find
// minimum flips to make
// all 1s in left
using System;
class GFG{
// Function to count minimum
// number of flips
public static int findMiniFlip(int[] nums)
{
int n = nums.Length;
String s = "";
for (int i = 0; i < n; i++)
s += nums[i];
// This is converting string
// s into integer of base 2
// (if s = '100' then num = 4)
long num = Convert.ToInt32(s, 2);
// initialize minXor with n
// that can be maximum
// number of flips
int minXor = n;
// right shift 1 by (n-1) bits
long mask = (1 << (n - 1));
while (n - 1 > 0)
{
// calculate bitwise XOR
// of num and mask
long temp = (num ^ mask);
// Math.Min(a, b) returns
// minimum of a and b
// return minimum number
// of flips till that
// digit
minXor = Math.Min(minXor,
countones(temp));
n--;
mask = (mask | (1 << n - 1));
}
return minXor;
}
// Function to count number of 1s
public static int countones(long n)
{
int c = 0;
while (n > 0)
{
n = n & (n - 1);
c++;
}
return c;
}
// Driver code
public static void Main(String[] args)
{
int[] nums = {1, 0, 1, 1,
0, 0, 0};
int n = findMiniFlip(nums);
Console.WriteLine(n);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to find minimum
// flips to make all 1s in left
// Function to count minimum number of flips
function findMiniFlip(nums)
{
let n = nums.length;
let s = "";
for(let i = 0; i < n; i++)
s += nums[i];
// This is converting string s into integer
// of base 2 (if s = '100' then num = 4)
let num = parseInt(s, 2);
// Initialize minXor with n that
// can be maximum number of flips
let minXor = n;
// Right shift 1 by (n-1) bits
let mask = (1 << (n - 1));
while (n - 1 > 0)
{
// Calculate bitwise XOR of num and mask
let temp = (num ^ mask);
// Math.min(a, b) returns minimum of a and b
// return minimum number of flips till that
// digit
minXor = Math.min(minXor, countones(temp));
n--;
mask = (mask | (1 << n -1));
}
return minXor;
}
// Function to count number of 1s
function countones(n)
{
let c = 0;
while (n > 0)
{
n = n & (n - 1);
c++;
}
return c;
}
// Driver Code
let nums = [ 1, 0, 1, 1, 0, 0, 0 ];
let n = findMiniFlip(nums);
document.write(n);
// This code is contributed by code_hunt
</script>
Producción:
1
Complejidad temporal: O(n)
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por niteesh_Kr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA