CareerCup

To find the number of digits in the largest lucky number till which point, we get:
(sum_of_all_digits_in_lucky_string_so_far) >= n
we need to iterate over all lucky numbers. Note, that for a lucky number with k digits, there are at most 2^k lucky numbers that you can generate. So, there are (k*2^k) digits altogether, for this k digit lucky number series. So we want to find the k for which the following is true:
SUM(k*2^k) <= n < SUM((k+1)*2(k+1))

This can be done simply by iterating in a while loop and finding the sum like so:

int factor = 2; 
int i = 1; 
int sum = 2;    // sum of digits so far 

while(sum < n) {
    factor = factor << 1;
    i++;
    sum = sum + (i*factor);
}

Now, we need to calculate the number for which we are interested in getting the lucky number series:

// at this point, k = i-1
int diff = n - sum - (i*factor);    // get the diff'th number that we are interested in

int num = 0;
int j = 1; 
while(j < i-1) {
    num = num*j + 4;
    j = j*10;
}

Finally, we call the lucky string generator like so:

getLuckyNumbers(num, i-1, 0);

private String resultString = "";

public void getLuckyNumbers(int num, int numDigits, int depth) {
    
    int tempNum = num;    
    
    for(int i=1; i<numdigits; i++) {
        // create new int with '5' at specified position
        // add digits
        // tempNum is num, with i'th digit replaced with 5
        tempNum = setNthDigit(num, numDigits-i, 5);
        if(depth == numDigits - 1) {
            resultString = resultString + tempNum;    // concatenate with result
            getLuckyNumbers(tempNum, numDigits-1, 0);
        }
        else
            getLuckyNumbers(tempNum, numDigits, depth + 1);
    }    
}

And finally finally, we find the diff'th digit in resultString

resultString.charAt(diff);

time complexity is O(2^k) where k = the number of digits in the lucky number series within the lucky string that we are interested in.

This can actually be optimized to calculate resultString just to the point where resultString.length() == diff

// Think of this as a list of all binary combinations from 2^1 to 2^N 0,1;00,01,10,11;000,001,010,...
        
        int n = 10; // input
        
        int curPow = 1;
        int skipCount = 0;
        String numbersInRange = "";
        
        // Find the 'bit' range
        // If we're looking for the position 10th (0-based index) => 0,1;00,01,10,11;'0'00,001, it will be in the 2^3 range
        // We also need to remember how far we skip (in this case, we skip 2^1 (2 digits) and 2^2 (8 digits) == 10 total )
        while ( ( skipCount + Math.pow( 2, curPow ) * curPow ) <= n ) {
            
            skipCount += Math.pow( 2, curPow ) * curPow;

            curPow++;
        }
        
        // Create all the posible combnation of the 2^X (x=3 in this case)
        for ( int x = 0; x < Math.pow( 2, curPow ); x++ ) {
            

            String bin = Integer.toBinaryString( x );
            int paddedCount = curPow - bin.length();
            
            for ( int y = 0; y < paddedCount; y++ ) {
                
                bin = "0" + bin;
            }
                        
            numbersInRange += bin;
        }
        System.out.println( numbersInRange );
        System.out.println( "skipcount: " + skipCount );
        System.out.println( "i = " + numbersInRange.charAt( n - skipCount ) );
        // Now map 0 => 4 and 1 => 5

     }

The luck string is ordered like this:

str length number examples
1 2^1 4, 5
2 2^2 44,45,54,55
3 2^3 444,445,454,455,544,545,554,555
...

So this question can be tranlated to find the size of luck_string and its offset to the array of string with the same size.

A verified solution in ruby as below:

# get the width and offset of the nth luck string
# e.g, n = 3 ('44'), width = 2, offset = 0 [44, 45, 54, 55]
def str_width_and_offset(n)
    sum = 0
    (1..n).each do |i|
       tmp = sum
       sum = sum + 2**i
       return i, n - tmp - 1 if sum -n >= 0
    end
end

