Javascript solution to CodeSignal’s Contours Shifting

The Contours Shifting is the 109th task of the second level (The Core) of the Arcade task series in CodeSignal. This is one of the most challenging tasks out there. It requires a strong understanding of arrays and it doesn’t have any short solution ( or not yet ). When I usually finish a task, I always read other people’s solutions and compare them to mine. The site sorts solutions starting from the most upvoted. So most of the time, I come across some unexpected alternative solutions that are way clever than mine and usually shorter. For the Contours Shifting task, this wasn’t the case. All the solutions were long. It seems like this task got everyone struggling. For once I felt reassured.
I spent an interesting moment solving this task and that has pushed me to be curious knowing how other people will solve it. If you’re here because you got the same curiosity, I’d be happy to share my solution with you !

but before, here’s the task description:

CodeSignal The Core 109th task Contours Shifting

Mark got a rectangular array matrix for his birthday, and now he's thinking about all the fun things he can do with it. He likes shifting a lot, so he decides to shift all of its i-contours in a clockwise direction if i is even, and counterclockwise if i is odd.

Here is how Mark defines i-contours:

the 0-contour of a rectangular array as the union of left and right columns as well as top and bottom rows;
consider the initial matrix without the 0-contour: its 0-contour is the 1-contour of the initial matrix;
define 2-contour, 3-contour, etc. in the same manner by removing 0-contours from the obtained arrays.
Implement a function that does exactly what Mark wants to do to his matrix.

Example

For

matrix = [[ 1,  2,  3,  4],
           [ 5,  6,  7,  8],
           [ 9, 10, 11, 12],
           [13, 14, 15, 16],
           [17, 18, 19, 20]]
the output should be

contoursShifting(matrix) = [[ 5,  1,  2,  3],
                             [ 9,  7, 11,  4],
                             [13,  6, 15,  8],
                             [17, 10, 14, 12],
                             [18, 19, 20, 16]]
For matrix = [[238, 239, 240, 241, 242, 243, 244, 245]],
the output should be
contoursShifting(matrix) = [[245, 238, 239, 240, 241, 242, 243, 244]].

Note, that if a contour is represented by a 1 × n array, its center is considered to be below it.

For

matrix = [[238],
           [239],
           [240],
           [241],
           [242],
           [243],
           [244],
           [245]]
the output should be

contoursShifting(matrix) = [[245],
                             [238],
                             [239],
                             [240],
                             [241],
                             [242],
                             [243],
                             [244]]
If a contour is represented by an n × 1 array, its center is considered to be to the left of it.

Input/Output

[execution time limit] 4 seconds (js)

[input] array.array.integer matrix

Guaranteed constraints:
1 ≤ matrix.length ≤ 100,
1 ≤ matrix[i].length ≤ 100,
1 ≤ matrix[i][j] ≤ 1000.

[output] array.array.integer

The given matrix with its contours shifted.

The javascript solution to CodeSignal The Core 109th task Contours Shifting

function contoursShifting(matrix) {
    var directions = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0]
    ]
    var newMatrix = matrix.map(a => [...a])
    var originalMatrix = matrix.map(a => [...a])
    var level = 0
    while (matrix.length > 0 && matrix[0].length > 0) {
        var width = matrix[0].length
        var height = matrix.length
        var cells = []
        var reverseCells = []
        for (var i = 0; i < width; i++) {
            cells.push([0, i])
            if (height - 1 > 0)
                reverseCells.unshift([height - 1, i])
        }
        for (var i = 1; i < height - 1; i++) {
            cells.push([i, width - 1])
            if (width - 1 > 0)
                reverseCells.push([height - 1 - i, 0])
        }
        cells = [...cells, ...reverseCells]
        var shiftedCells = cells.slice()
        if (level % 2 == 1) shiftedCells.push(shiftedCells.shift())
        else shiftedCells.unshift(shiftedCells.pop())
        cells.forEach(function(a, i) {
            b = shiftedCells[i]
            newMatrix[a[0] + level][a[1] + level] = originalMatrix[b[0] + level][b[1] + level]
        })
        matrix = matrix.slice(1, -1).map(a => a.slice(1, -1))
        level++
    }
    return newMatrix
}

If you finished the task I’d be interested to read your solution, don’t hesitate to share it with me and the others in the comments !

15 Javascript tricks you wish you knew before

Javascript is a very advanced coding langage and its community is one of the largest on the internet, any web developer who’s got a minimal experience should be familiar with Javascript. It is a necessary langage in developing web applications. For most cases, a web developer spends a considerable amount of time coding with javascript when working on a web project. That’s why it’s important for any web developer to improve his js skills as much as he can, because that will definitely impact his productivity. One way to be more efficient in javascript is to be aware of the existence of some tricks that could make your way of coding better, these tricks have always been there, it’s just that few coders are aware of them because they’re uncommon, but if you learn them you’ll notice that you’ll start using them often.

