Web Front-end
JS Tutorial
JavaScript program to calculate the inversion of size 3 in a given array
JavaScript program to calculate the inversion of size 3 in a given array
In this tutorial, we will learn to calculate the inversion of size 3 in a given array.
Problem Statement - We are given an array of length n containing distinct numeric entries. We need to find the total number of pairs of numbers of size 3 such that arr[i] > arr[j] > arr[k], where I
Here, we will first learn the brute force method, and then, we will optimize its time and space complexity.
Use brute force methods
In the brute force approach, we will use three nested for loops to find count reversals of size 3. The first loop iterates from 1 to n-2 elements, and the second loop iterates from the i-th element to the n-1-th element. If the previous element is greater than the next element, iterate over the array and find the element smaller than the middle element.
grammar
Users can use the brute force method following the syntax below to compute the inversion of size 3 in a given array.
for ( ) {
for ( ) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
algorithm
Step 1 - Iterate over the first n-2 elements using a for loop.
Step 2 - Iterate over m 1 to len-1 elements using a nested for loop.
Step 3 - In the nested for loop, check if array[m] is greater than array[n]. If so, iterate from the n 1th element to the last element.
Step 4 - If the element at the othth index is smaller than the element at the nth index, we can say that we found a valid inversion pair of size 3 and increase that The value 'cnt' variable is decremented by 1.
Step 5 - After all iterations of the for loop are completed, return the value of "cnt".
Example 1
In the example below, we implement a brute force method to find the total number of reversal pairs of size 3.
In the given array, the user can only observe 2 inversion pairs in the output. The first reversal pair is (10,5,4) and the second reversal pair is (20,5,4).
<html>
<body>
<h3> Using the <i> Brute force approach </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let len = array.length;
let cnt = 0;
for (let m = 0; m < len - 2; m++) {
for (let n = m + 1; n < len - 1; n++) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
Time and space complexity
Time complexity - Since we use three nested for loops, the time complexity is O(n^3).
Space complexity - When we use constant space, the space complexity is O(1).
Use two nested for loops
In this method, we will use two nested loops. We will find the total number of smaller elements to the right of the current element, and the total number of larger elements to the left. After that, we multiply the two to get the total number of reversals for a specific number.
grammar
Users can use two nested loops to calculate reversals of size 3 in JavaScript by following the syntax below.
for ( ) {
// find a smaller element on the right
for ()
if (array[m] < array[n])
right++;
// find bigger elements on the left
for ()
if (array[m] > array[n])
left++;
cnt += right * left;
}
algorithm
Step 1 - Iterate over n elements of the array using a for loop.
Step 2 - Use a for loop to find all elements to the right of the current element that are smaller than the current element.
Step 3 - Use the for loop again to find all elements to the left of the current element that are larger than the current element.
Step 4 - Multiply the values of the left and right variables and add them to the "cnt" variable.
Example 2
In the following example, we use two nested loops to find the total number of reversals of size 3, as shown in the above method. The user can observe that the output is the same as in the first method.
<html>
<body>
<h3> Using the <i> two nested loops </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let cnt = 0;
let len = array.length;
// Iterate through every element of the array
for (let m = 0; m < len - 1; m++) {
// count all element that are smaller than arr[m] and at the right to it
let right = 0;
for (let n = m - 1; n >= 0; n--)
if (array[m] < array[n])
right++;
// count all element that are greater than arr[m] and at the left to it
let left = 0;
for (let n = m + 1; n < len; n++)
if (array[m] > array[n])
left++;
// multiply left greater and right smaller elements
cnt += right * left;
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
Time and space complexity
Time complexity - Since we use two nested loops, the time complexity of the above method is O(n^2).
Space complexity - When we use constant space, the space complexity is O(1).
The user learned two methods to find count inversions of size 3 in a given array. In the first approach, we solved the problem using a brute force approach, and in the second approach, we further optimized the solution to reduce the time complexity.
The above is the detailed content of JavaScript program to calculate the inversion of size 3 in a given array. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
Replace String Characters in JavaScript
Mar 11, 2025 am 12:07 AM
Detailed explanation of JavaScript string replacement method and FAQ This article will explore two ways to replace string characters in JavaScript: internal JavaScript code and internal HTML for web pages. Replace string inside JavaScript code The most direct way is to use the replace() method: str = str.replace("find","replace"); This method replaces only the first match. To replace all matches, use a regular expression and add the global flag g: str = str.replace(/fi
8 Stunning jQuery Page Layout Plugins
Mar 06, 2025 am 12:48 AM
Leverage jQuery for Effortless Web Page Layouts: 8 Essential Plugins jQuery simplifies web page layout significantly. This article highlights eight powerful jQuery plugins that streamline the process, particularly useful for manual website creation
Build Your Own AJAX Web Applications
Mar 09, 2025 am 12:11 AM
So here you are, ready to learn all about this thing called AJAX. But, what exactly is it? The term AJAX refers to a loose grouping of technologies that are used to create dynamic, interactive web content. The term AJAX, originally coined by Jesse J
10 Mobile Cheat Sheets for Mobile Development
Mar 05, 2025 am 12:43 AM
This post compiles helpful cheat sheets, reference guides, quick recipes, and code snippets for Android, Blackberry, and iPhone app development. No developer should be without them! Touch Gesture Reference Guide (PDF) A valuable resource for desig
Improve Your jQuery Knowledge with the Source Viewer
Mar 05, 2025 am 12:54 AM
jQuery is a great JavaScript framework. However, as with any library, sometimes it’s necessary to get under the hood to discover what’s going on. Perhaps it’s because you’re tracing a bug or are just curious about how jQuery achieves a particular UI
10 jQuery Fun and Games Plugins
Mar 08, 2025 am 12:42 AM
10 fun jQuery game plugins to make your website more attractive and enhance user stickiness! While Flash is still the best software for developing casual web games, jQuery can also create surprising effects, and while not comparable to pure action Flash games, in some cases you can also have unexpected fun in your browser. jQuery tic toe game The "Hello world" of game programming now has a jQuery version. Source code jQuery Crazy Word Composition Game This is a fill-in-the-blank game, and it can produce some weird results due to not knowing the context of the word. Source code jQuery mine sweeping game
How do I create and publish my own JavaScript libraries?
Mar 18, 2025 pm 03:12 PM
Article discusses creating, publishing, and maintaining JavaScript libraries, focusing on planning, development, testing, documentation, and promotion strategies.
jQuery Parallax Tutorial - Animated Header Background
Mar 08, 2025 am 12:39 AM
This tutorial demonstrates how to create a captivating parallax background effect using jQuery. We'll build a header banner with layered images that create a stunning visual depth. The updated plugin works with jQuery 1.6.4 and later. Download the
