diff options
Diffstat (limited to '3.3.py')
| -rw-r--r-- | 3.3.py | 96 |
1 files changed, 96 insertions, 0 deletions
@@ -0,0 +1,96 @@ +#!/usr/bin/python2 + +# Find the Access Codes +# ===================== + +# In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need +# access to it. But the only door leading to the LAMBCHOP chamber is secured +# with a unique lock system whose number of passcodes changes daily. Commander +# Lambda gets a report every day that includes the locks' access codes, but +# only she knows how to figure out which of several lists contains the access +# codes. You need to find a way to determine which list contains the access +# codes once you're ready to go in. + +# Fortunately, now that you're Commander Lambda's personal assistant, she's +# confided to you that she made all the access codes "lucky triples" in order +# to help her better find them in the lists. A "lucky triple" is a tuple (x, y, +# z) where x divides y and y divides z, such as (1, 2, 4). With that +# information, you can figure out which list contains the number of access +# codes that matches the number of locks on the door when you're ready to go in +# (for example, if there's 5 passcodes, you'd need to find a list with 5 "lucky +# triple" access codes). + +# Write a function solution(l) that takes a list of positive integers l and +# counts the number of "lucky triples" of (li, lj, lk) where the list indices +# meet the requirement i < j < k. The length of l is between 2 and 2000 +# inclusive. The elements of l are between 1 and 999999 inclusive. The answer +# fits within a signed 32-bit integer. Some of the lists are purposely +# generated without any access codes to throw off spies, so if no triples are +# found, return 0. + +# For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, +# 6], making the answer 3 total. + + +# Test cases +# ========== +# Your code should pass the following test cases. +# Note that it may also be run against hidden test cases not shown here. + +# Input: +# solution.solution([1, 2, 3, 4, 5, 6]) +# Output: +# 3 + +# Input: +# solution.solution([1, 1, 1]) +# Output: +# 1 + +## O(n^2) +def solution(l): + c = [0] * len(l) + count = 0 + for i in range(0, len(l)): + for j in range(0, i): + if l[i] % l[j] == 0: + c[i] = c[i] + 1 + count = count + c[j] + return count + +## O(n^3) +def solution2(l): + c = 0 + while len(l) > 2: + t = l[1:] + for id,i in enumerate(t): + if i % l[0] == 0: + for j in t[(id + 1):]: + if j % i == 0: + c += 1 + l = l[1:] + return c + +## Way too much memory, it's not even funny +## python is supposed to do list comprehension in a good way, lol +def solution3(l): + return len([(i, j, k) + for id,i in enumerate(l) + for jd,j in enumerate(l[(id+1):]) + for k in l[(id+jd+2):] + if j%i==0 and k%j==0]) + +def solve(l): + print(l) + print(solution(l)) + +solve([1, 2, 3, 3, 5, 2]) +solve([1, 2, 3, 4, 5, 6]) +solve([1, 2, 3, 3, 2, 1]) +solve([1 for x in xrange(2000)]) +solve([1, 1, 1]) +solve([]) +solve([2]) +solve([2, 5]) +solve([1, 5, 6]) +solve([1, 999999, 2]) |