In this article I am going to share with you some of the most useful javascript tricks. These tricks could make your code shorter but don’t forget, sometimes the price is having a code that will be less readable. So keep in mind, not all these tricks are considered “best practice” so you should use them depending on your situation.

1 Shorten an array

Did you know that you can shorten an array by changing its length property?

var a = [1 , 2 , 3]
a.length = 2 // now a is [1 , 2]

2 Convert all elements of an array

You have an array of strings you want to convert into numbers ? you can do it like this:

var strings=['1' , '2' , '3']
numbers = strings.map(Number) // [ 1 , 2 , 3]

This works for Boolean and String as well !

3 Remove duplicates from an array

Sets in javascript are like arrays however they can only contain unique values. You can remove duplicates from an array using this trick :

arr = [ 1 ,2 ,3 ,2 ,3, 4]
arrWithoutDuplicates = [...new Set(arr)] // [1 , 2 , 3 , 4]

4 Assign values to multiple variables at once

You can use destructuring to shorten up how you assign values to variables, see this example:

[a ,b , c] = [1 , 2 ,3] // a=1   b=2  c=3

You can use the same syntax to break down an array into multiple variables

5 Break the array map method loop

Have you ever wanted to be able to break a map loop like when you use the break statement inside a for loop? it is possible to get the array from the parameters of the callback function and mutate it to stop the loop, here’s how

[1 , 2 , 3 , 4].map(function(a,i,arr){
    if(a==3)
        arr.splice(1)
    console.log(a)
})
// console output:
// 1
// 2
// 3

this works for reduce, forEach, filter… and any array method that has the array in the parameters of its callback function

6 Increment an array element or initialize it in case it’s null

You can only increment an array element if it already has an initial value otherwise you get an error. This is why you usually need to initialize the element before incrementing it which means you have to write two instructions ( two lines of code ) but this can be done in a single instruction:

var arr = []
arr[0] = ++arr[0] || 1 // arr = [1]

7 Convert a number to binary

using the toString method, you can convert any number to its binary equivalent

Number(3).toString(2) // 11

This works for any base, all you have to do is to change the base number from 2 to any other base

8 The shortest way to sum an array

I don’t suggest using this trick at all because it’s not secure but it’s still worth sharing:

var arr = [1 , 2 , 3]
eval(arr.join("+")) // returns 6

you can replace + with any other arithmetic symbol, for example * will bring you the multiplication of all the array elements

9 Convert an array to a string and vice versa

You can use split and join to convert strings into arrays and arrays into strings:

"abc".split("") // [ "a" , "b" , "c" ]
[ "a" , "b" , "c" ].join("") // "abc"

10 clone an array

Javascript offers many ways to clone an array but using slice is my favorite method

var arr = [1 , 2 , 3]
var arr2 = arr.slice()

11 Dynamic variable name

Variable names can be set dynamically, this can be done like this

var myVarName = "counter"
window[myVarName] = 1 // counter = 1

12 For loop with two variables

We are all used to use the for loop with a single variable, but did you know that you can use more ?

for( var i = 0, j = 5; i<= 5; i++, j-- ){
    console.log("you took "+i+" apples. "+j+" are left")
}
// you took 0 apples. 5 are left
// you took 1 apples. 4 are left
// you took 2 apples. 3 are left
// you took 3 apples. 2 are left
// you took 4 apples. 1 are left
// you took 5 apples. 0 are left

And you can use as much variables as you like

13 Combine multiple switch cases in a single block

Sometimes you want to call the same code for two or more different switch cases. You don’t have to create two different blocks though. You can combine two or more cases into a single block by cascading the cases statements

switch(month){
    case("June"):
    case("July"):
    case("August"):
       console.log("it feels like summer")
    break;
}

14 Assign the same value to multiple variables in a row

Rather than writing multiple code lines when assigning the same value to multiple variables, you can do it in a single instruction like this:

var a = b = c = "hello"
// a = "hello"
// b = "hello"
// c = "hello"

15 preserve the accuracy of big integers

Long numbers aren’t well supported by javascript, big numbers lose their numeric precision. In most cases, this issue can be dealt with by adding an “n” to the number, by doing so you’re transforming it to a BigInt. Here are some few examples where this can be useful

99999999999999999 // will print 100000000000000000
99999999999999999n // will print 99999999999999999n

1000000000000000000001 // 1e+21
1000000000000000000001n // 1000000000000000000001n

