So I have a list of 1s and 0s:

[1, 1, 0, 0, 1, 1, 0, 1, 1, 1]

and a list of numbers: [3, 4, 15]

I have to find all the prime factors of those numbers, and flip the states in the first list that correspond to the prime factors of those numbers.

So for the above example:

numbers[0] = 3, prime factors are just 3

So after the states were changed, the array look like:

[1, 1, 1, 0, 1, 0, 0, 1, 0, 1], so every (i + 1) % 3 == 0 positions were flipped

numbers[1] = 4, prime factors are just 2

So after the states were changed, the array look like:

[1, 0, 1, 1, 1, 1, 0, 0, 0, 0]

numbers[3] = 15, prime factors are just 3, 5

So after the states were changed, the array look like:

[1, 0, 0, 1, 1, 0, 0, 0, 1, 0]

[1, 0, 0, 1, 0, 0, 0, 0, 1, 1]

Heres what i have so far:

from collections import Counter
def prime_factors(num): i = 2 factors = [] while i * i < = num: if (num % i): i += 1 else: num //= i factors.append(i) if (num > 1): factors.append(num) return list(set(factors))
def flip(states, numbers): factors = [] for num in numbers: factors.extend(prime_factors(num)) facotrs = Counter(factors) for key, val in factors.items(): if val % 2: for i in range(len(states)): if ((i + 1) % factor == 0): states[i] = 1 if states[i] == 0 else 0 return states

This works fine, but for large lists, it TLEs.

How do I fix this to make it faster?

3

3 Answers

for key, val in factors.items(): if val % 2: for i in range(len(states)): if ((i + 1) % factor == 0): states[i] = 1 if states[i] == 0 else 0

In the second for-loop, you don't need to start at 0 in range(len(states)). You can start with factor-1.

In states[i] = 1 if states[i] == 0 else 0,

you can replace this line with XOR operator:

states[i] = states[i]^1.

Try to optimize the prime number generator with the sieve of Eratosthenes. Should work withing a couple seconds for numbers less than 10⁷

import math;
def sieve_primes(number): a = [True if n>=2 and n%2==1 or n==2 else False for n in range(number+1)]; for x in range(3, (int)(math.sqrt(number))): if a[x]: for xx in range(x*x, number, x): a[xx] = False; primes = [] for i in range(len(a)): if a[i]: primes.append(i); return primes;

Also, you could avoid multiple calls to the prime generator by finding the biggest number that you'll need to factorize, generating primes for it and storing them for later lookup.

This part:

 for i in range(len(states)): if ((i + 1) % factor == 0): states[i] = 1 if states[i] == 0 else 0

seems too elaborate. How about (untested!):

 for i in range(factor - 1, len(states), factor): states[i] = 1 - states[i]

? That is, jump directly to all only the indices i such that i+1 is divisible by factor.

Making factoring very fast

Here's suitable sieve code as mentioned in a comment. If the maximum possible number "is large", of course this is an absurd approach. But you haven't told us. If it's up to a few million, this goes fast.

# Return list `sf` such that sf[i] is the smallest prime
# factor of `i`, for 2 <= i <= maxn.
def sieve(maxn): from math import isqrt sf = list(range(maxn + 1)) for i in range(4, len(sf), 2): sf[i] = 2 for p in range(3, isqrt(maxn) + 1, 2): if sf[p] == p: for i in range(p * p, len(sf), p + p): if sf[i] == i: sf[i] = p return sf

The whole thing

Here's a whole program. Code for sieve() was already given. Once that's called, it never needs to be called again.

It's often the case that successfully completing timed "programming challenges" crucially relies on the stated input constraints. You were asked several times to tell us what they were, but to no avail. My educated guess is that they put a relatively low limit on the maximum number that needs to be factored. The program here exploits that. But if they didn't put limits on it, there's scant hope for "a fast" solution, because efficient factoring of truly large integers remains a difficult, open research problem.

The method here tries to balance the time and space needed for preprocessing against the time needed to factor. It may or may not be "the best" tradeoff, depending on the still-unknown-to-us input constraints. For example, if the maximum number is "quite" small, you could fully compute - and store - the unique prime factors for every possible number in advance (although a sieve method would remain the fastest easy way to do that).

# Return list of unique prime factors of n.
def upf(n, sf): result = [] while n > 1: p = sf[n] result.append(p) n //= p while n % p == 0: n //= p return result
MAXN = 1_000_000
sf = sieve(MAXN)
def crunch(nums, bits, sf): from collections import defaultdict pcount = defaultdict(int) for num in nums: for p in upf(num, sf): pcount[p] += 1 for p, count in pcount.items(): if count & 1: for i in range(p - 1, len(bits), p): bits[i] = 1 - bits[i]
nums = [3, 4, 15]
bits = [1, 1, 0, 0, 1, 1, 0, 1, 1, 1]
expected = [1, 0, 0, 1, 0, 0, 0, 0, 1, 1]
crunch(nums, bits, sf)
assert bits == expected

11

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy