Skip to main content
Code Review

Return to Question

Tweeted twitter.com/StackCodeReview/status/1251254113515552768
Bumped by Community user
Bumped by Community user
added 192 characters in body; edited tags; edited title
Source Link
Jamal
Jamal
  • 35.2k
  • 13
  • 134
  • 238

Given an array, find all its elements that can become a leader, after increasing by 1 all of the numbers in some segment of a given length

Challenge:

Integers K, M and a non-empty array A consisting of N integers, not bigger than M, are given.

The leader of the array is a value that occurs in more than half of the elements of the array, and the segment of the array is a sequence of consecutive elements of the array.

You can modify A by choosing exactly one segment of length K and increasing by 1 every element within that segment.

The goal is to find all of the numbers that may become a leader after performing exactly one array modification as described above.

Write a function:

def solution(K, M, A)

that, given integers K and M and an array A consisting of N integers, returns an array of all numbers that can become a leader, after increasing by 1 every element of exactly one segment of A of length K. The returned array should be sorted in ascending order, and if there is no number that can become a leader, you should return an empty array. Moreover, if there are multiple ways of choosing a segment to turn some number into a leader, then this particular number should appear in an output array only once.

For example, given integers K = 3, M = 5 and the following array A:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3

the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:

 A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3

and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3

and 3 will be the leader.

And, for example, given integers K = 4, M = 2 and the following array:

 A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2

the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000]; K is an integer within the range [1..N]; each element of array A is an integer within the range [1..M].

Challenge:

Integers K, M and a non-empty array A consisting of N integers, not bigger than M, are given.

The leader of the array is a value that occurs in more than half of the elements of the array, and the segment of the array is a sequence of consecutive elements of the array.

You can modify A by choosing exactly one segment of length K and increasing by 1 every element within that segment.

The goal is to find all of the numbers that may become a leader after performing exactly one array modification as described above.

Write a function:

def solution(K, M, A)

that, given integers K and M and an array A consisting of N integers, returns an array of all numbers that can become a leader, after increasing by 1 every element of exactly one segment of A of length K. The returned array should be sorted in ascending order, and if there is no number that can become a leader, you should return an empty array. Moreover, if there are multiple ways of choosing a segment to turn some number into a leader, then this particular number should appear in an output array only once.

For example, given integers K = 3, M = 5 and the following array A:

A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3

the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:

A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3

and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:

A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3

and 3 will be the leader.

And, for example, given integers K = 4, M = 2 and the following array:

A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2

the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.

Write an efficient algorithm for the following assumptions:

  • N and M are integers within the range [1..100,000];
  • K is an integer within the range [1..N];
  • Each element of array A is an integer within the range [1..M].

Given an array, find all its elements that can become a leader, after increasing by 1 all of the numbers in some segment of a given length

Challenge:

Integers K, M and a non-empty array A consisting of N integers, not bigger than M, are given.

The leader of the array is a value that occurs in more than half of the elements of the array, and the segment of the array is a sequence of consecutive elements of the array.

You can modify A by choosing exactly one segment of length K and increasing by 1 every element within that segment.

The goal is to find all of the numbers that may become a leader after performing exactly one array modification as described above.

Write a function:

def solution(K, M, A)

that, given integers K and M and an array A consisting of N integers, returns an array of all numbers that can become a leader, after increasing by 1 every element of exactly one segment of A of length K. The returned array should be sorted in ascending order, and if there is no number that can become a leader, you should return an empty array. Moreover, if there are multiple ways of choosing a segment to turn some number into a leader, then this particular number should appear in an output array only once.

For example, given integers K = 3, M = 5 and the following array A:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3

the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:

 A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3

and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3

and 3 will be the leader.

And, for example, given integers K = 4, M = 2 and the following array:

 A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2

the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000]; K is an integer within the range [1..N]; each element of array A is an integer within the range [1..M].

Given an array, find all its elements that can become a leader

Challenge:

Integers K, M and a non-empty array A consisting of N integers, not bigger than M, are given.

The leader of the array is a value that occurs in more than half of the elements of the array, and the segment of the array is a sequence of consecutive elements of the array.

You can modify A by choosing exactly one segment of length K and increasing by 1 every element within that segment.

The goal is to find all of the numbers that may become a leader after performing exactly one array modification as described above.

Write a function:

def solution(K, M, A)

that, given integers K and M and an array A consisting of N integers, returns an array of all numbers that can become a leader, after increasing by 1 every element of exactly one segment of A of length K. The returned array should be sorted in ascending order, and if there is no number that can become a leader, you should return an empty array. Moreover, if there are multiple ways of choosing a segment to turn some number into a leader, then this particular number should appear in an output array only once.

For example, given integers K = 3, M = 5 and the following array A:

A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3

the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:

A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3

and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:

A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3

and 3 will be the leader.

And, for example, given integers K = 4, M = 2 and the following array:

A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2

the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.

Write an efficient algorithm for the following assumptions:

  • N and M are integers within the range [1..100,000];
  • K is an integer within the range [1..N];
  • Each element of array A is an integer within the range [1..M].
I have included some examples.
Source Link
Harith
Harith
  • 131
  • 2

For example, given integers K = 3, M = 5 and the following array A:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3

the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:

 A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3

and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3

and 3 will be the leader.

And, for example, given integers K = 4, M = 2 and the following array:

 A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2

the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000]; K is an integer within the range [1..N]; each element of array A is an integer within the range [1..M].

My Solution

My Solution

For example, given integers K = 3, M = 5 and the following array A:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3

the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:

 A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3

and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:

 A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3

and 3 will be the leader.

And, for example, given integers K = 4, M = 2 and the following array:

 A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2

the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000]; K is an integer within the range [1..N]; each element of array A is an integer within the range [1..M].

My Solution

Source Link
Harith
Harith
  • 131
  • 2

Given an array, find all its elements that can become a leader, after increasing by 1 all of the numbers in some segment of a given length

I was successful in solving a challenge in codility, but my solution failed performance tests. How can I improve my solution?

Challenge:

Integers K, M and a non-empty array A consisting of N integers, not bigger than M, are given.

The leader of the array is a value that occurs in more than half of the elements of the array, and the segment of the array is a sequence of consecutive elements of the array.

You can modify A by choosing exactly one segment of length K and increasing by 1 every element within that segment.

The goal is to find all of the numbers that may become a leader after performing exactly one array modification as described above.

Write a function:

def solution(K, M, A)

that, given integers K and M and an array A consisting of N integers, returns an array of all numbers that can become a leader, after increasing by 1 every element of exactly one segment of A of length K. The returned array should be sorted in ascending order, and if there is no number that can become a leader, you should return an empty array. Moreover, if there are multiple ways of choosing a segment to turn some number into a leader, then this particular number should appear in an output array only once.

My Solution

def modify(segment): return [e+1 for e in segment] def dominant(A): d = dict() lenOfHalfA = int(len(A)/2) domList = [] for i in A: if not i in d: d[i] = 1 else: d[i] = d[i]+1 for key, value in d.items(): if value > lenOfHalfA: domList.append(key) return domList def solution(K, M, A): # write your code in Python 3.6 dominantList = [] x = 0 while x <= len(A) - K: modifiedA = A[:] modifiedA[x:K+x] = modify(A[x:K+x]) dominantList += dominant(modifiedA) x += 1 return list(set(dominantList))