CODEWITHSUNDEEP
python-3.xalgorithmdynamic-programming
crazysra
crazysra

Reputation: 151

Dealing with problems where memory isn't sufficient. Dynamic programming

I was solving a Problem using python, here i was storing a repetitive string "abc" in a string with everytime each character getting double like "abcaabbccaaaabbbbcccc.......... , and i had to find the nth character. The constraints were n<=10^9 , Now when i tried to store this their was memory error as the string was to too large (i tried to store all the charaters till the charater 2^30 times repeated). CAn somebody help me with the approach to tackle this situation.

t=' '
for i in range(0 , 30):
    t = t +'a'*(2**i)
    t = t +'b'*(2**i)
    t = t +'c'*(2**i)

Upvotes: 1

Views: 54

Answers (1)

Prune
Prune

Reputation: 77857

Obviously, you can't do this the straightforward, brute-force way. Instead, you need to count along a virtual string to find where your given index appears. I'll lay this out in too much detail so you can see the logic:

n = 314159265    # Pick a large value for illustration
rem = n

for i in range(0 , 30):
    size = 2**i
    # print(size, rem)
    rem -= size
    if rem <= 0:
        char = 'a'
        break
    rem -= size
    if rem <= 0:
        char = 'b'
        break
    rem -= size
    if rem <= 0:
        char = 'c'
        break

print("Character", n, "is", char)

Output:

Character 314159265 is b

You can shorten this with a better loop body; I'll leave that as a further exercise. If you get insightful with your arithmetic, you can simply compute the appropriate letter from the chunk sizes you generate.

Upvotes: 3

Related Questions