9999999999999998 + 1  // 100000000000000000
9999999999999998n + 1n  // 9999999999999999n

Be careful though, BigInt isn’t like regular numeric type. Even if you can perform arithmetic operations like addition or multiplication, there are some exception you should be aware of before using them in production. I highly suggest you read about the BigInt Object and how it affects the traditional arithmetic operations.

Here are the most useful PHP 8 new features

PHP8 is out, now what would I tell you more? when and how they released it ? come on, I know you’re not here for that kind of information.
if you’re a regular and lazy php developer like me then you’d be interested to learn about PHP 8 key new features only, which means updates that applies mostly to your regular daily coding and not those updates that you’re going to learn about now then forget forever because, as an ordinary server side developer, you rarely come across a scenario where they might be needed.

Now what’s a PHP 8 key update for me? it’s anything that can save us if only a second on something we do very often, like for example the way we write loops, pass parameters to a function, how we manipulate arrays…etc.
One second here and one second there and you end up spending less time on repetitive syntaxes and focus more on what’s more important.
Also, a key feature is something that is now allowing you to do what you were not able to in the older version (PHP 7 or older).

I’ll try to give an example of a common scenario for each PHP 8 new feature I present. You can get a real understanding of how useful an update could be for you by looking at the examples.

let’s now leave introductions aside and explore each one of the most useful PHP 8 new features.

1.Trailing Comma in functions Parameter List

commas are so annoying when you manipulate function parameters. Especially when we pass a lot of parameters into a single function.
for example, sometimes you need to move the last parameter to a different position:

Not only you need to add a comma after positioning the parameter, but also you need to remove the last one in order to get a correct syntax, otherwise you’ll get the error:

                    
Parse error: syntax error, unexpected ‘)’ in C:\wamp\www\straightdev\index.php on line 11

but with php 8, leaving the trailing comma is no more a problem. You can now leave a comma after the last parameter like this:

insertUser($firstName,)

so now, moving parameters becomes more practical and doesn’t require any extra step like adding or removing a comma

2.Named parameters

I wished this new php 8 feature existed before now, it would have saved me a lot of time. What are named parameters? it’s simply a more organised way to pass parameters to a function. This is very useful when declaring too many parameters, especially when you use optional parameters. Here’s a scenario where you would benefit of such a feature:

function insertUser($firstName, $lastName, $gender, $email, $pass,  $country , $city , $dateOfBirth ){
     //insert user into database
}

As you can see, the function insertUser contains 8 parameters. The problem when using too many parameters is that it’s hard to remember their order at the moment when you call the function, so you end up losing time trying to recall the position of each one, but you generally end up revisiting the function declaration before being able to format your function call correctly. Without mentioning that it’s always hard to read and understand a function call when it contains too many parameters

insertUser("straight", "developer", 0, "admin@straightdev.com", "*******",  "algeria" , "annaba" , "1991-01-01" );

Thanks to the php 8 named parameters new feature. Not only you’re no more obliged to respect the order of the parameters, but your function is now way more readable ! This feature allow you to name each one of your parameters when you pass them, here’s how:

insertUser(
          firstName: "straight",
          lastName: "developer",
          gender: 0,
          email: "admin@straightdev.com",
          pass: "*******",  
          country: "algeria" , 
          city: "annaba" , 
          dateOfBirth: "1991-01-01" ,
);

Reading this portion of code is easy isn’t it? imagine the impact this new way of writing function calls can have on your code !
you can now position your parameters the way you want, php 8 will assign the values according to their names

insertUser(
          email: "admin@straightdev.com",
          firstName: "straight",
          dateOfBirth: "1991-01-01", 
          lastName: "developer",
          gender: 0, 
          country: "algeria" , 
          city: "annaba" , 
          pass: "*******", 
);

But this feature is mostly useful when you use optional parameters. Let me show an example so you can better understand what I am saying, let’s suppose we declared this function:

function insertBook($authorId, $title, $price, $pages = false, $lang = false, $editor = false, $year = false ){
     //insert book into database
}

As you can see our function insertBook() contains 4 optional parameters. They’re optionals because they’re not always available to us therefore we might sometimes pass false or just skip the parameters rather than passing a real value.
The problem when you use too many optional parameters is that sometimes, you just can’t skip writing the default value for optional parameters. To illustrate this, let’s suppose that we want to insert a book and that we only have its author, title, price and year.
the function call will look like:

insertBook(123, "Les misérables", 20, false, false, false, 1862 )

As you can see $pages, $lang and $editor might be optionals yet we had to pass false in order to be able to reach the $year position and pass a value there. There’s clearly something wrong about this way of writing parameters especially if you deal with functions that have a high number of optional parameters. PHP 8 new named parameters feature solves the problem :

insertBook(
          authorId: 123,
          title: "Les misérables",
          price: 20, 
          year: 1862,
);

The most interesting part with the new named parameters feature is that you can still combine between the traditional and the new way of passing parameters. By doing that, you can avoid repetition as much as you can. Ideal when you’re a lazy developer and you want to use this feature only when it’s really needed, example:

insertBook(123,"Les misérables",20, year: 1862);

3.The match expression

The best way to understand the match expression is to compare it to switch. See it like a nicer and shorter way to return a specific value based on different conditions. Let’s take a common switch statement as an example and write its equivalence with match:

switch ($extension) {
            case 'jpg':
                $fileType="image";
                break;
            case 'flv':
                $fileType="video";
                break;
            
            default:
               $fileType="unknown";
                break;
        }

Our switch statement determines the type of a file based on its extension, simple. Now, let’s try reproducing the same thing using match

  $fileType = match ($extension) {
            'jpg' => 'image',
            'flv' => 'video',
            default => 'unknown',
        }

The first thing to notice is that match takes way less space than switch. It is easier to read and memorize. I know many beginners who tend to avoid using switch just because they find it hard to use its syntax but I think that with match no one will ever complain. As you can see, match does not require a break statement and it automatically returns a value ! But that’s not all, match offers a better approach to handle multiple matching conditions. For example, let’s say we wanted to cover more image extensions in our previous example. First let’s try doing this with switch:

switch ($extension) {
            case 'jpg':
            case 'jpeg':
            case 'png':
                $fileType="image";
                break;
            case 'flv':
                $fileType="video";
                break;
            
            default:
               $fileType="unknown";
                break;
        }

If you’re not familiar with this syntax, writing cascading case keys just like we did is how you combine multiple conditions into one matching block using the switch statement. Now, here’s how you do the same using match:

  $fileType = match ($extension) {
            "jpg" , "jpeg" , "png" => "image",
            "flv" => "video",
            default => "unknown",
        }

simple enough isn’t it? you can combine all your matching conditions using nothing but a comma.
At the end, match is a nice alternative to switch but not all the time. match has its own limitations too. For example, match doesn’t allow more than one expression per condition unlike switch , so keep note of this before you start thinking that you’re no more in need of it.

4.the str_contains function

have you ever asked yourself why there had never been a proper php function to detect if a string contains a substring? just like javascript:

str.includes("world");

so you won’t have to do this ugly thing in PHP:

strpos($str, "world") !== false; 

Since it’s better late than never, one of PHP 8 new features is a function that checks if a string contains a substring or not, this is how you use the php 8 new str_contains function:

str_contains($str, 'world');

I think that there’s nothing I can clarify more. The first parameter is the haystack and the second one is the needle. The function returns true only if the needle is in the haystack otherwise it returns false.

I think I mentioned the most useful PHP 8 new features for me. There are too many other updates you might like to know about. You can read about them here.
I am sure the other features are interesting too. But They don’t have as much impact on a regular php developer’s life as the ones I mentioned. If you think that there’s any other php 8 new feature that has a potential of doing a big impact on how ordinary php developers write php then let me know in the comments and explain how.

Did an employer asked you to sell him your upwork account on freelancer.com?

Fake projects everywhere on freelancer these last years, it becomes hard to determine if a serious client is hiding behind a new project and whether one should invest time and bids on projects posted by new clients.

I used to not miss bidding on projects that are posted by new employers on Freelancer.com as beginner employers are more likely to get in touch with you than the ones who’re used to hire on the platform to understand why let me explain you how things work on Freelancer.com

This is why new employers are more likely to contact you on freelancer.com:

Any employer who’s used to Freelancer.com knows perfectly how hard it is to find the right freelancer for his job, you can write the most clarifying project description, attach screenshots and schemes, mention the right skills, use the most appropriate title and offer the best price for the task yet if you don’t really know what you’re doing there’s big chances you chose the wrong person resulting a lost of money and time, what’s more you end up losing faith in the platform this is because a big majority of people who bids there are not skilled for the job yet they make a proposal and try to convince you just so you award them the project.

Being deceived by many workers, clients ends up being more cautious and less open to communicate, that’s why bidding on their projects is hard because no matter how honest you could be in your bid proposal you’ll end up being put in the same basket as the ones who pretend to be honest or at least think they are.

New employers however still ignore the fact that most bidders are just telling them what they want to hear, that’s why they’re more engaged in communication and usually contact more bidders than usual employers. Yes this could be a bad thing but if by chance you’re an honest freelancer and they come across your bid and decided to trust you then it’s a win-win for both of you, therefore projects that are posted by this category of employers contains often more chances for you to get hired than than the usual ones.

This is why I became less motivated to bid on projects that are posted by new employers

The only thing that used to bother me when I bid on projects from new employers is the fact that they might not be serious, in fact one important criteria to determine if a client is a serious one is to see how many reviews he has and of course the more the number is high the more the client is likely to be serious.

But a new phenomenon is now taking place, more and more fake projects are being posted everyday, nothing suspicious, in fact the project description looks like a normal one, worse, it’s more appealing than the others. At the beginning it looks like a regular project so you bid on it but when the client gets in touch with you he’s asking for something different than what his project description has made you think: I’d like to buy your Upwork account.

Most of the time, as soon as the client (the scammer) gets your first answer he then tries to get in touch with you outside the platform (freelancer) using many strategies.


But why do this people want to buy your upwork account, or pay you to use it, and why you shouldn’t even think about doing it? I’ll provide more details about this very soon but until then here’s how looks like one of the scammer’s proposals:

I am from China and my name is xxxx xxx.

I have a good plan that can help you earn extra money.

I am a talented fullstack engineer and I used to work in UpWork.

As you know, UpWork is a job platform that helps freelancers to find remote jobs.

I used to use my UpWork account to find jobs and I earned 4k~8k USD every month.

Unfortunately, my account has been suspended for some reason and I lost my jobs.

My suggestion is, I use your UpWork account (I can’t create more with my identity because I already used it.) and earn money. And I give you some of it maybe 10% or more. It will be about 0.4k ~ 0.8k depending on the earning amount.

There’s nothing to lose on your side, instead, you can earn extra money without any effort.

If you don’t have an UpWork account, we can create together using TeamViewer, AnyDesk or any other screen sharing application.

It’s worth trying, isn’t it?

Please send me a message if you’re interested.

My skype id: live:.cid.xxxxxxxxxxxxxx

Thank you,

regards


Codility.com Flags task solution with 100% score

Find the maximum number of flags that can be set on mountain peaks.

“Flags” is the third task of the prime and composite numbers lesson serie on Codility.com, tagged with the flag “respectable” this task is harder than its previous CountFactors and in this article I am going to share with you my solution which has a score of 100% in matter of corectness and performance but before we elaborate the solution here’s the task description on Codility.com:

Codility.com Flags task description

A non-empty array A consisting of N integers is given.

peak is an array element which is larger than its neighbours. More precisely, it is an index P such that 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1].

For example, the following array A: A[0] = 1 A[1] = 5 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

has exactly four peaks: elements 1, 3, 5 and 10.

You are going on a trip to a range of mountains whose relative heights are represented by array A, as shown in a figure below. You have to choose how many flags you should take with you. The goal is to set the maximum number of flags on the peaks, according to certain rules.

Flags can only be set on peaks. What’s more, if you take K flags, then the distance between any two flags should be greater than or equal to K. The distance between indices P and Q is the absolute value |P − Q|.

For example, given the mountain range represented by array A, above, with N = 12, if you take:

  • two flags, you can set them on peaks 1 and 5;
  • three flags, you can set them on peaks 1, 5 and 10;
  • four flags, you can set only three flags, on peaks 1, 5 and 10.

You can therefore set a maximum of three flags in this case.

Write a function:

function solution(A);

that, given a non-empty array A of N integers, returns the maximum number of flags that can be set on the peaks of the array.

For example, the following array A: A[0] = 1 A[1] = 5 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..400,000];
  • each element of array A is an integer within the range [0..1,000,000,000].

Flags task 100% solution in javascript

first step would be to form an array that will contain the position of each peak, so you basically iterate on the array A and test whether a value is greater than the previous and the next value at the same time, then push it into the peaks array if it is the case, once the peaks array is filled then comes the most challenging part which is to calculate the number of flags that we can put on the peaks.
remember, the distance between each two flags should not be less than the total number of flags, which means that the number of flags is determined by the distances between the peaks so there lays our solution.
Since we can know what’s the whole distance between the first peak and the last one then we can know that the number of flags cannot exceed a certain number, for example, if we take the same example as the task description, it results this array of peaks:

[ 1, 3, 5, 10]

the total distance here is 9 which is the difference between the value of the last element and the first element of the array, knowing this, we can assume that the flags number will never exceed 3 because if that happens then the total distance will be more than 9 which is impossible, for example, if I give you 4 flags and asked you to start from 1 then put them one after another alongside with respecting the rule : keep a distance of 4 between each two flags you’ll obtain this configuration of flags: [1,5,9,14] and as you can see the final element 14 is greater than the farest peak from our array: 9 which makes 4 an impossible value for k (the number of flags)
that being said, in order to calculate the maximum value for k we just need to calculate the square root of the distance between the first and the last peak just as follows:

