Encuentra el n-ésimo número cuya representación binaria es un palíndromo. No considere los ceros iniciales, mientras considera la representación binaria. Considere el primer número cuya representación binaria es un palíndromo como 1, en lugar de 0
Ejemplos:
Input : 1 Output : 1 1st Number whose binary representation is palindrome is 1 (1) Input : 9 Output : 27 9th Number whose binary representation is palindrome is 27 (11011)
Método 1: Ingenuo
Un enfoque ingenuo sería atravesar todos los números enteros del 1 al 2^31 – 1 e incrementar el número de palíndromos, si el número es un palíndromo. Cuando el conteo de palíndromos alcance el n requerido, rompa el bucle y devuelva el entero actual.
C++
// C++ program to find n-th number whose binary
// representation is palindrome.
#include <bits/stdc++.h>
using namespace std;
// Finds if the kth bit is set in the binary
// representation
int isKthBitSet(int x, int k)
{
return (x & (1 << (k - 1))) ? 1 : 0;
}
// Returns the position of leftmost set bit
// in the binary representation
int leftmostSetBit(int x)
{
int count = 0;
while (x) {
count++;
x = x >> 1;
}
return count;
}
// Finds whether the integer in binary
// representation is palindrome or not
int isBinPalindrome(int x)
{
int l = leftmostSetBit(x);
int r = 1;
// One by one compare bits
while (l > r) {
// Compare left and right bits and converge
if (isKthBitSet(x, l) != isKthBitSet(x, r))
return 0;
l--;
r++;
}
return 1;
}
int findNthPalindrome(int n)
{
int pal_count = 0;
// Start from 1, traverse through
// all the integers
int i = 0;
for (i = 1; i <= INT_MAX; i++) {
if (isBinPalindrome(i)) {
pal_count++;
}
// If we reach n, break the loop
if (pal_count == n)
break;
}
return i;
}
// Driver code
int main()
{
int n = 9;
// Function Call
cout << findNthPalindrome(n);
}
// This code is contributed
// by Akanksha Rai
C
// C program to find n-th number whose binary
// representation is palindrome.
#include <stdio.h>
#define INT_MAX 2147483647
// Finds if the kth bit is set in the binary
// representation
int isKthBitSet(int x, int k)
{
return (x & (1 << (k - 1))) ? 1 : 0;
}
// Returns the position of leftmost set bit
// in the binary representation
int leftmostSetBit(int x)
{
int count = 0;
while (x) {
count++;
x = x >> 1;
}
return count;
}
// Finds whether the integer in binary
// representation is palindrome or not
int isBinPalindrome(int x)
{
int l = leftmostSetBit(x);
int r = 1;
// One by one compare bits
while (l > r) {
// Compare left and right bits and converge
if (isKthBitSet(x, l) != isKthBitSet(x, r))
return 0;
l--;
r++;
}
return 1;
}
int findNthPalindrome(int n)
{
int pal_count = 0;
// Start from 1, traverse through
// all the integers
int i = 0;
for (i = 1; i <= INT_MAX; i++) {
if (isBinPalindrome(i)) {
pal_count++;
}
// If we reach n, break the loop
if (pal_count == n)
break;
}
return i;
}
// Driver code
int main()
{
int n = 9;
// Function Call
printf("%d", findNthPalindrome(n));
}
Java
// Java program to find n-th
// number whose binary
// representation is palindrome.
import java.io.*;
class GFG {
static int INT_MAX = 2147483647;
// Finds if the kth bit
// is set in the binary
// representation
static int isKthBitSet(int x, int k)
{
return ((x & (1 << (k - 1))) > 0) ? 1 : 0;
}
// Returns the position of
// leftmost set bit in the
// binary representation
static int leftmostSetBit(int x)
{
int count = 0;
while (x > 0) {
count++;
x = x >> 1;
}
return count;
}
// Finds whether the integer
// in binary representation is
// palindrome or not
static int isBinPalindrome(int x)
{
int l = leftmostSetBit(x);
int r = 1;
// One by one compare bits
while (l > r) {
// Compare left and right
// bits and converge
if (isKthBitSet(x, l) != isKthBitSet(x, r))
return 0;
l--;
r++;
}
return 1;
}
static int findNthPalindrome(int n)
{
int pal_count = 0;
// Start from 1, traverse
// through all the integers
int i = 0;
for (i = 1; i <= INT_MAX; i++) {
if (isBinPalindrome(i) > 0) {
pal_count++;
}
// If we reach n,
// break the loop
if (pal_count == n)
break;
}
return i;
}
// Driver code
public static void main(String[] args)
{
int n = 9;
// Function Call
System.out.println(findNthPalindrome(n));
}
}
// This code is contributed
// by anuj_67.
Python3
# Python 3 program to find n-th number # whose binary representation is palindrome. INT_MAX = 2147483647 # Finds if the kth bit is set in # the binary representation def isKthBitSet(x, k): return 1 if (x & (1 << (k - 1))) else 0 # Returns the position of leftmost # set bit in the binary representation def leftmostSetBit(x): count = 0 while (x): count += 1 x = x >> 1 return count # Finds whether the integer in binary # representation is palindrome or not def isBinPalindrome(x): l = leftmostSetBit(x) r = 1 # One by one compare bits while (l > r): # Compare left and right bits # and converge if (isKthBitSet(x, l) != isKthBitSet(x, r)): return 0 l -= 1 r += 1 return 1 def findNthPalindrome(n): pal_count = 0 # Start from 1, traverse # through all the integers i = 0 for i in range(1, INT_MAX + 1): if (isBinPalindrome(i)): pal_count += 1 # If we reach n, break the loop if (pal_count == n): break return i # Driver code if __name__ == "__main__": n = 9 # Function Call print(findNthPalindrome(n)) # This code is contributed # by ChitraNayal
C#
// C# program to find n-th
// number whose binary
// representation is palindrome.
using System;
class GFG {
static int INT_MAX = 2147483647;
// Finds if the kth bit
// is set in the binary
// representation
static int isKthBitSet(int x, int k)
{
return ((x & (1 << (k - 1))) > 0) ? 1 : 0;
}
// Returns the position of
// leftmost set bit in the
// binary representation
static int leftmostSetBit(int x)
{
int count = 0;
while (x > 0) {
count++;
x = x >> 1;
}
return count;
}
// Finds whether the integer
// in binary representation is
// palindrome or not
static int isBinPalindrome(int x)
{
int l = leftmostSetBit(x);
int r = 1;
// One by one compare bits
while (l > r) {
// Compare left and right
// bits and converge
if (isKthBitSet(x, l) != isKthBitSet(x, r))
return 0;
l--;
r++;
}
return 1;
}
static int findNthPalindrome(int n)
{
int pal_count = 0;
// Start from 1, traverse
// through all the integers
int i = 0;
for (i = 1; i <= INT_MAX; i++) {
if (isBinPalindrome(i) > 0) {
pal_count++;
}
// If we reach n,
// break the loop
if (pal_count == n)
break;
}
return i;
}
// Driver code
static public void Main()
{
int n = 9;
// Function Call
Console.WriteLine(findNthPalindrome(n));
}
}
// This code is contributed ajit
PHP
<?php
// PHP program to find n-th number whose
// binary representation is palindrome.
// Finds if the kth bit is set in
// the binary representation
function isKthBitSet($x, $k)
{
return ($x & (1 << ($k - 1))) ? 1 : 0;
}
// Returns the position of leftmost set
// bit in the binary representation
function leftmostSetBit($x)
{
$count = 0;
while ($x)
{
$count++;
$x = $x >> 1;
}
return $count;
}
// Finds whether the integer in binary
// representation is palindrome or not
function isBinPalindrome($x)
{
$l = leftmostSetBit($x);
$r = 1;
// One by one compare bits
while ($l > $r)
{
// Compare left and right bits
// and converge
if (isKthBitSet($x, $l) !=
isKthBitSet($x, $r))
return 0;
$l--;
$r++;
}
return 1;
}
function findNthPalindrome($n)
{
$pal_count = 0;
// Start from 1, traverse through
// all the integers
$i = 0;
for ($i = 1; $i <= PHP_INT_MAX; $i++)
{
if (isBinPalindrome($i))
{
$pal_count++;
}
// If we reach n, break the loop
if ($pal_count == $n)
break;
}
return $i;
}
// Driver code
$n = 9;
// Function Call
echo (findNthPalindrome($n));
// This code is contributed by jit_t
?>
Javascript
<script>
// Javascript program to find n-th
// number whose binary
// representation is palindrome.
let INT_MAX = 2147483647;
// Finds if the kth bit
// is set in the binary
// representation
function isKthBitSet(x, k)
{
return ((x & (1 << (k - 1))) > 0) ? 1 : 0;
}
// Returns the position of
// leftmost set bit in the
// binary representation
function leftmostSetBit(x)
{
let count = 0;
while (x > 0)
{
count++;
x = x >> 1;
}
return count;
}
// Finds whether the integer
// in binary representation is
// palindrome or not
function isBinPalindrome(x)
{
let l = leftmostSetBit(x);
let r = 1;
// One by one compare bits
while (l > r)
{
// Compare left and right
// bits and converge
if (isKthBitSet(x, l) !=
isKthBitSet(x, r))
return 0;
l--;
r++;
}
return 1;
}
function findNthPalindrome(n)
{
let pal_count = 0;
// Start from 1, traverse
// through all the integers
let i = 0;
for(i = 1; i <= INT_MAX; i++)
{
if (isBinPalindrome(i) > 0)
{
pal_count++;
}
// If we reach n,
// break the loop
if (pal_count == n)
break;
}
return i;
}
// Driver code
let n = 9;
// Function Call
document.write(findNthPalindrome(n));
// This code is contributed by suresh07
</script>
Producción
27
La complejidad temporal de esta solución es O(x) donde x es un número resultante.
Tenga en cuenta que el valor de x es generalmente mucho mayor que n.
Método 2: Usar BFS
En este enfoque primero, simplemente agregamos «11» esta string a la cola. Y luego, para cada string, tenemos dos casos. es decir
- si la string actual tiene una longitud uniforme, agregue «0» y «1» a la mitad de la string actual y agréguela a la cola.
- si la string actual tiene una longitud impar, agregue el carácter medio de la string actual en la string resultante y luego agréguela a la cola.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find n-th palindrome
#include <bits/stdc++.h>
using namespace std;
// utility function which is used to
// convert binary string into integer
int convertStringToInt(string s)
{
int num = 0;
// convert binary string into integer
for (int i = 0; i < s.size(); i++) {
num = num * 2 + (s[i] - '0');
}
return num;
}
// function to find nth binary palindrome number
int getNthNumber(int n)
{
// base case
if (n == 1)
return 1;
n--;
// stores the binary palindrome string
queue<string> q;
// add 2nd binary palindrome string
q.push("11");
// runs till the nth binary palindrome number
while (!q.empty()) {
// remove curr binary palindrome string from queue
string curr = q.front();
q.pop();
n--;
// if n==0 then we find the n'th binary palindrome
// so we return our answer
if (!n) {
return convertStringToInt(curr);
}
int mid = curr.size() / 2;
// if length is even .so it is our first case
// we have two choices
if (curr.size() % 2 == 0) {
string s0 = curr, s1 = curr;
s0.insert(mid, "0");
s1.insert(mid, "1");
q.push(s0);
q.push(s1);
}
// if length is odd .so it is our second case
// we have only one choice
else {
string ch(1, curr[mid]);
string temp = curr;
temp.insert(mid, ch);
q.push(temp);
}
}
return 0;
}
// Driver Code
int main()
{
int n = 9;
// Function Call
cout << getNthNumber(n);
}
// This code is contributed by Sagar Jangra and Naresh
// Saharan
Java
// Java program to find n-th palindrome
import java.io.*;
import java.util.*;
class GFG {
// utility function which is used to
// convert binary string into integer
public static int convertStringToInt(String s)
{
int ans = 0;
// convert binary string into integer
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1')
ans += 1 << i;
}
return ans;
}
// function to find nth binary palindrome number
public static int getNthNumber(int n)
{
// stores the binary palindrome string
Queue<String> q = new LinkedList<>();
// base case
if (n == 1)
return 1;
n = n - 1;
// add 2nd binary palindrome string
q.add("11");
// runs till the nth binary palindrome number
while (n-- > 0) {
// remove curr binary palindrome string from
// queue
String curr = q.remove();
// if n==0 then we find the n'th binary
// palindrome so we return our answer
if (n == 0)
return convertStringToInt(curr);
// calculate length of curr binary palindrome
// string
int len = curr.length();
// if length is even .so it is our first case
// we have two choices
if (len % 2 == 0) {
q.add(curr.substring(0, len / 2) + "0"
+ curr.substring(len / 2));
q.add(curr.substring(0, len / 2) + "1"
+ curr.substring(len / 2));
}
// if length is odd .so it is our second case
// we have only one choice
else {
char midChar = curr.charAt(len / 2);
q.add(curr.substring(0, len / 2) + midChar
+ curr.substring(len / 2));
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int n = 9;
// Function Call
System.out.println(getNthNumber(n));
}
}
// This code is contributed by Naresh Saharan and Sagar
// Jangra
Python3
# Python program to find n-th palindrome
# utility function which is used to
# convert binary string into integer
def convertStringToInt(s):
ans = 0
# convert binary string into integer
for i in range(len(s)):
ans = ans * 2 + (ord(s[i]) - ord('0'))
return ans
# function to find nth binary palindrome number
def getNthNumber(n):
# stores the binary palindrome string
q = []
# base case
if(n == 1):
return 1
n = n - 1
# add 2nd binary palindrome string
q.append("11")
# runs till the nth binary palindrome number
while(len(q) != 0):
# remove curr binary palindrome string from
# queue
curr = q.pop(0)
n -= 1
# if n==0 then we find the n'th binary
# palindrome so we return our answer
if(n ==0):
return convertStringToInt(curr)
# calculate length of curr binary palindrome
# string
lenn = len(curr)
# if length is even .so it is our first case
# we have two choices
if (len(curr) % 2 == 0):
q.append(curr[0:int(lenn/2)]+"0"+curr[int(lenn/2):])
q.append(curr[0:int(lenn/2)]+"1"+curr[int(lenn/2):])
# if length is odd .so it is our second case
# we have only one choice
else:
midChar = curr[int(lenn/2)]
q.append(curr[0:int(lenn/2)]+midChar+curr[int(lenn/2):])
return 0
# Driver code
n = 9
# Function Call
print(getNthNumber(n))
# This code is contributed by avanitrachhadiya2155
C#
// C# program to find n-th palindrome
using System;
using System.Collections.Generic;
class GFG{
// Utility function which is used to
// convert binary string into integer
public static int convertStringToInt(String s)
{
int ans = 0;
// Convert binary string into integer
for(int i = 0; i < s.Length; i++)
{
if (s[i] == '1')
ans += 1 << i;
}
return ans;
}
// Function to find nth binary palindrome number
public static int getNthNumber(int n)
{
// Stores the binary palindrome string
Queue<String> q = new Queue<String>();
// Base case
if (n == 1)
return 1;
n = n - 1;
// Add 2nd binary palindrome string
q.Enqueue("11");
// Runs till the nth binary palindrome number
while (n-- > 0)
{
// Remove curr binary palindrome
// string from queue
String curr = q.Dequeue();
// If n==0 then we find the n'th binary
// palindrome so we return our answer
if (n == 0)
return convertStringToInt(curr);
// Calculate length of curr binary palindrome
// string
int len = curr.Length;
// If length is even .so it is our first case
// we have two choices
if (len % 2 == 0)
{
q.Enqueue(curr.Substring(0, len / 2) + "0" +
curr.Substring(len / 2));
q.Enqueue(curr.Substring(0, len / 2) + "1" +
curr.Substring(len / 2));
}
// If length is odd .so it is our second case
// we have only one choice
else
{
char midChar = curr[len / 2];
q.Enqueue(curr.Substring(0, len / 2) + midChar +
curr.Substring(len / 2));
}
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int n = 9;
// Function Call
Console.WriteLine(getNthNumber(n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find n-th palindrome
// utility function which is used to
// convert binary string into integer
function convertStringToInt(s)
{
let ans = 0;
// convert binary string into integer
for (let i = 0; i < s.length; i++) {
if (s[i] == '1')
ans += 1 << i;
}
return ans;
}
// function to find nth binary palindrome number
function getNthNumber(n)
{
// stores the binary palindrome string
let q = [];
// base case
if (n == 1)
return 1;
n = n - 1;
// add 2nd binary palindrome string
q.push("11");
// runs till the nth binary palindrome number
while (n-- > 0) {
// remove curr binary palindrome string from
// queue
let curr = q.shift();
// if n==0 then we find the n'th binary
// palindrome so we return our answer
if (n == 0)
return convertStringToInt(curr);
// calculate length of curr binary palindrome
// string
let len = curr.length;
let len2 = Math.floor(len / 2);
// if length is even .so it is our first case
// we have two choices
if (len % 2 == 0) {
q.push(curr.substring(0, len2) + "0"
+ curr.substring(len2));
q.push(curr.substring(0, len2) + "1"
+ curr.substring(len2));
}
// if length is odd .so it is our second case
// we have only one choice
else {
let midChar = curr[len2];
q.push(curr.substring(0, len2) + midChar
+ curr.substring(len2));
}
}
return -1;
}
// Driver code
let n = 9;
// Function Call
document.write(getNthNumber(n));
// This code is contributed by ab2127
</script>
Producción
27
Complejidad temporal: O(N)
Complejidad espacial: O(N)
Método 3: Construcción del enésimo palíndromo
Podemos construir el palíndromo binario enésimo en su representación binaria directamente usando el siguiente enfoque.
Si observamos los primeros palíndromos binarios
* | nth Binary |
n | Palindrome | Group
| |
--------------------------- Group 0
1 ---> 1 (1)
Group 1 (Will have binary representation of length 2*(1)
and 2*(1) + 1)
Fix the first and last bit as 1 and insert nothing
(|) in between. Length is 2*(1)
2 ---> 1|1 (3)
Fix the first and last bit as 1 and insert bit 0
in between. Length is 2*(1) + 1
3 ---> 101 (5)
Fix the first and last bit as 1 and insert bit 1
in between. Length is 2*(1) + 1
4 ---> 111 (7)
F
Group 2 (Will have binary representation of length
2*(2) and 2*(2) + 1). Fix the first and last
bit as 1 and insert nothing (|) at middle.
And put 0 in binary format in both directions
from middle. Length is 2*(2)
5 ---> 10|01
Fix the first and last bit as 1 and insert
nothing (|) at middle. And put 1 in binary
format in both directions from middle.
Length is 2*(2)
6 ---> 11|11
7 ---> 10001
8 ---> 10101
9 ---> 11011
10 ---> 11111
Group 3 (Will have binary representation of
length 2*(3) and 2*(3) + 1)
11 ---> 100|001
12 ---> 101|101
13 ---> 110|011
14 ---> 111|111
15 ---> 1000001
16 ---> 1001001
17 ---> 1010101
18 ---> 1011101
19 ---> 1100011
20 ---> 1101011
21 ---> 1110111
22 ---> 1111111
--------------------
Algoritmo:
1) Podemos dividir el conjunto de números palíndromos en algunos grupos.
2) el n-ésimo grupo tendrá (2^(n-1) + 2^n = 3 * 2 ^(n-1) ) número de palíndromos binarios
3) Con el número dado, podemos encontrar el grupo al que pertenece pertenece y el desplazamiento en ese grupo.
4) Como no se van a considerar los ceros iniciales, deberíamos usar el bit 1 como bit inicial y bit final del número en representación binaria
5) Y llenaremos otros bits basados en groupno y groupoffset
6) Basados en offset, podemos encontrar qué bit debe insertarse en el medio (|(nada) o 0 o 1) y
qué número (en forma binaria) (1 o 2 o 3 o 4 o ..) debe colocarse en ambas direcciones desde la mitad
Considere el siguiente ejemplo
Let us construct the 8th binary palindrome number
The group number will be 2, and no.of elements
before that group are 1 + 3 * 2^1 which is 4
So the offset for the 8th element will be 8 - 4
- 1 = 3
And first 2^(groupno - 1) = 2^1, elements will
have even length(in binary representation) of
2*groupno, next 2^groupno elements will have odd
length(in binary representation) of 2*groupno + 1
Place bit 1 as the first bit and as the last bit
(firstbit: 0, last bit: 2*groupno or 2*groupno - 1)
As the offset is 3, 4th(3 + 1) element in the
group, will have odd length and have 1 in the
middle
Below is the table of middle bit to be used for
the given offset for the group 2
offset middle bit
0 |
1 |
2 0
3 1
4 0
5 1
And we should be filling the binary representation
of number 0(((groupoffset) - 2^(groupno-1)) /2)
from middle n both directions
1 0 1 0 1
FirstElement Number MiddleElement Number LastElement
1 0 1 0 1
The 8th number will be 21
A continuación se muestra la implementación de la idea anterior:
C++
// Efficient C++ program to find n-th palindrome
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Construct the nth binary palindrome with the
// given group number, aux_number and operation
// type
int constructNthNumber(int group_no, int aux_num, int op)
{
int INT_SIZE = 32 ;
int a[INT_SIZE] = { 0 };
int num = 0, len_f;
int i = 0;
// No need to insert any bit in the middle
if (op == 2)
{
// Length of the final binary representation
len_f = 2 * group_no;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
// Start filling the a[] from middle,
// with the aux_num binary representation
while (aux_num)
{
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Insert bit 0 in the middle
else if (op == 0)
{
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 0;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num)
{
// Get the auxiliary number's ith bit
// and fill around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Insert bit 1 in the middle
else
{
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 1;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num)
{
// Get the auxiliary number's ith bit
// and fill around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Convert the number to decimal from binary
for(i = 0; i < len_f; i++)
num += (1 << i) * a[i];
return num;
}
// Will return the nth binary palindrome number
int getNthNumber(int n)
{
int group_no = 0, group_offset;
int count_upto_group = 0, count_temp = 1;
int op, aux_num;
// Add number of elements in all the groups,
// until the group of the nth number is found
while (count_temp < n)
{
group_no++;
// Total number of elements until this group
count_upto_group = count_temp;
count_temp += 3 * (1 << (group_no - 1));
}
// Element's offset position in the group
group_offset = n - count_upto_group - 1;
// Finding which bit to be placed in the
// middle and finding the number, which we
// will fill from the middle in both
// directions
if ((group_offset + 1) <= (1 << (group_no - 1)))
{
// No need to put extra bit in middle
op = 2;
// We need to fill this auxiliary number
// in binary form the middle in both directions
aux_num = group_offset;
}
else
{
if (((group_offset + 1) -
(1 << (group_no - 1))) % 2)
// Need to Insert 0 at middle
op = 0;
else
// Need to Insert 1 at middle
op = 1;
aux_num = ((group_offset) -
(1 << (group_no - 1))) / 2;
}
return constructNthNumber(group_no, aux_num, op);
}
// Driver code
int main()
{
int n = 9;
// Function Call
cout << getNthNumber(n) ;
return 0;
}
// This code is contributed by Khushboogoyal499
C
// Efficient C program to find n-th palindrome
#include <stdio.h>
#define INT_SIZE 32
// Construct the nth binary palindrome with the
// given group number, aux_number and operation
// type
int constructNthNumber(int group_no, int aux_num, int op)
{
int a[INT_SIZE] = { 0 };
int num = 0, len_f;
int i = 0;
// No need to insert any bit in the middle
if (op == 2) {
// Length of the final binary representation
len_f = 2 * group_no;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
// Start filling the a[] from middle,
// with the aux_num binary representation
while (aux_num) {
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Insert bit 0 in the middle
else if (op == 0) {
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 0;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num) {
// Get the auxiliary number's ith bit and fill
// around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
else // Insert bit 1 in the middle
{
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 1;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num) {
// Get the auxiliary number's ith bit and fill
// around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Convert the number to decimal from binary
for (i = 0; i < len_f; i++)
num += (1 << i) * a[i];
return num;
}
// Will return the nth binary palindrome number
int getNthNumber(int n)
{
int group_no = 0, group_offset;
int count_upto_group = 0, count_temp = 1;
int op, aux_num;
// Add number of elements in all the groups,
// until the group of the nth number is found
while (count_temp < n) {
group_no++;
// Total number of elements until this group
count_upto_group = count_temp;
count_temp += 3 * (1 << (group_no - 1));
}
// Element's offset position in the group
group_offset = n - count_upto_group - 1;
// Finding which bit to be placed in the
// middle and finding the number, which we
// will fill from the middle in both
// directions
if ((group_offset + 1) <= (1 << (group_no - 1))) {
op = 2; // No need to put extra bit in middle
// We need to fill this auxiliary number
// in binary form the middle in both directions
aux_num = group_offset;
}
else {
if (((group_offset + 1)
- (1 << (group_no - 1))) % 2)
op = 0; // Need to Insert 0 at middle
else
op = 1; // Need to Insert 1 at middle
aux_num
= ((group_offset) - (1 << (group_no - 1))) / 2;
}
return constructNthNumber(group_no, aux_num, op);
}
// Driver code
int main()
{
int n = 9;
// Function Call
printf("%d", getNthNumber(n));
return 0;
}
Java
// Efficient Java program to find n-th palindrome
class GFG {
static int INT_SIZE = 32;
// Construct the nth binary palindrome with the
// given group number, aux_number and operation
// type
static int constructNthNumber(int group_no, int aux_num,
int op)
{
int a[] = new int[INT_SIZE];
int num = 0, len_f;
int i = 0;
// No need to insert any bit in the middle
if (op == 2) {
// Length of the final binary representation
len_f = 2 * group_no;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
// Start filling the a[] from middle,
// with the aux_num binary representation
while (aux_num > 0) {
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Insert bit 0 in the middle
else if (op == 0) {
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 0;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num > 0) {
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
else // Insert bit 1 in the middle
{
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 1;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num > 0) {
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Convert the number to decimal from binary
for (i = 0; i < len_f; i++)
num += (1 << i) * a[i];
return num;
}
// Will return the nth binary palindrome number
static int getNthNumber(int n)
{
int group_no = 0, group_offset;
int count_upto_group = 0, count_temp = 1;
int op, aux_num;
// Add number of elements in all the groups,
// until the group of the nth number is found
while (count_temp < n) {
group_no++;
// Total number of elements until this group
count_upto_group = count_temp;
count_temp += 3 * (1 << (group_no - 1));
}
// Element's offset position in the group
group_offset = n - count_upto_group - 1;
// Finding which bit to be placed in the
// middle and finding the number, which we
// will fill from the middle in both
// directions
if ((group_offset + 1) <= (1 << (group_no - 1))) {
op = 2; // No need to put extra bit in middle
// We need to fill this auxiliary number
// in binary form the middle in both directions
aux_num = group_offset;
}
else {
if (((group_offset + 1)
- (1 << (group_no - 1))) % 2 == 1)
op = 0; // Need to Insert 0 at middle
else
op = 1; // Need to Insert 1 at middle
aux_num
= ((group_offset)
- (1 << (group_no - 1))) / 2;
}
return constructNthNumber(group_no, aux_num, op);
}
// Driver code
public static void main(String[] args)
{
int n = 9;
// Function Call
System.out.printf("%d", getNthNumber(n));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Efficient Python3 program to find n-th palindrome INT_SIZE = 32 # Construct the nth binary palindrome with the # given group number, aux_number and operation type def constructNthNumber(group_no, aux_num, op): a = [0] * INT_SIZE num, i = 0, 0 # No need to insert any bit in the middle if op == 2: # Length of the final binary representation len_f = 2 * group_no # Fill first and last bit as 1 a[len_f - 1] = a[0] = 1 # Start filling the a[] from middle, # with the aux_num binary representation while aux_num: # Get the auxiliary number's ith # bit and fill around middle a[group_no + i] = a[group_no - 1 - i] = \ aux_num & 1 aux_num = aux_num >> 1 i += 1 # Insert bit 0 in the middle else if op == 0: # Length of the final binary representation len_f = 2 * group_no + 1 # Fill first and last bit as 1 a[len_f - 1] = a[0] = 1 a[group_no] = 0 # Start filling the a[] from middle, with # the aux_num binary representation while aux_num: # Get the auxiliary number's ith # bit and fill around middle a[group_no + 1 + i] = a[group_no - 1 - i] = \ aux_num & 1 aux_num = aux_num >> 1 i += 1 else: # Insert bit 1 in the middle # Length of the final binary representation len_f = 2 * group_no + 1 # Fill first and last bit as 1 a[len_f - 1] = a[0] = 1 a[group_no] = 1 # Start filling the a[] from middle, with # the aux_num binary representation while aux_num: # Get the auxiliary number's ith # bit and fill around middle a[group_no + 1 + i] = a[group_no - 1 - i] = \ aux_num & 1 aux_num = aux_num >> 1 i += 1 # Convert the number to decimal from binary for i in range(0, len_f): num += (1 << i) * a[i] return num # Will return the nth binary palindrome number def getNthNumber(n): group_no = 0 count_upto_group, count_temp = 0, 1 # Add number of elements in all the groups, # until the group of the nth number is found while count_temp < n: group_no += 1 # Total number of elements until this group count_upto_group = count_temp count_temp += 3 * (1 << (group_no - 1)) # Element's offset position in the group group_offset = n - count_upto_group - 1 # Finding which bit to be placed in the # middle and finding the number, which we # will fill from the middle in both directions if (group_offset + 1) <= (1 << (group_no - 1)): op = 2 # No need to put extra bit in middle # We need to fill this auxiliary number # in binary form the middle in both directions aux_num = group_offset else: if (((group_offset + 1) - (1 << (group_no - 1))) % 2): op = 0 # Need to Insert 0 at middle else: op = 1 # Need to Insert 1 at middle aux_num = (((group_offset) - (1 << (group_no - 1))) // 2) return constructNthNumber(group_no, aux_num, op) # Driver code if __name__ == "__main__": n = 9 # Function Call print(getNthNumber(n)) # This code is contributed by Rituraj Jain
C#
// Efficient C# program to find n-th palindrome
using System;
class GFG {
static int INT_SIZE = 32;
// Construct the nth binary palindrome with the
// given group number, aux_number and operation
// type
static int constructNthNumber(int group_no, int aux_num,
int op)
{
int[] a = new int[INT_SIZE];
int num = 0, len_f;
int i = 0;
// No need to insert any bit in the middle
if (op == 2) {
// Length of the final binary representation
len_f = 2 * group_no;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
// Start filling the a[] from middle,
// with the aux_num binary representation
while (aux_num > 0) {
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + i] = a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Insert bit 0 in the middle
else if (op == 0) {
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 0;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num > 0) {
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + 1 + i] = a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
else // Insert bit 1 in the middle
{
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 1;
// Start filling the a[] from middle, with
// the aux_num binary representation
while (aux_num > 0) {
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + 1 + i] = a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Convert the number to decimal from binary
for (i = 0; i < len_f; i++)
num += (1 << i) * a[i];
return num;
}
// Will return the nth binary palindrome number
static int getNthNumber(int n)
{
int group_no = 0, group_offset;
int count_upto_group = 0, count_temp = 1;
int op, aux_num;
// Add number of elements in all the groups,
// until the group of the nth number is found
while (count_temp < n) {
group_no++;
// Total number of elements until this group
count_upto_group = count_temp;
count_temp += 3 * (1 << (group_no - 1));
}
// Element's offset position in the group
group_offset = n - count_upto_group - 1;
// Finding which bit to be placed in the
// middle and finding the number, which we
// will fill from the middle in both
// directions
if ((group_offset + 1) <= (1 << (group_no - 1))) {
op = 2; // No need to put extra bit in middle
// We need to fill this auxiliary number
// in binary form the middle in both directions
aux_num = group_offset;
}
else {
if (((group_offset + 1) - (1 << (group_no - 1)))
% 2
== 1)
op = 0; // Need to Insert 0 at middle
else
op = 1; // Need to Insert 1 at middle
aux_num
= ((group_offset) - (1 << (group_no - 1)))
/ 2;
}
return constructNthNumber(group_no, aux_num, op);
}
// Driver code
public static void Main(String[] args)
{
int n = 9;
// Function Call
Console.Write("{0}", getNthNumber(n));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// Efficient PHP program to find n-th palindrome
$INT_SIZE=32;
/* Construct the nth binary palindrome with the
given group number, aux_number and operation
type */
function constructNthNumber($group_no, $aux_num,$op)
{
global $INT_SIZE;
$a=array_fill(0,$INT_SIZE,0);
$num = 0;
$i = 0;
$len_f=0;
// No need to insert any bit in the middle
if ($op == 2)
{
// Length of the final binary representation
$len_f = 2 * $group_no;
// Fill first and last bit as 1
$a[$len_f - 1] = $a[0] = 1;
/* Start filling the a[] from middle,
with the aux_num binary representation */
while ($aux_num)
{
// Get the auxiliary number's ith bit and
// fill around middle
$a[$group_no + i] = $a[$group_no - 1 - $i]
= $aux_num & 1;
$aux_num = $aux_num >> 1;
$i++;
}
}
// Insert bit 0 in the middle
else if ($op == 0)
{
// Length of the final binary representation
$len_f = 2 * $group_no + 1;
// Fill first and last bit as 1
$a[$len_f - 1] = $a[0] = 1;
$a[$group_no] = 0;
/* Start filling the a[] from middle, with
the aux_num binary representation */
while ($aux_num)
{
// Get the auxiliary number's ith bit and fill
// around middle
$a[$group_no + 1 + $i] = $a[$group_no - 1 - $i]
= $aux_num & 1;
$aux_num = $aux_num >> 1;
$i++;
}
}
else // Insert bit 1 in the middle
{
// Length of the final binary representation
$len_f = 2 * $group_no + 1;
// Fill first and last bit as 1
$a[$len_f - 1] = $a[0] = 1;
$a[$group_no] = 1;
/* Start filling the a[] from middle, with
the aux_num binary representation */
while ($aux_num)
{
// Get the auxiliary number's ith bit and fill
// around middle
$a[$group_no + 1 + $i] = $a[$group_no - 1 - $i]
= $aux_num & 1;
$aux_num = $aux_num >> 1;
$i++;
}
}
/* Convert the number to decimal from binary */
for ($i = 0; $i < $len_f; $i++)
$num += (1 << $i) * $a[$i];
return $num;
}
/* Will return the nth binary palindrome number */
function getNthNumber($n)
{
$group_no = 0;
$count_upto_group = 0;
$count_temp = 1;
$op=$aux_num=0;
/* Add number of elements in all the groups,
until the group of the nth number is found */
while ($count_temp < $n)
{
$group_no++;
// Total number of elements until this group
$count_upto_group = $count_temp;
$count_temp += 3 * (1 << ($group_no - 1));
}
// Element's offset position in the group
$group_offset = $n - $count_upto_group - 1;
/* Finding which bit to be placed in the
middle and finding the number, which we
will fill from the middle in both
directions */
if (($group_offset + 1) <= (1 << ($group_no - 1)))
{
$op = 2; // No need to put extra bit in middle
// We need to fill this auxiliary number
// in binary form the middle in both directions
$aux_num = $group_offset;
}
else
{
if ((($group_offset + 1) - (1 << ($group_no - 1))) % 2)
$op = 0; // Need to Insert 0 at middle
else
$op = 1; // Need to Insert 1 at middle
$aux_num = (int)((($group_offset) - (1 << ($group_no - 1))) / 2);
}
return constructNthNumber($group_no, $aux_num, $op);
}
// Driver code
$n = 9;
// Function Call
print(getNthNumber($n));
// This code is contributed by mits
?>
Javascript
<script>
// Efficient javascript program to find n-th palindrome
var INT_SIZE = 32;
// Construct the nth binary palindrome with the
// given group number, aux_number and operation
// type
function constructNthNumber(group_no , aux_num,op)
{
var a = Array.from({length: INT_SIZE}, (_, i) => 0);
var num = 0, len_f=0;
var i = 0;
// No need to insert any bit in the middle
if (op == 2)
{
// Length of the final binary representation
len_f = 2 * group_no;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
// Start filling the a from middle,
// with the aux_num binary representation
while (aux_num > 0)
{
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Insert bit 0 in the middle
else if (op == 0)
{
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 0;
// Start filling the a from middle, with
// the aux_num binary representation
while (aux_num > 0)
{
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Insert bit 1 in the middle
else
{
// Length of the final binary representation
len_f = 2 * group_no + 1;
// Fill first and last bit as 1
a[len_f - 1] = a[0] = 1;
a[group_no] = 1;
// Start filling the a from middle, with
// the aux_num binary representation
while (aux_num > 0)
{
// Get the auxiliary number's ith bit and
// fill around middle
a[group_no + 1 + i]
= a[group_no - 1 - i]
= aux_num & 1;
aux_num = aux_num >> 1;
i++;
}
}
// Convert the number to decimal from binary
for(i = 0; i < len_f; i++)
num += (1 << i) * a[i];
return num;
}
// Will return the nth binary palindrome number
function getNthNumber(n)
{
var group_no = 0, group_offset;
var count_upto_group = 0, count_temp = 1;
var op, aux_num;
// Add number of elements in all the groups,
// until the group of the nth number is found
while (count_temp < n)
{
group_no++;
// Total number of elements until this group
count_upto_group = count_temp;
count_temp += 3 * (1 << (group_no - 1));
}
// Element's offset position in the group
group_offset = n - count_upto_group - 1;
// Finding which bit to be placed in the
// middle and finding the number, which we
// will fill from the middle in both
// directions
if ((group_offset + 1) <= (1 << (group_no - 1)))
{
// No need to put extra bit in middle
op = 2;
// We need to fill this auxiliary number
// in binary form the middle in both directions
aux_num = group_offset;
}
else
{
if (((group_offset + 1) -
(1 << (group_no - 1))) % 2 == 1)
// Need to Insert 0 at middle
op = 0;
else
// Need to Insert 1 at middle
op = 1;
aux_num = ((group_offset) -
(1 << (group_no - 1))) / 2;
}
return constructNthNumber(group_no, aux_num, op);
}
// Driver code
var n = 9;
// Function Call
document.write(getNthNumber(n));
// This code is contributed by Princi Singh
</script>
Producción
27
Complejidad Temporal: O(1).
Referencia:
https://www.codeproject.com/Articles/1162038/Finding-nth-Binary-Palindrome-in-Csharp
Este artículo es una contribución de Kamesh Relangi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeek y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA