Dado un número no negativo n y dos valores l y r . El problema es verificar si n tiene o no un patrón alternativo en su representación binaria en el rango de l a r . Aquí, patrón alternativo significa que los bits activados y desactivados ocurren en orden alternativo. Los bits se numeran de derecha a izquierda, es decir, se considera que el bit menos significativo está en la primera posición.
Restricción: 1 <= l <= r <= número de bits en la representación binaria de n .
Ejemplos:
Input : n = 18, l = 1, r = 3 Output : Yes (18)10 = (10010)2 The bits in the range 1 to 3 in the binary representation of 18 are in alternate order. Input : n = 22, l = 2, r = 4 Output : No (22)10 = (10110)2 The bits in the range 2 to 4 in the binary representation of 22 are not in alternate order.
Algoritmo:
bitsAreInAltPatrnInGivenTRange(n, l, r)
// Shift bits of given number n by
// (l-1).
num = n >> (l - 1)
// Find first bit of range
prev = num & 1
// Traverse through remaining
// bits. For every bit, check if
// current bit is same as previous
// or not.
num = num >> 1
for i = 1 to (r - l)
curr = num & 1
if curr == prev then
return false
prev = curr
num = num >> 1
return true;
C++
// C++ implementation to check whether bits are in
// alternate pattern in the given range
#include <bits/stdc++.h>
using namespace std;
// function to check whether bits are in
// alternate pattern in the given range
bool bitsAreInAltPatrnInGivenTRange(unsigned int n,
unsigned int l,
unsigned int r)
{
unsigned int num, prev, curr;
// right shift n by (l - 1) bits
num = n >> (l - 1);
// get the bit at the last position in 'num'
prev = num & 1;
// right shift 'num' by 1
num = num >> 1;
// loop until there are bits in the given range
for (int i = 1; i <= (r - l); i++) {
// get the bit at the last position in 'num'
curr = num & 1;
// if true, then bits are not in alternate
// pattern
if (curr == prev)
return false;
// update 'prev'
prev = curr;
// right shift 'num' by 1
num = num >> 1;
}
// bits are in alternate pattern in the
// given range
return true;
}
// Driver program to test above
int main()
{
unsigned int n = 18;
unsigned int l = 1, r = 3;
if (bitsAreInAltPatrnInGivenTRange(n, l, r))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation to check
// whether bits are in alternate
// pattern in the given range
class GFG
{
// function to check whether
// bits are in alternate
// pattern in the given range
static boolean bitsAreInAltPatrnInGivenTRange(int n,
int l, int r)
{
int num, prev, curr;
// right shift n by (l - 1) bits
num = n >> (l - 1);
// get the bit at the
// last position in 'num'
prev = num & 1;
// right shift 'num' by 1
num = num >> 1;
// loop until there are
// bits in the given range
for (int i = 1; i <= (r - l); i++)
{
// get the bit at the
// last position in 'num'
curr = num & 1;
// if true, then bits are
// not in alternate pattern
if (curr == prev)
return false;
// update 'prev'
prev = curr;
// right shift 'num' by 1
num = num >> 1;
}
// bits are in alternate
// pattern in the given range
return true;
}
// Driver Code
public static void main(String[] args)
{
int n = 18;
int l = 1, r = 3;
if (bitsAreInAltPatrnInGivenTRange(n, l, r))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by mits
Python3
# Python3 implementation to check
# whether bits are in alternate
# pattern in the given range
# function to check whether
# bits are in alternate
# pattern in the given range
def bitsAreInAltPatrnInGivenTRange(n, l, r):
# right shift n by (l - 1) bits
num = n >> (l - 1);
# get the bit at the
# last position in 'num'
prev = num & 1;
# right shift 'num' by 1
num = num >> 1;
# loop until there are
# bits in the given range
for i in range(1,(r - l)):
# get the bit at the
# last position in 'num'
curr = num & 1;
# if true, then bits are
# not in alternate pattern
if (curr == prev):
return False;
# update 'prev'
prev = curr;
# right shift 'num' by 1
num = num >> 1;
# bits are in alternate
# pattern in the given range
return True;
# Driver Code
if __name__ == "__main__":
n = 18;
l = 1;
r = 3;
if(bitsAreInAltPatrnInGivenTRange(n, l, r)):
print("Yes");
else:
print("No");
# This Code is contributed by mits
C#
// C# implementation to check
// whether bits are in alternate
// pattern in the given range
using System;
class GFG
{
// function to check whether
// bits are in alternate
// pattern in the given range
static bool bitsAreInAltPatrnInGivenTRange(int n,
int l, int r)
{
int num, prev, curr;
// right shift n by (l - 1) bits
num = n >> (l - 1);
// get the bit at the
// last position in 'num'
prev = num & 1;
// right shift 'num' by 1
num = num >> 1;
// loop until there are
// bits in the given range
for (int i = 1; i <= (r - l); i++)
{
// get the bit at the
// last position in 'num'
curr = num & 1;
// if true, then bits are
// not in alternate pattern
if (curr == prev)
return false;
// update 'prev'
prev = curr;
// right shift 'num' by 1
num = num >> 1;
}
// bits are in alternate
// pattern in the given range
return true;
}
// Driver Code
static void Main()
{
int n = 18;
int l = 1, r = 3;
if (bitsAreInAltPatrnInGivenTRange(n, l, r))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation to check
// whether bits are in alternate
// pattern in the given range
// function to check whether
// bits are in alternate
// pattern in the given range
function bitsAreInAltPatrnInGivenTRange($n, $l, $r)
{
// right shift n by (l - 1) bits
$num = $n >> ($l - 1);
// get the bit at the
// last position in 'num'
$prev = $num & 1;
// right shift 'num' by 1
$num = $num >> 1;
// loop until there are
// bits in the given range
for ($i = 1; $i <= ($r - $l); $i++)
{
// get the bit at the
// last position in 'num'
$curr = $num & 1;
// if true, then bits are
// not in alternate pattern
if ($curr == $prev)
return false;
// update 'prev'
$prev = $curr;
// right shift 'num' by 1
$num = $num >> 1;
}
// bits are in alternate
// pattern in the given range
return true;
}
// Driver Code
$n = 18;
$l = 1;
$r = 3;
if (bitsAreInAltPatrnInGivenTRange($n, $l, $r))
echo "Yes";
else
echo "No";
// This Code is contributed by mits
?>
Javascript
<script>
// Javascript implementation to check whether bits are in
// alternate pattern in the given range
// function to check whether bits are in
// alternate pattern in the given range
function bitsAreInAltPatrnInGivenTRange(n, l, r)
{
var num, prev, curr;
// right shift n by (l - 1) bits
num = n >> (l - 1);
// get the bit at the last position in 'num'
prev = num & 1;
// right shift 'num' by 1
num = num >> 1;
// loop until there are bits in the given range
for (var i = 1; i <= (r - l); i++) {
// get the bit at the last position in 'num'
curr = num & 1;
// if true, then bits are not in alternate
// pattern
if (curr == prev)
return false;
// update 'prev'
prev = curr;
// right shift 'num' by 1
num = num >> 1;
}
// bits are in alternate pattern in the
// given range
return true;
}
// Driver program to test above
var n = 18;
var l = 1, r = 3;
if (bitsAreInAltPatrnInGivenTRange(n, l, r))
document.write( "Yes");
else
document.write( "No");
// This code is contributed by rrrtnx.
</script>
Producción:
Yes
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA