Given that N person (numbered 1 to N) standing as to form a circle. They all have the gun in their hand which is pointed to their leftmost Partner.
Every one shoots such that 1 shoot 2, 3 shoots 4, 5 shoots 6 …. (N-1)the shoot N (if N is even otherwise N shoots 1).
Again on the second iteration, they shoot the rest of remains as above mentioned logic (now for n as even, 1 will shoot to 3, 5 will shoot to 7 and so on).
The task is to find which person is the luckiest(didn’t die)?
Examples:
Input: N = 3
Output: 3
As N = 3 then 1 will shoot 2, 3 will shoot 1 hence 3 is the luckiest person.Input: N = 8
Output: 1
Here as N = 8, 1 will shoot 1, 3 will shoot 4, 5 will shoot 6, 7 will shoot 8, Again 1 will shoot 3, 5 will shoot 7, Again 1 will shoot 5 and hence 1 is the luckiest person.
This problem has already been discussed in Lucky alive person in a circle | Code Solution to sword puzzle. In this post, a different approach is discussed.
Approach:
- Take the Binary Equivalent of N.
- Find its 1’s compliment and convert its equal decimal number N`.
- find |N – N`|.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to convert string to numberint 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 decimalint 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 complementstring 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 codeint 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;} |
Java
// Java implementation of the above approachimport java.util.*;public class Main { // Function to convert string to number public static int stringToNum(String s) { // The object has the value 12345 and stream // it to the integer x int x = Integer.parseInt(s); return x; } // Function to convert binary to decimal public static 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 != 0) { int last_digit = temp % 10; temp = temp / 10; dec_value += last_digit * base; base = base * 2; } return dec_value; } public static String itoa(int num, String str, int base) { int i = 0; boolean isNegative = false; /* Handle 0 explicitly, otherwise empty string is printed for 0 */ if (num == 0) { str += '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 += (rem > 9) ? (char)(rem - 10 + 'a') : (char)(rem + '0'); num = num / base; } // If the number is negative, append '-' if (isNegative) str += '-'; StringBuilder sb = new StringBuilder(str); // Reverse the string sb.reverse(); return sb.toString(); } public static char flip(char c) { return (c == '0') ? '1' : '0'; } // Function to find the ones complement public static 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.charAt(i)); return ones; } // Driver code public static void main(String[] args) { // 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; System.out.println(luckiest_person); }}// This code is contributed by Prajwal Kandekar |
Python3
# Function to convert string to numberdef string_to_num(s): return int(s)# Function to convert binary to decimal integerdef binary_to_decimal(n): num = string_to_num(n) dec_value = 0 # Initializing base value to 1, i.e 2^0 base = 1 temp = num while temp: last_digit = temp % 10 temp = temp // 10 dec_value += last_digit * base base = base * 2 return dec_value def itoa(num, base): i = 0 is_negative = False str_list = [] # Handle 0 explicitly, otherwise empty string is printed for 0 if num == 0: str_list.append('0') return ''.join(str_list) # In standard itoa(), negative numbers are handled only with base 10. Otherwise numbers are considered unsigned. if num < 0 and base == 10: is_negative = True num = -num # Process individual digits while num != 0: rem = num % base str_list.append(str(rem) if rem <= 9 else chr(ord('A') + rem - 10)) num //= base # If the number is negative, append '-' if is_negative: str_list.append('-') # Reverse the string str_list.reverse() return ''.join(str_list)def flip(c): return '1' if c == '0' else '0'# Function to find the ones complementdef ones_complement(bin): n = len(bin) ones = "" # for ones complement flip every bit for i in range(n): ones += flip(bin[i]) return ones# Driver code# Taking the number of a person standing in a circle.N = 3# Storing the binary equivalent in a string.ans = itoa(N, 2)# Taking one's complement and convert it to decimal valueN_dash = binary_to_decimal(ones_complement(ans))luckiest_person = N - N_dashprint(luckiest_person) |
C#
using System;class MainClass { // Function to convert string to number public static int stringToNum(string s) { // The object has the value 12345 and stream // it to the integer x int x = int.Parse(s); return x; } // Function to convert binary to decimal public static int binaryToDecimal(string n) { int num = stringToNum(n); int dec_value = 0; // Initializing base value to 1, i.e 2^0 int base_value = 1; int temp = num; while (temp != 0) { int last_digit = temp % 10; temp = temp / 10; dec_value += last_digit * base_value; base_value = base_value * 2; } return dec_value; } public static string itoa(int num, string str, int base_value) { int i = 0; bool isNegative = false; /* Handle 0 explicitly, otherwise empty string is printed for 0 */ if (num == 0) { str += '0'; return str; } // In standard itoa(), negative numbers // are handled only with base 10. // Otherwise numbers are considered unsigned. if (num < 0 && base_value == 10) { isNegative = true; num = -num; } // Process individual digits while (num != 0) { int rem = num % base_value; str += (rem > 9) ? (char)(rem - 10 + 'a') : (char)(rem + '0'); num = num / base_value; } // If the number is negative, append '-' if (isNegative) str += '-'; char[] charArray = str.ToCharArray(); // Reverse the string Array.Reverse(charArray); return new string(charArray); } public static char flip(char c) { return (c == '0') ? '1' : '0'; } // Function to find the ones complement public static 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 public static void 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; Console.WriteLine(luckiest_person); }}// This code is contributed by Prajwal Kandekar |
Javascript
// JavaScript implementation of the above approach// Function to convert string to numberfunction stringToNum(s){ return parseInt(s);}// Function to convert binary to decimal integerfunction 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 complementfunction 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 valuelet N_dash = binaryToDecimal(onesComplement(ans));let luckiest_person = N - N_dash;console.log(luckiest_person);// This code is contributed by phasing17 |
Output
3
Alternate Shorter Implementation :
The approach used here is same.
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 approachimport 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 approachimport mathdef 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 CodeN = 3lucky_p = luckiest_person(N)print(lucky_p)# this code is contributed by phasing17 |
C#
// C# implementation of the above approachusing 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 approachfunction 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> |
Output
3
Alternate Implementation in O(1) : The approach used here is same, but the operations used are of constant time.
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 nint 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 Codelet N = 8;let lucky_p = luckiest_person(N);document.write(lucky_p);// This code is contributed by Saurabh Jaiswal</script> |
Python3
def set_bit_number(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)def luckiest_person(n): # to calculate the highest number which # is power of 2 and less than n nearest_power = set_bit_number(n) # return the correct answer as per the # approach in above article return 2 * (n - nearest_power) + 1# Driver Codeif __name__ == "__main__": N = 8 lucky_p = luckiest_person(N) print(lucky_p) |
Output
1
Another approach in O(1) : On the basis of the pattern that forms in given question, which is displayed in following table.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |||||
| 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 codeint 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 codeint main(){ int n = 5; cout << find(n); return 0;}// This code is contributed by Dharmik Parmar |
Java
import java.util.*;public class GFG { public static void main(String[] args) { int n = 5; System.out.println(find(n)); } public static int find(int n) { // Obtain number less n in 2's power int twospower = (int) Math.pow(2, (int) (Math.log(n) / Math.log(2))); // 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; }} |
Python3
import mathdef find(n): # Obtain number less n in 2's power twospower = int(math.pow(2, int(math.log2(n)))) # Find p-position of odd number, in odd series diff = n - twospower + 1 # Value of pth odd number diffthodd = (2 * diff) - 1 return diffthodd# Driver coden = 5print(find(n)) |
C#
using System;public class GFG { static public void Main() { int n = 5; Console.WriteLine(find(n)); } public static int find(int n) { // Obtain number less n in 2's power int twospower = (int)Math.Pow( 2, (int)(Math.Log(n) / Math.Log(2))); // 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; }} |
Javascript
// JS program to implement the approachfunction find(n) { // Obtain number less n in 2's power let twospower = Math.pow(2, Math.floor(Math.log(n) / Math.log(2))); // Find p-position of odd number, in odd series let diff = n - twospower + 1; // Value of pth odd number let diffthodd = 2 * diff - 1; return diffthodd;}let n = 5;console.log(find(n)); |
Output
3
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
