CODEWITHSUNDEEP
python
Akash Rana
Akash Rana

Reputation: 3845

Lucky Numbers Python Program Incorrect Python Output

Practice Problems / Lucky String All submissions to this problem are public. View all submissions.

Lucky numbers are those numbers which contain only "4" and/or "5". For example 4, 5, 44, 54,55,444 are lucky numbers while 457, 987 ,154 are not.

Lucky number sequence is one in which all lucky numbers exist in increasing order for example 4,5,44,45,54,55,444,445,454,455...

Now we concatenate all the lucky numbers (in ascending order) to make a lucky string "4544455455444445454455..."

Given n, your task is to find the nth digit of the lucky string. If the digit is 4 then you >have to print "Hacker" else you have to print "Earth".

Input:

first line contain number of test cases T , next T line contain a single integer n.

Output:

For each test case print Hacker if n-th digit of lucky string is 4 else print Earth if n-th digit of lucky string is 5.

Constraints:

1 <= t <= 10^5
1 <= n <= 10^15

Following is the python code :

test_cases = int(input())

final = []

def check(stra,num):
    if stra[num-1]==4:
        final.append("Hacker")
    else:
        final.append("Earth")

def GenStr(num):
    stra = "4"
    i = int(5)
    while(len(stra)<num+2):
        X = str(i)
        flag = True
        for j in range(len(str(i))):
            if(X[j]==4 or X[j]==5):
                pass
            else:
                flag = False
        if flag==True:
            stra+=X
        i+=1
    print(stra)
    return stra

for i in range(test_cases): 
    num = int(input())
    # generate string
    stra = GenStr(num)
    print("stra "+stra)
    # check the stat
    check(stra,num)

print("\n".join(final))

What is wrong in this code, please do not mind if it is a silly mistake I am just a beginner in python programming

Upvotes: 0

Views: 1507

Answers (3)

Hugh Bothwell
Hugh Bothwell

Reputation: 56684

As @Gassa points out, brute-forcing this is just not going to work; you would need a million gigabytes of RAM, and it would take far too long.

So what would an analytic solution look like?

If you replace "4" with "0" and "5" with "1", you will see that the lucky number sequence becomes 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, .... This should look familiar: it is every 1-digit binary number in ascending order, followed by every 2-digit binary number in ascending order, followed by every 3-digit binary number in ascending order, etc.

So if you do something like

n = 491         # the digit we are seeking (for example)

d = 1           # number of binary digits
p = 2           # 2**d == number of items encoded
while n > d*p:  # sought digit is past the end of the next binary expansion?
    n -= d*p        # reduce offset by appropriate number of digits
    d += 1
    p *= 2

then n = 233, d = 6 means we are looking for the 233rd character in the 6-bit expansion.

But we can improve on that:

k, n = n // d, n % d

which gives n = 5, k = 38, d = 6 means we are looking at the 5th character of the 38th 6-bit value.

Note: all offsets here are 0-based; if you expect 1-based offsets, you will have to adjust your math accordingly!

The 38th 6-bit value is just 38 converted to a 6-bit binary value; you could muck about with strings to extract the character you want, but it's probably easier to remember that integers are stored as binary internally so we can get what we want with a bit of math:

digit = (k >> (d - n - 1)) & 1   # => 0

so the character in the original string would be a "4".

Upvotes: 0

Two-Bit Alchemist
Two-Bit Alchemist

Reputation: 18467

Comments on your Code

There are several things in your code which don't quite make sense, and need to be addressed:

  • int(input()) says to ask the user nothing, try to convert any string they type before pressing enter to an integer, and crash otherwise.
  • The pattern for i in range(len(x)) is almost always wrong in Python. Strings are iterable (they are lists of characters), which is why you can use the list-style index operator (as you do with x[j]), so just iterate over them: for j in str(i).
  • The pattern if x==True: is always wrong in Python. We prefer if x:.
  • i = int(5). There is no need to convert an integer literal to an integer. i = 5 is the correct assignment statement.
  • Try to use better variable names. It's very difficult to follow your code and your reasoning because it is littered with meaningless identifiers like stra (string a??), X, num, etc.

How to Approach the Assignment

I will be honest: I don't fully understand the assignment as presented. It's not clear what a "test case" is or how the input will be formatted (or, for that matter, where the input is coming from). That said, a few thoughts on how to approach this:

  • Finding numbers that contain only 4 or 5 means treating them as strings. This could be as easy as testing len(str(x).replace('4', '').replace('5', '')), and there are better ways than that.
  • Listing 'lucky numbers' in increasing order can be accomplished with the built-in sorted function.
  • Concatenating that list would be ''.join(sorted(lucky_numbers)) or similar.
  • Taking the nth digit of that list could then be done with string indexing as before.

Upvotes: 1

Gassa
Gassa

Reputation: 8844

  1. The immediately incorrect thing is the following. stra is 4. flag always becomes False. Thus stra never grows, and while(len(stra)<num+2): is an infinite loop.

  2. The approach itself will not fully solve the problem, since you can't construct a string of length 1015, it would take too much time and just won't fit into memory.

Upvotes: 1

Related Questions