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.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #43: Sub-string divisibility
  4. Discussions

Project Euler #43: Sub-string divisibility

  • leduckhai
     + 3 comments

    My codes take 10s in Colab and can't pass test case 6. Can anyone help me optimize?

    Thanks in advance!

    from itertools import permutations
 
def Substring_Divisibility(n):
  ### This part takes so much time
  permStr = []
  for i in permutations(range(0,n+1)):
    s = ''.join(map(str,i)) 
    permStr.append(s)
  ### __________________
  
  total = 0
  for s in permStr:
    if len(s[1:4]) == 3: 
      if int(s[1:4])%2 == 0: pass
      else: continue
    else: 
      pass

    if len(s[2:5]) == 3: 
      if int(s[2:5])%3 == 0: pass
      else: continue
    else: 
      pass

    if len(s[3:6]) == 3: 
      if int(s[3:6])%5 == 0: pass
      else: continue
    else: 
      pass

    if len(s[4:7]) == 3: 
      if int(s[4:7])%7 == 0: pass
      else: continue
    else: 
      pass

    if len(s[5:8]) == 3: 
      if int(s[5:8])%11 == 0: pass
      else: continue
    else: 
      pass

    if len(s[6:9]) == 3: 
      if int(s[6:9])%13 == 0: pass
      else: continue
    else: 
      pass

    if len(s[7:10]) == 3: 
      if int(s[7:10])%17 == 0: pass
      else: continue
    else: 
      pass
      
    total += int(s)
      
  return total

if __name__ == '__main__':
  n = int(input())
  print(Substring_Divisibility(n))