var root=Math.floor(Math.sqrt(peaks[peaks.length-1]-peaks[0]))

then we iterate on the peaks but starting from the square root then going down until we obtain the maximum number of the flags that can be placed on the peaks.
Here’s the full solution:

function solution(A) {
    var peaks=[]
    for(var i=1;i<A.length-1;i++){
        if(A[i-1]<A[i] && A[i]>A[i+1])
        peaks.push(i)
    }
    if(peaks.length<2)
    return peaks.length
    var root=Math.floor(Math.sqrt(peaks[peaks.length-1]-peaks[0]))
    for(i=root+1;i>0;i--){
        var distanceSum=0
        var flags=1
        for(var j=0;j<peaks.length-1;j++){
            var current=peaks[j]
            var next=peaks[j+1]
            var difference=Math.abs(next-current)
            if((difference+distanceSum)>=i){
                flags++
                distanceSum=0
            }
            else
            distanceSum+=difference
        if(flags==i)
        return flags
        }
    }
}

the solution is getting 100% score but I feel like there’s a better approach then this but I honestly couldn’t think of it, if by chance you happen to have a better solution then don’t hesitate to share it with me !

MinPerimeterRectangle task javascript solution 100% score on Codility.com

Find the minimal perimeter of any rectangle whose area equals N.

This is the third task of Prime and composite numbers lesson serie, it’s tagged with the flag “painless” and in this article I am going to share with you a javascript solution that gets 100% score in matter of performance and correctness so before we begin here’s the task description on Codility.com:

Codility’s MinPerimeterRectangle task description

An integer N is given, representing the area of some rectangle.

The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).

The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.

For example, given integer N = 30, rectangles of area 30 are:

  • (1, 30), with a perimeter of 62,
  • (2, 15), with a perimeter of 34,
  • (3, 10), with a perimeter of 26,
  • (5, 6), with a perimeter of 22.

Write a function:

function solution(N);

that, given an integer N, returns the minimal perimeter of any rectangle whose area is exactly equal to N.

For example, given an integer N = 30, the function should return 22, as explained above.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000,000].

MinPerimeterRectangle task javascript 100% solution

In this solution I use the same technique as in the previous task “CountFactors” which is to take advantage of the square root of N but before we elaborate this, let’s talk first about how are we going to calculate the minimal perimeter of any rectangle whose area equals N,
knowing that the perimeter of a rectangle is equal 2 * (A + B) and that the area N is equal to A * B which means in other words that A & B are factors of N, we can come to the conclusion that the perimeter of a rectangle is minimal when the difference between the length of the sides A & B is minimal, so the more the value of A is close to the value of B the more we approach to a minimal perimeter and since A & B are factor of N then we already know how we can obtain the most close A & B values and that’s with the help of the square root of N, remember that √n divides all the factors of N into two symmetric groups which means that the more we get close to √n the more we approach to the factors pair that we’re looking for, in other words the A & B we’re looking for are the biggest factor before √n and its symmetric factor: the smallest factor after √n, this is basically the divisors that comes directly before and after √n
if we take the same example as the task description:30 here’s the list of its divisors along with the square root :

1 2 3 5 √30 6 10 15 30

notice that the minimal A & B are found around √n
so the minimal A,B here are 5,6 which are the divisors around √30
now that you understand this, here’s the full code which is a full implementation of what I just explained above

function solution(N) {
    var root=Math.round(Math.sqrt(N))
    for(var i=root;i>=1;i--){
        if(N%i==0){
            var a=i
            var b=N/a
            return 2*(a+b)
        }
    }
}

if you have a better solution or even the same solution but with less lines of code then don’t hesitate to share it with me in the comments below

how to obtain a score of 100% on the CountFactors task on Codility.com

1. CountFactors
Count factors of given number n.

Here comes the first task of the lesson 10: prime and composite numbers on Codility, the task is CountFactors and it’s probably the easiest of all the four tasks in this lessons serie, the others being: Flags, MinPerimeterRectangle and Peaks. You can find the 100% score solution of each one them in my other posts !
The solution I am going to share with you is a javascript based function and has a time complexity of O(sqrt(N)), first things first, here’s the task description on Codility:

Codility Prime and composite numbers: CountFactors task description

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

function solution(N);

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..2,147,483,647]

Counting the divisors that are lower than the square root of the number

The solution is very simple and straightforward and it has already been explained in the “reading materiel (pdf)” you can find in the prime and composite numbers lesson page, to obtain the number of factors of a number n, we simply count how much divisors are there before we reach the root square of n ( √n ), that’s because √n splits n’s factors into two equal groups, for example let’s take the number 100, so √n would be 10 right? here’s the list of all the factors of n:

1, 2, 5, 10, 20, 50, 100

as you can see, there are exactly as much factors in the left of 10 as in the right which means that there is a smart solution that would use half performances comparing to the most obvious solution which is to loop on every number lower than n and test if it’s a divisor or not.
knowing that, we can simply increment our counter by 2 instead of 1 each time we encounter a divisor then stop as soon as we reach the square root:

var root=Math.sqrt(N)    
for(var i=1;i<=root;i++){ 
}

then we test if i is a divisor of n on each iteration using the modulus operator (%)

 var root=Math.sqrt(N)    
 for(var i=1;i<=root;i++){ 
   if(N%i==0)
    factors+=2; 
 } 

but that’s not enough yet because when the square root is a factor then it needs to be counted too, but you only add one to the counter this time, because if the square root is a factor then its symmetric factor would be the square root itself, after all √n * √n = n

if(i==root)
  factors++
else
  factors+=2;

Keep in mind that the square root of n can only be a factor only if it’s a whole number which is not the case when n=10 for example.
Here’s the final javascript code:

function solution(N) {
    var factors=0
    var root=Math.sqrt(N)
    for(var i=1;i<=root;i++){
        if(N%i==0)
            if(i==root)
                factors++
            else
                factors+=2;
    }
    return factors
}

a 100% score javascript solution to the MaxSliceSum Exercise on Codility.com

Find a maximum sum of a compact subsequence of array elements.

In this article I am going to share with you a 100% score solution to the 3rd task of the Maximum slice problem lessons (chapter 9) on Codility.com, the solution has a O(n) time complexity and follows the same technique described in the chapter documentation pdf file (the last solution)
first, here’s the full task description from Codility.com:

Codility Max Slice Sum task description

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + … + A[Q].

Write a function:

function solution(A);

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0

the function should return 5 because:

  • (3, 4) is a slice of A that has sum 4,
  • (2, 2) is a slice of A that has sum −6,
  • (0, 1) is a slice of A that has sum 5,
  • no other slice of A has sum greater than (0, 1).

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • each element of array A is an integer within the range [−1,000,000..1,000,000];
  • the result will be an integer within the range [−2,147,483,648..2,147,483,647].

get a 100% score on Max Slice Sum task with this solution

As I mentioned before, you can use the same technique as the one suggested by the chapter lesson document

 def golden_max_slice(A):
   max_ending = max_slice = 0
   for a in A:
     max_ending = max(0, max_ending + a)
     max_slice = max(max_slice, max_ending)
 return max_slice

however that won’t be enough because in case the array A contains only negative numbers then the result won’t be correct, for example:

A=[-1]

the function will return 0 while the right answer is -1 !

In order to take care of this exception all we need to do is to add a variable that keeps note of the highest number of the array while we iterate over each element, once the loop is done, if the max slice sum is equal to zero which is 99% when the array contains only negative values, in this case we return the highest number from the array instead of returning zero simply because the sum of two or more negative numbers will never be greater than the value of one them. Here’s the full solution :

function solution(A) {
    var sum=0
    var max=A[0]
    var maxCell=A[0]
    for(a of A){
        sum=Math.max(0,sum+a)
        max=Math.max(max,sum)
        maxCell=Math.max(maxCell,a)
    }
    if(max==0)
        return maxCell
    return max
}

I don’t think there exist a solution that will take less lines than this but if you think you can surprise me then don’t hesitate to do so by sharing your solution in the comments below !

a 100% score javascript solution to the MaxProfit Exercise on Codility.com

Given a log of stock prices compute the maximum possible earning.

the MaxProfit exercise is the second task from the Maximum slice problem lesson (9th lesson) on Codility.com and in this article I am going to share with you a O(N) time complexity 100% score javascript solution but before here’s the task description on codility.com:

Codility MaxProfit task description

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that: A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

function solution(A);

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that: A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [0..400,000];
  • each element of array A is an integer within the range [0..200,000].

Codility MaxProfit task solution with javascript (100% score)

The solution is straight forward and uses the same approach as the last solution in codility PDF chapter 9: Maximum slice problem.
First of all, we create a new array and name it profits, this array will contain the profit or loss between the value of each cell and the one next to it (i & i+1), to do so, we loop over the main array A and calculate the difference like the following:

for(var i=0;i<A.length-1;i++){
        var current=A[i]
        var next=A[i+1]
        var difference=next-current
        profits.push(difference)
    }

Once we obtain the array of differences, all we have to do now is to find which slice of the array has the largest sum which can be obtained using this code:

 for(var p of profits){
        max=Math.max(0,max+p)
        bestProfit=Math.max(bestProfit,max)
    }

