Sherlock and The Beast

This is my solution to this question from Hackerrank.

Given N (<= 100000), find the largest N-digit number such that:

1. The number has only 3 and 5 as its digits.
2. Number of times 3 appears is divisible by 5.
3. Number of times 5 appears is divisible by 3.

If no such number exists, produce -1.

Please guide me. Is there any optimization or improvement that can be done to the code?

a=0
items=[]

a=int(raw_input(''))
for i in range(0,a):
items.append(int(raw_input('')))

def Sherlock_and_The_Beast(items):
for i in items:

if i<3:
print -1
elif i%3==0:
print int(str(5)*i)
elif i==5:
print int(str(3)*i)

else:
flag=False
for j in range(i/3,-1,-1):
if (i-(3*j))%5==0:
flag=True
print int(str(5)*(3*j)+str(3)*(i-(3*j)))
break
if not flag:
print -1

Sherlock_and_The_Beast(items)

-

I think your code could use some restructuring:

1. The name Sherlock_and_The_Beast is more applicable as a module name instead of a function name. Now, even though I said 'more applicable', it does not mean I would suggest naming your Python script this. I would instead call it sherlock.py.*
2. Your function should be named something like generate_decent_number. This gives a better description of what it actually does.
3. I would have your function take a single integer instead of a list and then return the decent number. Doing so, removes the need for a flag variable.
4. Use xrange instead of range.

There are also a few style notes to point out:

1. Use descriptive variable names. Even though i (and to some extent j) have been conventionalized as indexing names, I prefer to be more descriptive. i should be item and j should be num.
2. Use whitespace appropriately. Put single spaces around assignment or conditional operators:

foo = 'bar'
if foo == 'bar'

3. I prefer to use not when I can. Because 0 evaluates to False in conditional statements, you can use:

elif not item % 5:


elif item%5 == 0:


This is mostly a personal preference. Some people abhor checking for negative conditions.

Past these notes above, your code is simple and straightforward which are both Pythonic conventions.

Here is my version:

def get_decent_number(num_digits):
if num_digits < 3:
return -1

three = str(3)
five = str(5)
if not num_digits % 3:
return five*num_digits
elif num_digits == 5:
return three*num_digits

for num in xrange(num_digits/3, -1, -1):
diff = num_digits - 3*num
if not diff % 5:
return five*3*num + three*diff

return -1

-
in my code i have changed forlop replace 0 with -1 –  sundar nataraj Сундар Jun 16 '14 at 15:10
Shouldn't get_decent_number(15) actually yield 555555555555555? –  Bergi Jun 16 '14 at 17:21
Yes, that was a bad example on my part. –  BeetDemGuise Jun 16 '14 at 17:42
+1 thanks darin –  sundar nataraj Сундар Jun 17 '14 at 3:04

In terms of improvements, a few obvious things. Generally, as with many Python questions here, I would suggest you read and implement the Python Style Guide, PEP-0008, particularly:

• Naming conventions (function and variable names should be lowercase_with_underscores); and
• Whitespace (e.g. if i<3: should be if i < 3:).

Although this was written for Hacker Rank, you should still not have running code at the top level of the script. Instead, I suggest you wrap the top section in a function (e.g. def create_items():) and then add:

if __name__ == "__main__":
sherlock_and_the_beast(create_items())


The context does, however, place some restrictions - I was going to suggest that you gave a meaningful prompt to raw_input, but the Hacker Rank grader gets confused!

You could use the for: else: construct to simplify your final loop:

for j in range(i/3, 0, -1):
if (i - (3 * j)) % 5 == 0:
print int('5' * (3 * j) + '3' * (i % (3 * j)))
break
else:
print -1

-
hey i have changed the for loop –  sundar nataraj Сундар Jun 16 '14 at 12:51

On top of the comment from jonrsharpe, I'd like to point out a few things about the code to the initial list :

• you do not need to initialise a to 0 first : this line can be removed.
• you do not need to provide 0 as a first argument to range as it is the default behavior
• you don't even need the variable a at all
• we usually call _ the variables whose value is not going to be used

A this stage, you have :

items=[]
for _ in range(int(raw_input(''))):
items.append(int(raw_input('')))


Then, you can use list comprehension to write this in a concise way :

items=[int(raw_input('')) for _ in range(int(raw_input('')))]


Finally, because of the way this is going to be used, you do not even need to actually build the list : you could just use generator expression :

items = (int(raw_input('')) for _ in range(int(raw_input(''))))

-
+1 thanks for your suggestions –  sundar nataraj Сундар Jun 17 '14 at 3:03

Is there any improvement that can be done to the code?

Yes. The other answers do have very good points, but I don't want to repeat them. I only could add that renaming your i variable to n would match the task description better.

Is there any optimization?

You don't need any loop at all! We only need to distinguish four cases:

• N is divisible by 3 exactly
• N is divisible by 3 with remainder 1 and is at least 10
• N is divisible by 3 with remainder 2 and is at least 5
• else there is no decent number with N digits

So we can simplify the code to

def decent_number(n):
rem = n % 3
threes = ((3 - rem) % 3) * 5
fives = n - threes
if fives < 0:
return -1
else:
return int("5"*fives + "3"*threes)

for line in lines
print decent_number(int(line))

-

Even without deducing a general algorithm, here's how I would have written it, in Python as well:

def largest_decent_number_of_length(N):
for num_threes in xrange(0, N, 5):
num_fives = length - num_threes
if num_fives % 3 == 0:
return "5" * num_fives + "3" * num_threes
else:
return "-1"

