We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
My codes take 10s in Colab and can't pass test case 6. Can anyone help me optimize?
Thanks in advance!
fromitertoolsimportpermutationsdefSubstring_Divisibility(n):### This part takes so much timepermStr=[]foriinpermutations(range(0,n+1)):s=''.join(map(str,i))permStr.append(s)### __________________total=0forsinpermStr:iflen(s[1:4])==3:ifint(s[1:4])%2==0:passelse:continueelse:passiflen(s[2:5])==3:ifint(s[2:5])%3==0:passelse:continueelse:passiflen(s[3:6])==3:ifint(s[3:6])%5==0:passelse:continueelse:passiflen(s[4:7])==3:ifint(s[4:7])%7==0:passelse:continueelse:passiflen(s[5:8])==3:ifint(s[5:8])%11==0:passelse:continueelse:passiflen(s[6:9])==3:ifint(s[6:9])%13==0:passelse:continueelse:passiflen(s[7:10])==3:ifint(s[7:10])%17==0:passelse:continueelse:passtotal+=int(s)returntotalif__name__=='__main__':n=int(input())print(Substring_Divisibility(n))
If you got TLE, you may consider using generator instead of regular for loop or listcomp. I used for loop first, then moved on to listcomp, nothing worked. Finally, using generator I got over test case 6. There's nothing wrong in your code, so far I am concerned
The main difference between your approach and my approach is How to generate permutations and check for divisibility
Approach:-
This code takes an integer input n and defines a function solve() to find the sum of all numbers formed by permutations of the digits 0 to n, which satisfy a certain divisibility condition. The divisible_test() function checks if a given number formed by the permutation satisfies the divisibility condition for a set of prime numbers. The condition checks if the sub-strings of length 3 in the number are divisible by the corresponding prime numbers in the divisible list.
The solve() function iterates through all permutations of the numbers 0 to n and checks if each permutation satisfies the divisibility condition using divisible_test(). If a permutation satisfies the condition, it converts the permutation into an integer and adds it to the sum. Finally, the function returns the sum of all such numbers.
The code uses the itertools.permutations function to generate all permutations of the numbers 0 to n. It then applies the divisible_test() function to each permutation to check for divisibility. If a permutation satisfies the divisibility condition, its corresponding number is added to the sum.
'''
from itertools import permutations
n = int(input())
def solve():
return sum(int(''.join(map(str, num))) for num in permutations(range(n+1)) if divisible_test(num))
divisible=[2, 3, 5, 7, 11, 13, 17]
def divisible_test(num):
return all((num[i+1]*100+num[i+2]*10+num[i+3]) %p == 0 for i, p in enumerate(divisible[:n-2]))
print(solve())
'''
'''
from itertools import permutations
n = int(input())
def solve():
return sum(int(''.join(map(str, num))) for num in permutations(range(n+1)) if divisible_test(num))
divisible=[2, 3, 5, 7, 11, 13, 17]
def divisible_test(num):
return all((num[i+1]*100+num[i+2]*10+num[i+3]) %p == 0 for i, p in enumerate(divisible[:n-2]))
print(solve())
'''
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Project Euler #43: Sub-string divisibility
You are viewing a single comment's thread. Return to all comments →
My codes take 10s in Colab and can't pass test case 6. Can anyone help me optimize?
Thanks in advance!
If you got TLE, you may consider using generator instead of regular for loop or listcomp. I used for loop first, then moved on to listcomp, nothing worked. Finally, using generator I got over test case 6. There's nothing wrong in your code, so far I am concerned
If it's just 1/2 cases run the same code in pypy3. It works.
Try this code:
Note:-
The main difference between your approach and my approach is How to generate permutations and check for divisibility
Approach:- This code takes an integer input n and defines a function solve() to find the sum of all numbers formed by permutations of the digits 0 to n, which satisfy a certain divisibility condition. The divisible_test() function checks if a given number formed by the permutation satisfies the divisibility condition for a set of prime numbers. The condition checks if the sub-strings of length 3 in the number are divisible by the corresponding prime numbers in the divisible list.
The solve() function iterates through all permutations of the numbers 0 to n and checks if each permutation satisfies the divisibility condition using divisible_test(). If a permutation satisfies the condition, it converts the permutation into an integer and adds it to the sum. Finally, the function returns the sum of all such numbers.
The code uses the itertools.permutations function to generate all permutations of the numbers 0 to n. It then applies the divisible_test() function to each permutation to check for divisibility. If a permutation satisfies the divisibility condition, its corresponding number is added to the sum.
''' from itertools import permutations n = int(input()) def solve(): return sum(int(''.join(map(str, num))) for num in permutations(range(n+1)) if divisible_test(num)) divisible=[2, 3, 5, 7, 11, 13, 17] def divisible_test(num): return all((num[i+1]*100+num[i+2]*10+num[i+3]) %p == 0 for i, p in enumerate(divisible[:n-2])) print(solve()) '''
''' from itertools import permutations n = int(input()) def solve(): return sum(int(''.join(map(str, num))) for num in permutations(range(n+1)) if divisible_test(num)) divisible=[2, 3, 5, 7, 11, 13, 17] def divisible_test(num): return all((num[i+1]*100+num[i+2]*10+num[i+3]) %p == 0 for i, p in enumerate(divisible[:n-2])) print(solve()) '''