Here’s the final code:

function solution(A) {
    var profits=[]
    var max=0
    var bestProfit=0
    for(var i=0;i<A.length-1;i++){
        var current=A[i]
        var next=A[i+1]
        var difference=next-current
        profits.push(difference)
    }
    for(var p of profits){
        max=Math.max(0,max+p)
        bestProfit=Math.max(bestProfit,max)
    }
    if(bestProfit<0)
    return 0
    return bestProfit
}

Understanding Codility O(n) final solution on the max slice lesson (chapter 9 pdf)

as it’s already been said in the lesson pdf file on Codility, the implementation of this solution is simple however understanding it might be challenging at first so let me simplify it for you:
to understand this solution let us suppose that our array contains only positive numbers, if this is true then the maximum slice would be inevitably the whole array, and the largest sum would become the total sum of the array right ?
for example:

profits=[ 4, 5, 2, 1 ]

the largest possible sum here is 12 which equals the overall sum of the array itself

so calculating the largest sum of an array containing only positive numbers is as simple as calculating the total sum the whole array:

 for(var p of profits){
        max+=p
    }
return max

but what if we add some negative values to the array?

profits=[ 4, 5, -10, 2 , 1 ]

would the largest possible sum of the array equals the overall sum of it ? of course not, the largest sum here becomes 9 while the overall sum is 2 so our previous rule is no more valid because once negative values are included, the overall sum of the array decreases accordingly making it possible to have a slice that has a larger sum than the overall sum.
to deal with this, all we have to do is to loop on the array like if we’re trying to calculate the total sum of it, but this time, we reset the sum to zero each time the sum reaches a negative number:

max=Math.max(0,max+p)

this is equivalent to

if(max+p<0)
   max=0
else
   max+=p

and the loop should look like:

 for(var p of profits){
        max=Math.max(0,max+p)
        bestProfit=Math.max(bestProfit,max)
 }

a 100% score javascript solution to the EquiLeader Exercise on Codility.com

In this article I am going to share with you a javascript solution to the second exercise of the leaders lessons part of codility lessons, the solution gets 100% score in matter of correctness and performance and has a time complexity of O(N)

EquiLeader task description on Codility:

Find the index S such that the leaders of the sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N – 1] are the same.

A non-empty array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N − 1] have leaders of the same value.

For example, given array A such that: A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

we can find two equi leaders:

  • 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
  • 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

The goal is to count the number of equi leaders.

Write a function:

function solution(A);

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given: A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

the function should return 2, as explained above.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..100,000];
  • each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

Looping from right then from left

In order to determine if a specific index of the main array A is an “equi leader” or not we must:
-know what’s the leader of the subsequence that ends with the index in question
-know what’s the leader of the other subsequence (from the index until the end of the array)
if we have both of these information, all we need to do is to compare between the leader of the left subsequence and the leader of the right one and we’re able to say if an index is an equiLeader.
In order to do so, first we need to calculate the leader of each index of the array starting from the right, the first loop in my solution fills the leaders array giving us the leader of all the possible subsequences from the right. after that comes the second loop, this does the same thing but it goes from the left, at the same time it checks if an element is an equi leader or not and increments a counter each time it finds one,
at the end the counter will have exactly the number of equi leaders on A.

function solution(A) {
    var rightCounters=[]
    var leftCounters=[]
    var leaders=[]
    for(var i=A.length-1;i>=0;i--){
        var current=A[i]
        if(typeof rightCounters[current]=="undefined"){
            rightCounters[current]=1
        }
        else
            rightCounters[current]++
            if(rightCounters[current]>(A.length-i)/2)
            leaders[i]=current
            else{
                if(i!=A.length-1 && rightCounters[leaders[i+1]]>(A.length-i)/2)
                    leaders[i]=leaders[i+1]
                else
                    leaders[i]=-1
            }
    }
    var counter=0;
    var lastLeader=A[0]
    for(var i=0;i<A.length;i++){
        var current=A[i]
        if(typeof leftCounters[current]=="undefined")
            leftCounters[current]=1
        else
            leftCounters[current]++
        if(leftCounters[current]>(i+1)/2){
            if(current==leaders[i+1])
                counter++
            lastLeader=current;

        }
            else{
                if(lastLeader!=-1 && leftCounters[lastLeader]>(i+1)/2){
                    if(lastLeader==leaders[i+1])
                        counter++
                }
                else
                    lastLeader=-1
            }
        }
        return counter;
}

Do you have a solution that has a score of 100% and contains less lines of code? if so then don’t hesitate to share it with me in the comments below !