Dado que N persona (numerada del 1 al N) está de pie como para formar un círculo. Todos tienen el arma en la mano que apunta a su compañero más a la izquierda.
Cada uno dispara de tal manera que 1 dispara a 2, 3 dispara a 4, 5 dispara a 6…. (N-1) el brote N (si N es par, de lo contrario N dispara 1).
Nuevamente, en la segunda iteración, disparan el resto de los restos como la lógica mencionada anteriormente (ahora para n como par, 1 disparará a 3, 5 disparará a 7 y así sucesivamente).
La tarea es encontrar qué persona es la más afortunada (no murió)?
Ejemplos :
Entrada: N = 3
Salida: 3
Como N = 3, 1 disparará a 2, 3 disparará a 1, por lo que 3 es la persona más afortunada.Entrada: N = 8
Salida: 1
Aquí como N = 8, 1 disparará 1, 3 disparará 4, 5 disparará 6, 7 disparará 8, De nuevo 1 disparará 3, 5 disparará 7, De nuevo 1 disparará 5 y por lo tanto 1 es la persona más afortunada.
Este problema ya ha sido discutido en Persona viva con suerte en un círculo | Solución de código para el rompecabezas de la espada . En esta publicación, se discute un enfoque diferente.
Acercarse:
- Tome el equivalente binario de N.
- Encuentre su complemento a 1 y convierta su número decimal igual N`.
- encontrar |N – N`|.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to convert string to number
int stringToNum(string s)
{
// object from the class stringstream
stringstream geek(s);
// The object has the value 12345 and stream
// it to the integer x
int x = 0;
geek >> x;
return x;
}
// Function to convert binary to decimal
int binaryToDecimal(string n)
{
int num = stringToNum(n);
int dec_value = 0;
// Initializing base value to 1, i.e 2^0
int base = 1;
int temp = num;
while (temp) {
int last_digit = temp % 10;
temp = temp / 10;
dec_value += last_digit * base;
base = base * 2;
}
return dec_value;
}
string itoa(int num, string str, int base)
{
int i = 0;
bool isNegative = false;
/* Handle 0 explicitly, otherwise
empty string is printed for 0 */
if (num == 0) {
str[i++] = '0';
return str;
}
// In standard itoa(), negative numbers
// are handled only with base 10.
// Otherwise numbers are considered unsigned.
if (num < 0 && base == 10) {
isNegative = true;
num = -num;
}
// Process individual digits
while (num != 0) {
int rem = num % base;
str[i++] = (rem > 9) ? (rem - 10) + 'a' : rem + '0';
num = num / base;
}
// If the number is negative, append '-'
if (isNegative)
str[i++] = '-';
// Reverse the string
reverse(str.begin(), str.end());
return str;
}
char flip(char c)
{
return (c == '0') ? '1' : '0';
}
// Function to find the ones complement
string onesComplement(string bin)
{
int n = bin.length(), i;
string ones = "";
// for ones complement flip every bit
for (i = 0; i < n; i++)
ones += flip(bin[i]);
return ones;
}
// Driver code
int main()
{
// Taking the number of a person
// standing in a circle.
int N = 3;
string arr = "";
// Storing the binary equivalent in a string.
string ans(itoa(N, arr, 2));
// taking one's compelement and
// convert it to decimal value
int N_dash = binaryToDecimal(onesComplement(ans));
int luckiest_person = N - N_dash;
cout << luckiest_person;
return 0;
}
Javascript
// JavaScript implementation of the above approach
// Function to convert string to number
function stringToNum(s)
{
return parseInt(s);
}
// Function to convert binary to decimal integer
function binaryToDecimal(n)
{
let num = stringToNum(n);
let dec_value = 0;
// Initializing base value to 1, i.e 2^0
let base = 1;
let temp = num;
while (temp) {
let last_digit = temp % 10;
temp = Math.floor(temp / 10);
dec_value += last_digit * base;
base = base * 2;
}
return dec_value;
}
function itoa(num, str, base)
{
let i = 0;
let isNegative = false;
str = str.split("");
/* Handle 0 explicitly, otherwise
empty string is printed for 0 */
if (num == 0) {
str[i++] = '0';
return str.join("");
}
// In standard itoa(), negative numbers
// are handled only with base 10.
// Otherwise numbers are considered unsigned.
if (num < 0 && base == 10) {
isNegative = true;
num = -num;
}
// Process individual digits
while (num != 0) {
let rem = num % base;
str[i++] = (rem > 9) ? (rem - 10): rem;
num = Math.floor(num / base);
}
// If the number is negative, append '-'
if (isNegative)
str[i++] = '-';
// Reverse the string
str.reverse();
return str.join("");
}
function flip(c)
{
return (c == '0') ? '1' : '0';
}
// Function to find the ones complement
function onesComplement(bin)
{
let n = bin.length;
let i;
let ones = "";
// for ones complement flip every bit
for (i = 0; i < n; i++)
ones += flip(bin[i]);
return ones;
}
// Driver code
// Taking the number of a person
// standing in a circle.
let N = 3;
let arr = "";
// Storing the binary equivalent in a string.
let ans = itoa(N, arr, 2);
// taking one's compelement and
// convert it to decimal value
let N_dash = binaryToDecimal(onesComplement(ans));
let luckiest_person = N - N_dash;
console.log(luckiest_person);
// This code is contributed by phasing17
Producción
3
Implementación alternativa más corta:
el enfoque utilizado aquí es el mismo.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
int luckiest_person(int n)
{
// to calculate the number of bits in
// the binary equivalent of n
int len = log2(n) + 1;
// Finding complement by inverting the
// bits one by one from last
int n2 = n;
for (int i = 0; i < len; i++) {
// XOR of n2 with (1<<i) to flip
// the last (i+1)th bit of binary equivalent of n2
n2 = n2 ^ (1 << i);
}
// n2 will be the one's complement of n
return abs(n - n2);
}
int main()
{
int N = 3;
int lucky_p = luckiest_person(N);
cout << lucky_p;
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
class GFG {
static int luckiest_person(int n)
{
// To calculate the number of bits in
// the binary equivalent of n
int len = (int)(Math.log(n) / Math.log(2)) + 1;
// Finding complement by inverting the
// bits one by one from last
int n2 = n;
for (int i = 0; i < len; i++) {
// XOR of n2 with (1<<i) to flip the last
// (i+1)th bit of binary equivalent of n2
n2 = n2 ^ (1 << i);
}
// n2 will be the one's complement of n
return Math.abs(n - n2);
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int lucky_p = luckiest_person(N);
System.out.println(lucky_p);
}
}
// This code is contributed by rishavmahato348
Python3
# Python3 implementation of the above approach import math def luckiest_person(n): # to calculate the number of bits in # the binary equivalent of n len_ = int(math.log(n, 2)) + 1 # Finding complement by inverting the # bits one by one from last n2 = n for i in range(len_): # XOR of n2 with (1<<i) to flip # the last (i+1)th bit of binary equivalent of n2 n2 = n2 ^ (1 << i) # n2 will be the one's complement of n return abs(n - n2) # Driver Code N = 3 lucky_p = luckiest_person(N) print(lucky_p) # this code is contributed by phasing17
C#
// C# implementation of the above approach
using System;
class GFG {
static int luckiest_person(int n)
{
// To calculate the number of bits in
// the binary equivalent of n
int len = (int)(Math.Log(n) / Math.Log(2)) + 1;
// Finding complement by inverting the
// bits one by one from last
int n2 = n;
for (int i = 0; i < len; i++) {
// XOR of n2 with (1<<i) to flip the last
// (i+1)th bit of binary equivalent of n2
n2 = n2 ^ (1 << i);
}
// n2 will be the one's complement of n
return Math.Abs(n - n2);
}
// Driver code
public static void Main()
{
int N = 3;
int lucky_p = luckiest_person(N);
Console.Write(lucky_p);
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// JavaScript implementation of the above approach
function luckiest_person(n)
{
// to calculate the number of bits in
// the binary equivalent of n
let len = parseInt(Math.log(n) / Math.log(2)) + 1;
// Finding complement by inverting the
// bits one by one from last
let n2 = n;
for (let i = 0; i < len; i++) {
// XOR of n2 with (1<<i) to flip
// the last (i+1)th bit of binary equivalent of n2
n2 = n2 ^ (1 << i);
}
// n2 will be the one's complement of n
return Math.abs(n - n2);
}
// Driver Code
let N = 3;
let lucky_p = luckiest_person(N);
document.write(lucky_p);
</script>
Producción
3
Implementación alternativa en O(1): El enfoque utilizado aquí es el mismo, pero las operaciones utilizadas son de tiempo constante.
C++
// Here is a O(1) solution for this problem
// it will work for 32 bit integers]
#include <bits/stdc++.h>
using namespace std;
// function to find the highest power of 2
// which is less than n
int setBitNumber(int n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Increment n by 1 so that
// there is only one set bit
// which is just before original
// MSB. n now becomes 1000000000
n = n + 1;
// Return original MSB after shifting.
// n now becomes 100000000
return (n >> 1);
}
int luckiest_person(int n)
{
// to calculate the highest number which
// is power of 2 and less than n
int nearestPower = setBitNumber(n);
// return the correct answer as per the
// approach in above article
return 2 * (n - nearestPower) + 1;
}
int main()
{
int N = 8;
int lucky_p = luckiest_person(N);
cout << lucky_p;
return 0;
}
// This code is contributed by Ujesh Maurya
Java
/*package whatever //do not write package name here */
import java.io.*;
// Here is a O(1) solution for this problem
// it will work for 32 bit integers]
class GFG {
static int setBitNumber(int n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Increment n by 1 so that
// there is only one set bit
// which is just before original
// MSB. n now becomes 1000000000
n = n + 1;
// Return original MSB after shifting.
// n now becomes 100000000
return (n >> 1);
}
static int luckiest_person(int n)
{
// to calculate the highest number which
// is power of 2 and less than n
int nearestPower = setBitNumber(n);
// return the correct answer as per the
// approach in above article
return 2 * (n - nearestPower) + 1;
}
// Driver Code
public static void main(String[] args)
{
int N = 8;
int lucky_p = luckiest_person(N);
System.out.print(lucky_p);
}
}
// This code is contributed by Ujesh Maurya
C#
// Here is a O(1) solution for this problem
// it will work for 32 bit integers]
using System;
class GFG {
// function to find the highest power of 2
// which is less than n
static int setBitNumber(int n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Increment n by 1 so that
// there is only one set bit
// which is just before original
// MSB. n now becomes 1000000000
n = n + 1;
// Return original MSB after shifting.
// n now becomes 100000000
return (n >> 1);
}
static int luckiest_person(int n)
{
// to calculate the highest number which
// is power of 2 and less than n
int nearestPower = setBitNumber(n);
// return the correct answer as per the
// approach in above article
return 2 * (n - nearestPower) + 1;
}
// Driver code
public static void Main()
{
int N = 8;
int lucky_p = luckiest_person(N);
Console.Write(lucky_p);
}
}
// This code is contributed by Ujesh Maurya
Javascript
<script>
// Javascript program for the above approach
// Here is a O(1) solution for this problem
// it will work for 32 bit integers]
function setBitNumber(n) {
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Increment n by 1 so that
// there is only one set bit
// which is just before original
// MSB. n now becomes 1000000000
n = n + 1;
// Return original MSB after shifting.
// n now becomes 100000000
return (n >> 1);
}
function luckiest_person(n) {
// to calculate the highest number which
// is power of 2 and less than n
let nearestPower = setBitNumber(n);
// return the correct answer as per the
// approach in above article
return 2 * (n - nearestPower) + 1;
}
// Driver Code
let N = 8;
let lucky_p = luckiest_person(N);
document.write(lucky_p);
// This code is contributed by Saurabh Jaiswal
</script>
Producción
1
Otro enfoque en O(1): Sobre la base del patrón que se forma en la pregunta dada, que se muestra en la siguiente tabla.
| norte | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | |||||
| 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Driven code
int find(int n)
{
// Obtain number less n in 2's power
int twospower = pow(2, (int)log2(n));
// Find p-position of odd number, in odd series
int diff = n - twospower + 1;
// Value of pth odd number
int diffthodd = (2 * diff) - 1;
return diffthodd;
}
// Driver code
int main()
{
int n = 5;
cout << find(n);
return 0;
}
// This code is contributed by Dharmik Parmar
Producción
3
Publicación traducida automáticamente
Artículo escrito por Harshal Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA