Codility – Page 5

Solution to Abs-Distinct by codility

29 Jan

Question: https://codility.com/demo/take-sample-test/abs_distinct Question Name: AbsDistinct In the original requirement, expected worst-case space complexity is O(N). But actually, O(1) is enought.

def solution(A):

abs_distinct = 1

current = max(abs(A[0]), abs(A[-1]))

index_head = 0

index_tail = len(A)-1

while index_head <= index_tail:

# We travel the array from the greatest

# absolute value to the smallest.

former = abs(A[index_head])

if former == current:

# Skip the heading elements, whose

# absolute values are the same with

# current recording one.

index_head += 1

continue

latter = abs(A[index_tail])

if latter == current:

# Skip the tailing elements, whose

# absolute values are the same with

# current recording one.

index_tail -= 1

continue

# At this point, both the former and

# latter has different absolute value

# from current recorded one.

if former >= latter:

# The next greatest value is former

current = former

index_head += 1

else:

# The next greatest value is latter

current = latter

index_tail -= 1

# Meet with a new absolute value

abs_distinct += 1

return abs_distinct

Solution to Binary-Gap by codility

29 Jan

Question: https://codility.com/demo/take-sample-test/binary_gap Question Name: BinaryGap

def solution(N):

max_gap = 0

current_gap = 0

# Skip the tailing zero(s)

while N > 0 and N%2 == 0:

N //= 2

while N > 0:

remainder = N%2

if remainder == 0:

# Inside a gap

current_gap += 1

else:

# Gap ends

if current_gap != 0:

max_gap = max(current_gap, max_gap)

current_gap = 0

N //= 2

return max_gap

Solution to alpha2010 (Prefix-Set) by codility

29 Jan

Question: https://codility.com/demo/take-sample-test/prefix_set Question Name: alpha2010 or PrefixSet At the first glance, I think the set of Python is the best choice. Actually, the set solution passed all the test, and got 100/100 grade.

def solution(A):

alphabet = set()

for element in A:

alphabet.add(element)

for index in xrange(len(A)):

alphabet.discard(A[index])

if len(alphabet) == 0:

return index

BUT, acording to the time complexity … Read More »

Solution to Count-Semiprimes by codility

28 Jan

Question: https://codility.com/demo/take-sample-test/count_semiprimes Question Name: CountSemiprimes

def solution(N, P, Q):

from math import sqrt

# Find out all the primes with Sieve of Eratosthenes

prime_table = [False]*2+[True]*(N-1)

prime = []

prime_count = 0

for element in xrange(2, int(sqrt(N))+1):

if prime_table[element] == True:

prime.append(element)

prime_count += 1

multiple = element * element

while multiple <= N:

prime_table[multiple] = False

multiple += element

for element in xrange(int(sqrt(N))+1, N+1):

if prime_table[element] == True:

prime.append(element)

prime_count += 1

# Compute the semiprimes information

semiprime = [0] * (N+1)

# Find out all the semiprimes.

# semiprime[i] == 1 when i is semiprime, or

# 0 when i is not semiprime.

for index_former in xrange(prime_count-1):

for index_latter in xrange(index_former, prime_count):

if prime[index_former]*prime[index_latter] > N:

# So large that no need to record them

break

semiprime[prime[index_former]*prime[index_latter]] = 1

# Compute the number of semiprimes until each position.

# semiprime[i] == k means:

# in the range (0,i] there are k semiprimes.

for index in xrange(1, N+1):

semiprime[index] += semiprime[index-1]

# the number of semiprimes within the range [ P[K], Q[K] ]

# should be semiprime[Q[K]] - semiprime[P[K]-1]

question_len = len(P)

result = [0]*question_len

for index in xrange(question_len):

result[index] = semiprime[Q[index]] - semiprime[P[index]-1]

return result

Solution to Count-Non-Divisible by codility

28 Jan

Question: https://codility.com/demo/take-sample-test/count_non_divisible Question Name: CountNonDivisible

def solution(A):

from math import sqrt

A_max = max(A)

A_len = len(A)

# Compute the frequency of occurrence of each

# element in array A

count = {}

for element in A:

count[element] = count.get(element,0)+1

# Compute the divisors for each element in A

divisors = {}

for element in A:

# Every nature number has a divisor 1.

divisors[element] = [1]

# In this for loop, we only find out all the

# divisors less than sqrt(A_max), with brute

# force method.

for divisor in xrange(2, int(sqrt(A_max))+1):

multiple = divisor

while multiple <= A_max:

if multiple in divisors and not divisor in divisors[multiple]:

divisors[multiple].append(divisor)

multiple += divisor

# In this loop, we compute all the divisors

# greater than sqrt(A_max), filter out some

# duplicate ones, and combine them.

for element in divisors:

temp = [element/div for div in divisors[element]]

# Filter out the duplicate divisors

temp = [item for item in temp if item not in divisors[element]]