# print m luck string
m = ARGV[0].to_i
luck_str = ""
(1..m).each do |n|
width,offset = str_width_and_offset(n)

# return offset's bit mask, e.g, 3 => "11"
bit_mask_str = offset.to_i.to_s(2)

# padding '0' to width length
bit_mask_str = ('0'*(width - bit_mask_str.size)) << bit_mask_str

# replace '0' with '4' and '1' with '5'
luck_str << bit_mask_str.gsub(/0/,'4').gsub(/1/,'5') + " "
end

puts luck_str

Use two queues...
1st queue add numbers with unit place as 4
2nd queue add numbers with unit place as 5
Find min of both queues and add it to result string in form of digits.
do it till our result string is more than n.
get nth digit

public static void main(String args[]) throws IOException
{
String finalString = "";
for(int i = 1; i <= 100000; i++ )
{
int ref = i, num = 0;
boolean flag = true;
while(ref != 0)
{
num = ref%10;
ref /= 10;
if((num != 4) && (num != 5))
{
flag = false;
break;
}
}
if(flag)
{
finalString = finalString + i;
}
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = -1;
while(n != 0)
{
System.out.println("Enter 0 to Exit");
System.out.println("Enter your Value of N : ");
n = Integer.parseInt(br.readLine());
if(n<=0)
{
continue;
}
n = Integer.parseInt(finalString.substring(n-1, n));
if(n == 5)
{
System.out.println("Earth");
}
else
{
System.out.println("Hacker");
}
}
System.out.println("Ends");
}

public static int get45(int n) {
        int mask = 1;
        int sum = 0;
        int k = 0;

        do {
            sum += k * (mask << k);
            k++;
        }
        while (n > sum + k * (mask << k));

        int remainder = n - sum;
        int pos = remainder / k;
        int mod = remainder % k;
        int tmp = 0;

        for(int i = 0;i < pos;i++) {
             tmp++;
        }

        if((tmp & (mask << (k - mod - 1))) != 0) {
            return 5;
        }  else {
            return 4;
        }

    }

#include<iostream>
using namespace std;

int main(int argc, char **argv)
{
    int T, i;
    unsigned long long int n, sum, p, q, j;

    cin >> T;
    for (i = 1; i <= T; i++) {
        cin >> n;
        sum = 0;
        j = 1;
        do {
            sum += j * (1 << j);
            j++;
        } while (sum < n);
        j--;
        n = n - (sum - j * (1 << j));
        //cout << n << endl;
        p = (n - 1) / j;
        q = (n - 1) % j;
        if ((p & (1 << (j - q - 1))) == 0) {
            cout << "Hacker" << endl;
        } else {
            cout << "Earth" << endl;
        }

    }
}

#include "stdafx.h"
#include <allocators>
#include <math.h>

int* BinaryValue(int ,int);
int _tmain(int argc, _TCHAR* argv[])
{
	while (1)
	{
		int vPrev = 0, v = 0;
		int position;
		int*arrN = 0;
		int result = 0;
		int flag = 0;
		int inc = 0;
		printf("\nEnter the position within the string ");
		scanf_s("%d", &position);

		for (int bitcount = 1; bitcount < 16; bitcount++)//checks till 2^15 th digit in the string;
		{
			if (flag == 1)
				break;
			v += bitcount * ((int)pow(2.0, bitcount));
			if (v > position)
			{
				int k = 0, kPrev = 0;
				for (k = vPrev; k <= v;)
				{
					if (k > position)
					{
						arrN = BinaryValue(inc - 1, bitcount);
						result = arrN[position - kPrev];
						if (result == 0)
						{
							result = 4;//considered 4 to be binary 0
							printf("Hacker");
						}
						else
						{
							result = 5;//considered 5 to be binary 1
							printf("Earth");
						}

						flag = 1;
						break;
					}
					kPrev = k;
					k += bitcount;
					inc++;
				}
			}
			vPrev = v;
		}
		free(arrN);
	}
	return 0;
}

int* BinaryValue(int given, int bitcount)
{
	int  n = 0;
	int* arrN;
	arrN = (int*)malloc(sizeof(int)*bitcount);
	for (n = bitcount - 1; n >= 0; n--)
	{
		arrN[n] = given % 2;
		given /= 2;
	}
	//for (int m = 0; m < bitcount; m++)
	//	printf("%d", arrN[m]);
	return arrN;
}

//Solution implemented in c++

#include <iostream>
#include <string>


//create a function that returns a string that takes in a string named T and an unsigned integer ( to save memory ) named n.
//Assuming T is the actual LuckyString and not the number of Lucky Strings needing to be executed. (!IMPORTANT)
//the keyword unsigned assumes an unsigned integer in c++
std::string findLuckyString(std::string T, unsigned n){
//IMPLEMENT CONTRAINTS HERE OR IN PARAMETERS
/* Sine contraints for this problem are very vague, I did not implemnent them.
Do they mean storage as in the decimal value or the binary value. This MUST be clarified(!IMPORTANT)
*/
//We loop through the string until we find the proper index.
for (int i = 0; i < T.length(); i++){

//checks the index to see if it is matching
if(n == i){
//if the index is a 5, we will return a string titled "Hacker"
if(T[i] == '5'){
return "Earth";
}//end if
else if(T[i] == '4'){
// if the index is a 4, then the function returns a string titled "Earth"
return "Hacker";
}//end else
}//end if
}//end loop
//if the index is out of bounds OR the string does no consist of all 5s and 4s, then the input is invalid nd will return the string below
return "invalid input! Check string input to make sure '5's and '4's are present and that n is a valid index in the string";
}

int main(){
//test the function with some values. all index's start at 0!
std::cout << findLuckyString("544544", 4) << std::endl;
std::cout << findLuckyString("555554455333", 7) << std::endl;
std::cout << findLuckyString("544544", 10) << std::endl;
std::cout << findLuckyString("67823", 3) << std::endl;
system("PAUSE");
}

Using C#

public void TestMethod2(int nthdigit)
{
var alphabet = "45";
string tempLuckyString = "";
int digitstosub = 0;
int tempcheck = 1;
int temp = 0;
while (tempcheck < nthdigit)
{
temp++;
if(temp ==1)
{
tempcheck = (int)(Math.Pow(2, temp)) * temp;
}
else
{
digitstosub = tempcheck;
tempcheck = (int)(Math.Pow(2, temp)) * temp + tempcheck;
}
}
int newdigit = nthdigit - digitstosub;
int Noofdigitswithtemp = (int)(Math.Pow(2, temp)) * temp;

var q = alphabet.Select(x => x.ToString());
for (int i = 0; i < temp - 1; i++)
{
q = q.SelectMany(x => alphabet, (x, y) => x + y);
}
foreach (var item in q)
{
tempLuckyString = tempLuckyString + item;
if (tempLuckyString.Length > newdigit)
break;
}

var theElement = tempLuckyString.ElementAt(newdigit-1);
Console.WriteLine(theElement);
}

generate all 1, 2, 3 .. combinations of 4, 5 and keep appending them. If the length of string is greater then n return the nth value.

for example :

public void returnNthLucky() {
String s = "";
int k = 1;
while(s.length < n) {
List l = generate(k, {4, 5});
s += appendAll(l);
}
}

public generate(int k, string[] sym, List<String> l, String s) {
if (s.length == k) {
l.add(s);
}
for( k : sym) {
generate(k, sym, l, s + k);
}
}

var theElement = tempLuckyString.ElementAt(newdigit-1);
//Console.WriteLine(temp.ToString());
//Console.WriteLine(check.ToString());
//Console.WriteLine(digitstosub.ToString());
//Console.WriteLine(Noofdigitswithtemp.ToString());
//Console.WriteLine(newdigit.ToString());
//Console.WriteLine(tempLuckyString);
Console.WriteLine(theElement);