Suerte persona viva en un círculo | Juego – 2

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:  

1. Tome el equivalente binario de N.
2. Encuentre su complemento a 1 y convierta su número decimal igual N`.
3. encontrar |N – N`|.

A continuación se muestra la implementación del enfoque anterior:  

// 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 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

3

Implementación alternativa más corta: 
el enfoque utilizado aquí es el mismo.

// 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 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 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# 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

<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>

3

Implementación alternativa en O(1): El enfoque utilizado aquí es el mismo, pero las operaciones utilizadas son de tiempo constante.

// 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

/*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

// 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

<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>

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.

#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

3