Python – Page 6 – Code Says

Solution to Find Minimum in Rotated Sorted Array II by LeetCode

21 Dec

Question: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ Question Name: Find Minimum in Rotated Sorted Array II This question is essentially the same as the prevous one.

class Solution:

# @param num, a list of integer

# @return an integer

def findMin(self, num):

if num[0] < num[-1]:

# Completely sorted

return num[0]

elif len(num) < 5:

# The input is small enough to do a linear search.

return min(num)

else:

# The length of input is greater than 2. So the division won't get

# an empty list.

# The input may be or may be not sorted.

mid = (len(num) - 1) // 2

return min(self.findMin(num[:mid]), self.findMin(num[mid:]))

Solution to Find Minimum in Rotated Sorted Array by LeetCode

20 Oct

Question: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array/ Question Name: Find Minimum in Rotated Sorted Array

class Solution:

# @param num, a list of integer

# @return an integer

def findMin(self, num):

if num[0] < num[-1]:

# Completely sorted

return num[0]

elif len(num) < 3:

# The input is small enough to do a linear search.

return min(num)

else:

# The length of input is greater than 2. So the division won't get

# an empty list.

mid = (len(num) - 1) // 2

return min(self.findMin(num[:mid]), self.findMin(num[mid:]))

Solution to Maximum Product Subarray by LeetCode

29 Sep

Question: https://oj.leetcode.com/problems/maximum-product-subarray/ Question Name: Maximum Product Subarray The following solution is not the optimal. Because the recursion is not necessary. But recursion does make the coding easier.

class Solution:

# @param A, a list of non-zero integers

# @return an integer

def maxProductWithoutZero(self, A):

# Two base cases for this recursive method.

if len(A) == 0: return 0

if len(A) == 1: return A[0]

negativeCount = len([i for i in A if i < 0])

if negativeCount % 2 == 0:

# There are even number of negative integers. The product of all them

# is a positive integer as the maximum product among all subarrays.

return reduce(lambda x, y: x * y, A, 1)

else:

# There are odd number of negative integers. We divide the array into

# two subarray: one without the first negative integer, and the other

# without the last negative integer.

firstNeg = 0

while firstNeg < len(A):

if A[firstNeg] < 0: break

firstNeg += 1

lastNeg = len(A) - 1

while lastNeg >= 0:

if A[lastNeg] < 0: break

lastNeg -= 1

return max(self.maxProductWithoutZero(A[:lastNeg]),

self.maxProductWithoutZero(A[firstNeg + 1:]))

# @param A, a list of integers

# @return an integer

def maxProduct(self, A):

begin, end = 0, 0

if A.count(0) != 0: maxProd = 0

else: maxProd = A[0]

# Use 0 (zero) as delimiter to split the original array into small ones,

# which do not contain 0.

while end < len(A):

if A[end] != 0:

end += 1

else:

maxProd = max(maxProd, self.maxProductWithoutZero(A[begin : end]))

end += 1

begin = end

return max(maxProd, self.maxProductWithoutZero(A[begin : end]))

Solution to Hills

7 Sep

Question Name: Hills Question Description: An integer array store the heights of some consecutive hills. Find a minimum integer N, so that you could increase/decrease the heights of the hills by any integer in range [0, N]. After the adjustment, … Read More »

Solution to Deviation

4 Sep

Question Name: Deviation Question Description: Given an array of integer elements and an integer d, please consider all the sequences of d consecutive elements in the array. For each sequence we compute the difference between the maximum and the minimum … Read More »

Solution to Delta2011 (Min-Abs-Sum) by codility

29 Jul

Question: https://codility.com/demo/take-sample-test/delta2011 Question Name: Delta2011 or Min-Abs-Sum or MinAbsSum I did not solve it in a golden way. The official solution is so elegant.

def solution(A):

# Since S could be 1 or -1, it does not matter that

# each element in A is positive or negative.

A = [abs(item) for item in A]

sumOfA = sum(A)

# Get the number distribution. So we do not need to try

# each number for multiple times.

numbers = {}

for item in A: numbers[item] = numbers.get(item, 0) + 1

# This is the KEY point.

# Typically, we will use possible = [False] * len to track, which numbers

# could be the result by summing up subsets of A.

# For a number, appeared for many times, there will be multiple attempts

# for it. But in this way, when we are trying number n,

# possible[i] == -1 means it is impossible.

# possible[i] == i >= 0 means it is possible and there are i n(s) left to use.

# So for ALL number n(s), we only need ONE scan over the record.

possible = [-1] * (sumOfA // 2 + 1)

possible[0] = 0

for number in numbers: # Try each distinct number

for trying in xrange(sumOfA//2+1):

if possible[trying] >= 0:

# Can be reached with previous numbers

possible[trying] = numbers[number]

elif trying >= number and possible[trying-number] > 0:

# Cannot be reached with only previous numbers.

# But could be achieved with previous numbers AND current one.

possible[trying] = possible[trying-number] - 1

# Divide the A into two parts: P and Q, with restriction P <= Q.

# So P <= sumOfA // 2 <= Q. We want the largest possible P, so that

# Q-P is minimized.

for halfSum in xrange(sumOfA//2, -1, -1):

if possible[halfSum] >= 0:

return sumOfA - halfSum - halfSum

raise Exception("Should never be here!")

return 0

Solution to Str-Symmetry-Point by codility

28 Jul

Question: https://codility.com/demo/take-sample-test/str_symmetry_point Question Name: Str-Symmetry-Point or StrSymmetryPoint

def solution(S):

sLen = len(S)

# Symmetry point is possible, when and only when the

# string's length is odd.

if sLen % 2 == 0: return -1

# With a odd-length string, the only possible symmetry

# point is the middle point.

mid = sLen // 2

begin, end = 0, sLen-1

# The middle point of an odd-length string is symmetry

# point, only when the string is symmetry.

while begin < mid:

if S[begin] != S[end]: return -1

begin += 1

end -= 1

return mid

Solution to Tie-Ropes by codility

28 Jul

Question: https://codility.com/demo/take-sample-test/tie_ropes Question Name: Tie-Ropes or TieRopes

def solution(K, A):

# The number of tied ropes, whose lengths

# are greater than or equal to K.

count = 0

# The length of current rope (might be a tied one).

length = 0

for rope in A:

length += rope # Tied with the previous one.

# Find a qualified rope. Prepare to find the

# next one.

if length >= K: count += 1; length = 0

return count

Solution to Count-Factors by codility

28 Jul

Question: https://codility.com/demo/take-sample-test/count_factors Question Name: Count-Factors or CountFactors

def solution(N):

candidate = 1

result = 0

while candidate * candidate < N:

# N has two factors: candidate and N // candidate

if N % candidate == 0: result += 2

candidate += 1

# If N is square of some value.

if candidate * candidate == N: result += 1

return result

Solution to Missing-Integer by codility

28 Jul

Question: https://codility.com/demo/take-sample-test/missing_integer Question Name: Missing-Integer or MissingInteger

def solution(A):

''' Solve it with Pigeonhole principle.

There are N integers in the input. So for the

first N+1 positive integers, at least one of

them must be missing.

'''

# We only care about the first N+1 positive integers.

# occurrence[i] is for the integer i+1.

occurrence = [False] * (len(A) + 1)

for item in A:

if 1 <= item <= len(A) + 1:

occurrence[item-1] = True

# Find out the missing minimal positive integer.

for index in xrange(len(A) + 1):

if occurrence[index] == False:

return index + 1

raise Exception("Should never be here.")

return -1

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...