if __name__ == "__main__":
T = raw_input('')
for _ in range(0, T):
N = raw_input('')
print largest_decent_number_of_length(N)


This solution to me is more clear because it doesn't do magic with modulo to determine the case we are in, and incorporates some points which I feel are important for clear code.

First of all, as jonrsharpe also mentioned: if you want to do code executing at the top level, do it in an if __name__ == "__main__": section. This will only execute when directly run, but not when imported. However, this is something python specific, and in another language you would have to do this in a different fashion.

Second: The variable names are quite specific, num_threes and num_fives are more clear than i and j. I could have gone overboard, and have written number_of_threes but that would have made the names overly long, and thus less readable for such a short piece of code. The T and N however are quite short, but they are a direct translation from the document. I could have named them num_challenges and challenge, but that isn't necessary---assuming the reader also read the challenge itself. Another thing I always try to do is make function names read like descriptions, especially when the variables are filled in. This doesn't work often, but in the cases where you can, I believe it makes code more readable. "print largest decent number of length N" sounds like a clear task to me.

Third: After reading this, you should be able to follow my logic---I hope. The largest number will start with 5s, followed by 3s --- interchanging a 5 and a 3 would make the number smaller. Also, less 3s means more 5s, so we start with as few 3s as possible, and add as few as possible while still satisfying the second requirement (num_threes % 5 == 0). For each of these options, we check if the number of fives also satisfies the requirements, and if so, we print the number.

Fourth: we don't print the number, but return it, making the function reusable. (Not that important in this case, but I would just like to mention it). The main loop is concerned with reading numbers, and printing results. The function is concerned with finding the answer. The responsibilities are separated.

Fifth: The value returned is in both cases of the same type (a string, twice). Returning a string instead of a number is an arbitrary choice, however one that followed quite easily from the manipulations involved. One could decide to make it an integer instead, by writing return int("5" * num_fives + "3" * num_threes) and return -1. Both are a viable solution, and if I had to extend on this I would probably choose to go for wrapping the int(...) around it. However, the most important thing is that the function returns items of only one type.

Sixth: One of the nice things of python is the for...else construct. The else portion is executed when break/return is not called from within the loop. Using this, you don't have to use a variable flag that gets set on each point where you break from the loop. I admit it is a weird feature and it took me quite some time to get used to it, but it is ideally suited for the loops where you try to find an item satisfying a condition. If you found it, you can just break. If you haven't found it, the else will be executed instead.

-
You are right, the for ... else construct is odd and can be useful is some situations. However, its not needed in this situation because the for loop returns a value instead of breaking off of one. Also, I would not use either N or T as variable names mainly because ALL_CAPS is the only way, in Python, we can 'define' constants. –  BeetDemGuise Jun 16 '14 at 19:43
@DarinDouglass: I actually thought of not using the else. It would still work, but when you're used to the for ... else, this seems to make the intend more clear. I agree with your remark on ALL_CAPS for constants, however I definitely hope nobody I share code with would choose 1-letter constants. In that case, t/n or num_challenges/challenge might be better variable names. –  Sjoerd Job Postmus Jun 16 '14 at 20:18

I am surprised no one said this.

you have too many new lines, someone did mention that you need to use whitespace correctly. You actually have newlines in the middle of an if then elif else block which I think should cause issues

a=0
items=[]

a=int(raw_input(''))
for i in range(0,a):
items.append(int(raw_input('')))

def Sherlock_and_The_Beast(items):
for i in items:

if i<3:
print -1
elif i%3==0:
print int(str(5)*i)
elif i==5:
print int(str(3)*i)

else:
flag=False
for j in range(i/3,-1,-1):
if (i-(3*j))%5==0:
flag=True
print int(str(5)*(3*j)+str(3)*(i-(3*j)))
break
if not flag:
print -1

Sherlock_and_The_Beast(items)


and this is what it should look like

items=[]

a=int(raw_input(''))
for i in range(0,a):
items.append(int(raw_input('')))

def Sherlock_and_The_Beast(items):
for i in items:
if i<3:
print -1
elif i%3==0:
print int(str(5)*i)
elif i==5:
print int(str(3)*i)
else:
flag=False
for j in range(i/3,-1,-1):
if (i-(3*j))%5==0:
flag=True
print int(str(5)*(3*j)+str(3)*(i-(3*j)))
break
if not flag:
print -1

Sherlock_and_The_Beast(items)


I also got rid of an unneeded declaration of the a variable, pretty much the next statement gives that variable a value, so just create the variable there instead

-
I did mention whitespace, albeit briefly. Extra lines are syntactically irrelevant in Python, although I agree that the OP could have been more consistent. –  jonrsharpe Jun 16 '14 at 21:18
Extra lines are horrible in a language like python, especially in the middle of an if block or a for loop. thank you for the info though @jonrsharpe I assumed it would freak out with the extra lines in there –  Malachi Jun 16 '14 at 22:02
The style guide does mention blank lines inside functions, but says only "Use blank lines in functions, sparingly, to indicate logical sections.". –  jonrsharpe Jun 17 '14 at 15:57
@jonrsharpe, thanks for the info. one answer mentions a for ...else block and so the spacing in the if statement there along with the indentation weirdness could mean that these are all typos, which means that the blank lines just make it more unclear what is going on in the code. –  Malachi Jun 17 '14 at 17:29