divisors[element].extend(temp)

# The result of each number should be, the array length minus

# the total number of occurances of its divisors.

result = []

for element in A:

result.append(A_len-sum([count.get(div,0) for div in divisors[element]]))

return result

Solution to boron2013 (Flags) by codility

27 Jan

Question: https://codility.com/demo/take-sample-test/flags Question Name: boron2013 or Flags The official solution is here. UPDATE 2014-10-02: thanks to Piotrek Martynowicz, a bug is found and fixed.

def solution(A):

from math import sqrt

A_len = len(A)

next_peak = [-1] * A_len

peaks_count = 0

first_peak = -1

# Generate the information, where the next peak is.

for index in xrange(A_len-2, 0, -1):

if A[index] > A[index+1] and A[index] > A[index-1]:

next_peak[index] = index

peaks_count += 1

first_peak = index

else:

next_peak[index] = next_peak[index+1]

if peaks_count < 2:

# There is no peak or only one.

return peaks_count

max_flags = 1

max_min_distance = int(sqrt(A_len))

for min_distance in xrange(max_min_distance + 1, 1, -1):

# Try for every possible distance.

flags_used = 1

flags_have = min_distance-1 # Use one flag at the first peak

pos = first_peak

while flags_have > 0:

if pos + min_distance >= A_len-1:

# Reach or beyond the end of the array

break

pos = next_peak[pos+min_distance]

if pos == -1:

# No peak available afterward

break

flags_used += 1

flags_have -= 1

max_flags = max(max_flags, flags_used)

return max_flags

Solution to Peaks by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/peaks Question Name: Peaks UPDATE on July 18th 2015: Many thanks to @Antonio Correia (https://34.145.67.234/2014/solution-to-peaks-by-codility/#comment-11725) !!! @Antonio Correia found a huge bug in my solution, even though it passed the codility.com. The bug has been fixed.

def solution(A):

from math import sqrt

A_len = len(A)

peaks_until_here = [0]*A_len

# Retrieve how many peaks exist from beginning to current

# position.

for index in range(1, A_len-1):

peaks_until_here[index] = peaks_until_here[index-1]

if A[index] > A[index-1] and A[index] > A[index+1]:

peaks_until_here[index] += 1

if A_len < 3 or peaks_until_here[-2] == 0:

# The array is too short to have a peak. OR

# There is no peak in this array.

return 0

peaks_until_here[-1] = peaks_until_here[-2]

max_blocks = 0

# Compute every possible partition plan, and find out the

# one with most blocks.

for candidate in range(1, int(sqrt(A_len))+1, 1):

if A_len % candidate == 0:

blocks, block_size = candidate, A_len//candidate

# Check the first block.

if peaks_until_here[0] < peaks_until_here[block_size-1]:

# Check the following blocks.

for each_block in range(block_size, A_len, block_size):

if peaks_until_here[each_block-1] == \

peaks_until_here[each_block+block_size-1]:

# No peak is found in the next block

# This partition plan is not accepted

break

else:

max_blocks = blocks

if candidate * candidate == A_len:

# If candidate is equal to sqrt(A_len) exactly,

# candidate would equal to A_len//candidate.

continue

block_size, blocks = candidate, A_len//candidate

# Check the first block.

if peaks_until_here[0] < peaks_until_here[block_size-1]:

# Check the following blocks.

for each_block in range(block_size, A_len, block_size):

if peaks_until_here[each_block-1] == \

peaks_until_here[each_block+block_size-1]:

# No peak is found in the next block

# This partition plan is not accepted

break

else:

return blocks

return max_blocks

Solution to Min-Perimeter-Rectangle by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/min_perimeter_rectangle Question Name: MinPerimeterRectangle Let the length of one side be len_1, and the length of one adjacent side be len_2. For a rectangle with a constant area, the perimeter is minimized when the difference between len_1 and len_2, … Read More »

Solution to Max-Slice-Sum by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/max_slice_sum Question Name: MaxSliceSum The classic maximum subarray problem. It should be the very first question in this lesson.

def solution(A):

max_slice_ending_here = A[0]

max_slice = A[0]

for element in A[1:]:

max_slice_ending_here = max(element, max_slice_ending_here+element)

max_slice = max(max_slice, max_slice_ending_here)

return max_slice

Solution to Max-Profit by codility

25 Jan

Question: http://codility.com/demo/take-sample-test/max_profit Question Name: MaxProfit For this question, we have to travel from the last element to the first one.

def solution(A):

days = len(A)

# If the number of days is zero or one, there

# is no time to get profit.

if days < 2:

return 0

max_price_from_here = A[days-1]

max_profit = 0

for index in xrange(days-2, -1, -1):

# max_price_from_here-A[index] means the maximum

# profit from current day to end.

max_profit = max(max_profit, max_price_from_here-A[index])

max_price_from_here = max(A[index], max_price_from_here)

return max_profit

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...