Count smaller elements on right side
Here given code implementation process.
// C Program
// Count smaller elements on right side
#include <stdio.h>
// Counting the number of smaller element of right side
// in each element of array
void countElement(int arr[], int size)
{
// Loop controlling variables
int i = 0;
int j = 0;
int count = 0;
// Outer loop (0...size)
for (i = 0; i < size ; ++i)
{
count = 0;
// Inner loop (i+1...size)
for (j = i + 1; j < size; ++j)
{
if(arr[i] > arr[j])
{
// When get new larger element
count++;
}
}
printf(" [%d] : %d \n",arr[i],count);
}
}
int main(int argc, char const *argv[])
{
// Given array elements
int arr[] = {7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8};
// Get the size
int size = sizeof(arr)/sizeof(arr[0]);
countElement(arr,size);
return 0;
}
Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0/*
Java program
Count smaller elements on right side
*/
public class Element
{
// Counting the number of smaller element of right side
// in each element of array
public void countElement(int[] arr, int size)
{
// Element counter
int count = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Outer loop (0...size)
for (i = 0; i < size; ++i)
{
count = 0;
// Inner loop (i+1...size)
for (j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
// When get new larger element
count++;
}
}
System.out.print(" [" + arr[i] + "] : " + count + " \n");
}
}
public static void main(String[] args)
{
Element task = new Element();
int[] arr = {
7 , 2 , 6 , 9 , 13 , 5 , 11 , 12 , 6 , 3 , 1 , 8
};
int size = arr.length;
task.countElement(arr, size);
}
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Count smaller elements on right side
*/
class Element
{
public:
// Counting the number of smaller element of right side
// in each element of array
void countElement(int arr[], int size)
{
// Element counter
int count = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Outer loop (0...size)
for (i = 0; i < size; ++i)
{
count = 0;
// Inner loop (i+1...size)
for (j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
// When get new larger element
count++;
}
}
cout << " [" << arr[i] << "] : " << count << " \n";
}
}
};
int main()
{
Element task = Element();
int arr[] = {
7 , 2 , 6 , 9 , 13 , 5 , 11 , 12 , 6 , 3 , 1 , 8
};
int size = sizeof(arr) / sizeof(arr[0]);
task.countElement(arr, size);
return 0;
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0// Include namespace system
using System;
/*
C# program
Count smaller elements on right side
*/
public class Element
{
// Counting the number of smaller element of right side
// in each element of array
public void countElement(int[] arr, int size)
{
// Element counter
int count = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Outer loop (0...size)
for (i = 0; i < size; ++i)
{
count = 0;
// Inner loop (i+1...size)
for (j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
// When get new larger element
count++;
}
}
Console.Write(" [" + arr[i] + "] : " + count + " \n");
}
}
public static void Main(String[] args)
{
Element task = new Element();
int[] arr = {
7 , 2 , 6 , 9 , 13 , 5 , 11 , 12 , 6 , 3 , 1 , 8
};
int size = arr.Length;
task.countElement(arr, size);
}
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0<?php
/*
Php program
Count smaller elements on right side
*/
class Element
{
// Counting the number of smaller element of right side
// in each element of array
public function countElement( & $arr, $size)
{
// Element counter
$count = 0;
// Loop controlling variables
$i = 0;
$j = 0;
// Outer loop (0...size)
for ($i = 0; $i < $size; ++$i)
{
$count = 0;
// Inner loop (i+1...size)
for ($j = $i + 1; $j < $size; ++$j)
{
if ($arr[$i] > $arr[$j])
{
// When get new larger element
$count++;
}
}
echo " [". $arr[$i] ."] : ". $count ." \n";
}
}
}
function main()
{
$task = new Element();
$arr = array(7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8);
$size = count($arr);
$task->countElement($arr, $size);
}
main();Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0/*
Node Js program
Count smaller elements on right side
*/
class Element
{
// Counting the number of smaller element of right side
// in each element of array
countElement(arr, size)
{
// Element counter
var count = 0;
// Loop controlling variables
var i = 0;
var j = 0;
// Outer loop (0...size)
for (i = 0; i < size; ++i)
{
count = 0;
// Inner loop (i+1...size)
for (j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
// When get new larger element
count++;
}
}
process.stdout.write(" [" + arr[i] + "] : " + count + " \n");
}
}
}
function main()
{
var task = new Element();
var arr = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8];
var size = arr.length;
task.countElement(arr, size);
}
main();Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0# Python 3 program
# Count smaller elements on right side
class Element :
# Counting the number of smaller element of right side
# in each element of array
def countElement(self, arr, size) :
# Element counter
count = 0
# Loop controlling variables
i = 0
j = 0
# Outer loop (0...size)
while (i < size) :
count = 0
j = i + 1
# Inner loop (i+1...size)
while (j < size) :
if (arr[i] > arr[j]) :
# When get new larger element
count += 1
j += 1
print(" [", arr[i] ,"] : ", count ," ")
i += 1
def main() :
task = Element()
arr = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8]
size = len(arr)
task.countElement(arr, size)
if __name__ == "__main__": main()Output
[ 7 ] : 6
[ 2 ] : 1
[ 6 ] : 3
[ 9 ] : 5
[ 13 ] : 7
[ 5 ] : 2
[ 11 ] : 4
[ 12 ] : 4
[ 6 ] : 2
[ 3 ] : 1
[ 1 ] : 0
[ 8 ] : 0# Ruby program
# Count smaller elements on right side
class Element
# Counting the number of smaller element of right side
# in each element of array
def countElement(arr, size)
# Element counter
count = 0
# Loop controlling variables
i = 0
j = 0
# Outer loop (0...size)
while (i < size)
count = 0
j = i + 1
# Inner loop (i+1...size)
while (j < size)
if (arr[i] > arr[j])
# When get new larger element
count += 1
end
j += 1
end
print(" [", arr[i] ,"] : ", count ," \n")
i += 1
end
end
end
def main()
task = Element.new()
arr = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8]
size = arr.length
task.countElement(arr, size)
end
main()Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0
/*
Scala program
Count smaller elements on right side
*/
class Element
{
// Counting the number of smaller element of right side
// in each element of array
def countElement(arr: Array[Int], size: Int): Unit = {
// Element counter
var count: Int = 0;
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Outer loop (0...size)
while (i < size)
{
count = 0;
j = i + 1;
// Inner loop (i+1...size)
while (j < size)
{
if (arr(i) > arr(j))
{
// When get new larger element
count += 1;
}
j += 1;
}
print(" [" + arr(i) + "] : " + count + " \n");
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Element = new Element();
var arr: Array[Int] = Array(7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8);
var size: Int = arr.length;
task.countElement(arr, size);
}
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0/*
Swift 4 program
Count smaller elements on right side
*/
class Element
{
// Counting the number of smaller element of right side
// in each element of array
func countElement(_ arr: [Int], _ size: Int)
{
// Element counter
var count: Int = 0;
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Outer loop (0...size)
while (i < size)
{
count = 0;
j = i + 1;
// Inner loop (i+1...size)
while (j < size)
{
if (arr[i] > arr[j])
{
// When get new larger element
count += 1;
}
j += 1;
}
print(" [", arr[i],"] : ", count ," ");
i += 1;
}
}
}
func main()
{
let task: Element = Element();
let arr: [Int] = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8];
let size: Int = arr.count;
task.countElement(arr, size);
}
main();Output
[ 7 ] : 6
[ 2 ] : 1
[ 6 ] : 3
[ 9 ] : 5
[ 13 ] : 7
[ 5 ] : 2
[ 11 ] : 4
[ 12 ] : 4
[ 6 ] : 2
[ 3 ] : 1
[ 1 ] : 0
[ 8 ] : 0/*
Kotlin program
Count smaller elements on right side
*/
class Element
{
// Counting the number of smaller element of right side
// in each element of array
fun countElement(arr: Array < Int > , size: Int): Unit
{
// Element counter
var count: Int;
// Loop controlling variables
var i: Int = 0;
var j: Int;
// Outer loop (0...size)
while (i < size)
{
count = 0;
j = i + 1;
// Inner loop (i+1...size)
while (j < size)
{
if (arr[i] > arr[j])
{
// When get new larger element
count += 1;
}
j += 1;
}
print(" [" + arr[i] + "] : " + count + " \n");
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Element = Element();
var arr: Array < Int > = arrayOf(7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8);
var size: Int = arr.count();
task.countElement(arr, size);
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0In above solution are need O(n*n) time. We can optimize this problem using tree. See this example.
// C Program
// Count smaller elements on right side
#include <stdio.h>
#include <stdlib.h>
// Define tree node
struct TreeNode
{
int key;
struct TreeNode *left;
struct TreeNode *right;
int frequency;
int count;
};
// Define tree structure
struct BstTree
{
struct TreeNode *root;
};
// Returns a new tree
struct BstTree *createTree()
{
struct BstTree *tree = (struct BstTree *) malloc(sizeof(struct BstTree));
if (tree == NULL)
{
printf("\n Memory Overflow when create new tree");
}
else
{
tree->root = NULL;
}
return tree;
}
// Returns a new node of tree
struct TreeNode *createNode(int data)
{
// Create new node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node == NULL)
{
printf("\n Memory Overflow when create new tree");
}
else
{
// When node is created then add initial values
node->key = data;
node->left = NULL;
node->right = NULL;
node->frequency = 1;
node->count = 0;
}
return node;
}
// Add new node of binary search tree and
// Returns the number of smaller node in right side
int addNode(struct BstTree *tree, int data)
{
int tracker = 0;
if (tree->root == NULL)
{
// When tree empty add first node
tree->root = createNode(data);
return tracker;
}
else
{
// Get root node of tree
struct TreeNode *node = tree->root;
// Add new node in binary search tree
while (node != NULL)
{
if (data < node->key)
{
// increase left child node count
node->count++;
if (node->left == NULL)
{
node->left = createNode(data);
return tracker;
}
else
{
// Visit to left child
node = node->left;
}
}
else if (data > node->key)
{
tracker = tracker + (node->count + node->frequency);
if (node->right == NULL)
{
node->right = createNode(data);
return tracker;
}
else
{
// Visit to right child
node = node->right;
}
}
else
{
// When node key already exists
// increase node frequency
node->frequency += 1;
return tracker + node->count;
}
}
}
}
// Counting the number of smaller element of right side in each element of array
void countElement(int arr[], int size)
{
// Create a tree
struct BstTree *tree = createTree();
// auxiliary space which is storing calculated result
int auxiliary[size];
int i = 0;
for (i = size - 1; i >= 0; --i)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary[i] = addNode(tree, arr[i]);
}
// Display calculated result
for (i = 0; i < size; ++i)
{
printf(" [%d] : %d \n", arr[i], auxiliary[i]);
}
}
int main(int argc, char
const *argv[])
{
int arr[] = {
7 , 2 , 6 , 9 , 13 , 5 , 11 , 12 , 6 , 3 , 1 , 8
};
int size = sizeof(arr) / sizeof(arr[0]);
countElement(arr, size);
return 0;
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0/*
Java program
Count smaller elements on right side
*/
//Binary Tree node
class TreeNode
{
public int key;
public int count;
public int frequency;
public TreeNode left;
public TreeNode right;
public TreeNode(int key)
{
this.key = key;
this.left = null;
this.right = null;
this.count = 0;
this.frequency = 1;
}
}
class BstTree
{
public TreeNode root;
public BstTree()
{
this.root = null;
}
}
public class Element
{
// Add new node of binary search tree and
// Returns the number of smaller node in right side
public int addNode(BstTree tree, int data)
{
int tracker = 0;
if (tree.root == null)
{
// When tree empty add first node
tree.root = new TreeNode(data);
}
else
{
// Get root node of tree
TreeNode node = tree.root;
// Add new node in binary search tree
while (node != null)
{
if (data < node.key)
{
// increase left child node count
node.count++;
if (node.left == null)
{
node.left = new TreeNode(data);
return tracker;
}
else
{
// Visit to left child
node = node.left;
}
}
else if (data > node.key)
{
tracker = tracker + (node.count + node.frequency);
if (node.right == null)
{
node.right = new TreeNode(data);
return tracker;
}
else
{
// Visit to right child
node = node.right;
}
}
else
{
// When node key already exists
// increase node frequency
node.frequency += 1;
return tracker + node.count;
}
}
}
return tracker;
}
// Counting the number of smaller element of right side in each element of array
public void countElement(int[] arr, int size)
{
// Create a tree
BstTree tree = new BstTree();
// auxiliary space which is storing calculated result
int[] auxiliary = new int[size];
int i = 0;
for (i = size - 1; i >= 0; --i)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary[i] = addNode(tree, arr[i]);
}
// Display calculated result
for (i = 0; i < size; ++i)
{
System.out.print(" [" + arr[i] + "] : " + auxiliary[i] + " \n");
}
}
public static void main(String[] args)
{
Element task = new Element();
int[] arr =
{
7 , 2 , 6 , 9 , 13 , 5 , 11 , 12 , 6 , 3 , 1 , 8
};
int size = arr.length;
task.countElement(arr,size);
}
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Count smaller elements on right side
*/
//Binary Tree node
class TreeNode
{
public:
int key;
int count;
int frequency;
TreeNode *left;
TreeNode *right;
TreeNode(int key)
{
this->key = key;
this->left = NULL;
this->right = NULL;
this->count = 0;
this->frequency = 1;
}
};
class BstTree
{
public:
TreeNode *root;
BstTree()
{
this->root = NULL;
}
};
class Element
{
public:
// Add new node of binary search tree and
// Returns the number of smaller node in right side
int addNode(BstTree *tree, int data)
{
int tracker = 0;
if (tree->root == NULL)
{
// When tree empty add first node
tree->root = new TreeNode(data);
}
else
{
// Get root node of tree
TreeNode *node = tree->root;
// Add new node in binary search tree
while (node != NULL)
{
if (data < node->key)
{
// increase left child node count
node->count++;
if (node->left == NULL)
{
node->left = new TreeNode(data);
return tracker;
}
else
{
// Visit to left child
node = node->left;
}
}
else if (data > node->key)
{
tracker = tracker + (node->count + node->frequency);
if (node->right == NULL)
{
node->right = new TreeNode(data);
return tracker;
}
else
{
// Visit to right child
node = node->right;
}
}
else
{
// When node key already exists
// increase node frequency
node->frequency += 1;
return tracker + node->count;
}
}
}
return tracker;
}
// Counting the number of smaller element of right side in each element of array
void countElement(int arr[], int size)
{
// Create a tree
BstTree *tree = new BstTree();
// auxiliary space which is storing calculated result
int auxiliary[size];
int i = 0;
for (i = size - 1; i >= 0; --i)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary[i] = this->addNode(tree, arr[i]);
}
// Display calculated result
for (i = 0; i < size; ++i)
{
cout << " [" << arr[i] << "] : " << auxiliary[i] << " \n";
}
}
};
int main()
{
Element task = Element();
int arr[] = {
7 , 2 , 6 , 9 , 13 , 5 , 11 , 12 , 6 , 3 , 1 , 8
};
int size = sizeof(arr) / sizeof(arr[0]);
task.countElement(arr, size);
return 0;
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0// Include namespace system
using System;
/*
C# program
Count smaller elements on right side
*/
//Binary Tree node
public class TreeNode
{
public int key;
public int count;
public int frequency;
public TreeNode left;
public TreeNode right;
public TreeNode(int key)
{
this.key = key;
this.left = null;
this.right = null;
this.count = 0;
this.frequency = 1;
}
}
public class BstTree
{
public TreeNode root;
public BstTree()
{
this.root = null;
}
}
public class Element
{
// Add new node of binary search tree and
// Returns the number of smaller node in right side
public int addNode(BstTree tree, int data)
{
int tracker = 0;
if (tree.root == null)
{
// When tree empty add first node
tree.root = new TreeNode(data);
}
else
{
// Get root node of tree
TreeNode node = tree.root;
// Add new node in binary search tree
while (node != null)
{
if (data < node.key)
{
// increase left child node count
node.count++;
if (node.left == null)
{
node.left = new TreeNode(data);
return tracker;
}
else
{
// Visit to left child
node = node.left;
}
}
else if (data > node.key)
{
tracker = tracker + (node.count + node.frequency);
if (node.right == null)
{
node.right = new TreeNode(data);
return tracker;
}
else
{
// Visit to right child
node = node.right;
}
}
else
{
// When node key already exists
// increase node frequency
node.frequency += 1;
return tracker + node.count;
}
}
}
return tracker;
}
// Counting the number of smaller element of right side in each element of array
public void countElement(int[] arr, int size)
{
// Create a tree
BstTree tree = new BstTree();
// auxiliary space which is storing calculated result
int[] auxiliary = new int[size];
int i = 0;
for (i = size - 1; i >= 0; --i)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary[i] = addNode(tree, arr[i]);
}
// Display calculated result
for (i = 0; i < size; ++i)
{
Console.Write(" [" + arr[i] + "] : " + auxiliary[i] + " \n");
}
}
public static void Main(String[] args)
{
Element task = new Element();
int[] arr = {
7 , 2 , 6 , 9 , 13 , 5 , 11 , 12 , 6 , 3 , 1 , 8
};
int size = arr.Length;
task.countElement(arr, size);
}
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0<?php
/*
Php program
Count smaller elements on right side
*/
//Binary Tree node
class TreeNode
{
public $key;
public $count;
public $frequency;
public $left;
public $right;
function __construct($key)
{
$this->key = $key;
$this->left = null;
$this->right = null;
$this->count = 0;
$this->frequency = 1;
}
}
class BstTree
{
public $root;
function __construct()
{
$this->root = null;
}
}
class Element
{
// Add new node of binary search tree and
// Returns the number of smaller node in right side
public function addNode($tree, $data)
{
$tracker = 0;
if ($tree->root == null)
{
// When tree empty add first node
$tree->root = new TreeNode($data);
}
else
{
// Get root node of tree
$node = $tree->root;
// Add new node in binary search tree
while ($node != null)
{
if ($data < $node->key)
{
// increase left child node count
$node->count++;
if ($node->left == null)
{
$node->left = new TreeNode($data);
return $tracker;
}
else
{
// Visit to left child
$node = $node->left;
}
}
else if ($data > $node->key)
{
$tracker = $tracker + ($node->count + $node->frequency);
if ($node->right == null)
{
$node->right = new TreeNode($data);
return $tracker;
}
else
{
// Visit to right child
$node = $node->right;
}
}
else
{
// When node key already exists
// increase node frequency
$node->frequency += 1;
return $tracker + $node->count;
}
}
}
return $tracker;
}
// Counting the number of smaller element of right side in each element of array
public function countElement( & $arr, $size)
{
// Create a tree
$tree = new BstTree();
// auxiliary space which is storing calculated result
$auxiliary = array_fill(0, $size, 0);
$i = 0;
for ($i = $size - 1; $i >= 0; --$i)
{
// Add a tree node and
// Get number of smaller node of right side
$auxiliary[$i] = $this->addNode($tree, $arr[$i]);
}
// Display calculated result
for ($i = 0; $i < $size; ++$i)
{
echo " [". $arr[$i] ."] : ". $auxiliary[$i] ." \n";
}
}
}
function main()
{
$task = new Element();
$arr = array(7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8);
$size = count($arr);
$task->countElement($arr, $size);
}
main();Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0/*
Node Js program
Count smaller elements on right side
*/
//Binary Tree node
class TreeNode
{
constructor(key)
{
this.key = key;
this.left = null;
this.right = null;
this.count = 0;
this.frequency = 1;
}
}
class BstTree
{
constructor()
{
this.root = null;
}
}
class Element
{
// Add new node of binary search tree and
// Returns the number of smaller node in right side
addNode(tree, data)
{
var tracker = 0;
if (tree.root == null)
{
// When tree empty add first node
tree.root = new TreeNode(data);
}
else
{
// Get root node of tree
var node = tree.root;
// Add new node in binary search tree
while (node != null)
{
if (data < node.key)
{
// increase left child node count
node.count++;
if (node.left == null)
{
node.left = new TreeNode(data);
return tracker;
}
else
{
// Visit to left child
node = node.left;
}
}
else if (data > node.key)
{
tracker = tracker + (node.count + node.frequency);
if (node.right == null)
{
node.right = new TreeNode(data);
return tracker;
}
else
{
// Visit to right child
node = node.right;
}
}
else
{
// When node key already exists
// increase node frequency
node.frequency += 1;
return tracker + node.count;
}
}
}
return tracker;
}
// Counting the number of smaller element of right side in each element of array
countElement(arr, size)
{
// Create a tree
var tree = new BstTree();
// auxiliary space which is storing calculated result
var auxiliary = Array(size).fill(0);
var i = 0;
for (i = size - 1; i >= 0; --i)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary[i] = this.addNode(tree, arr[i]);
}
// Display calculated result
for (i = 0; i < size; ++i)
{
process.stdout.write(" [" + arr[i] + "] : " + auxiliary[i] + " \n");
}
}
}
function main()
{
var task = new Element();
var arr = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8];
var size = arr.length;
task.countElement(arr, size);
}
main();Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0# Python 3 program
# Count smaller elements on right side
# Binary Tree node
class TreeNode :
def __init__(self, key) :
self.key = key
self.left = None
self.right = None
self.count = 0
self.frequency = 1
class BstTree :
def __init__(self) :
self.root = None
class Element :
# Add new node of binary search tree and
# Returns the number of smaller node in right side
def addNode(self, tree, data) :
tracker = 0
if (tree.root == None) :
# When tree empty add first node
tree.root = TreeNode(data)
else :
# Get root node of tree
node = tree.root
# Add new node in binary search tree
while (node != None) :
if (data < node.key) :
# increase left child node count
node.count += 1
if (node.left == None) :
node.left = TreeNode(data)
return tracker
else :
# Visit to left child
node = node.left
elif(data > node.key) :
tracker = tracker + (node.count + node.frequency)
if (node.right == None) :
node.right = TreeNode(data)
return tracker
else :
# Visit to right child
node = node.right
else :
# When node key already exists
# increase node frequency
node.frequency += 1
return tracker + node.count
return tracker
# Counting the number of smaller element of right side in each element of array
def countElement(self, arr, size) :
# Create a tree
tree = BstTree()
# auxiliary space which is storing calculated result
auxiliary = [0] * (size)
i = 0
i = size - 1
while (i >= 0) :
# Add a tree node and
# Get number of smaller node of right side
auxiliary[i] = self.addNode(tree, arr[i])
i -= 1
# Display calculated result
i = 0
while (i < size) :
print(" [", arr[i] ,"] : ", auxiliary[i] ," ")
i += 1
def main() :
task = Element()
arr = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8]
size = len(arr)
task.countElement(arr, size)
if __name__ == "__main__": main()Output
[ 7 ] : 6
[ 2 ] : 1
[ 6 ] : 3
[ 9 ] : 5
[ 13 ] : 7
[ 5 ] : 2
[ 11 ] : 4
[ 12 ] : 4
[ 6 ] : 2
[ 3 ] : 1
[ 1 ] : 0
[ 8 ] : 0# Ruby program
# Count smaller elements on right side
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :key, :count, :frequency, :left, :right
attr_accessor :key, :count, :frequency, :left, :right
def initialize(key)
self.key = key
self.left = nil
self.right = nil
self.count = 0
self.frequency = 1
end
end
class BstTree
# Define the accessor and reader of class BstTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
end
class Element
# Add new node of binary search tree and
# Returns the number of smaller node in right side
def addNode(tree, data)
tracker = 0
if (tree.root == nil)
# When tree empty add first node
tree.root = TreeNode.new(data)
else
# Get root node of tree
node = tree.root
# Add new node in binary search tree
while (node != nil)
if (data < node.key)
# increase left child node count
node.count += 1
if (node.left == nil)
node.left = TreeNode.new(data)
return tracker
else
# Visit to left child
node = node.left
end
elsif(data > node.key)
tracker = tracker + (node.count + node.frequency)
if (node.right == nil)
node.right = TreeNode.new(data)
return tracker
else
# Visit to right child
node = node.right
end
else
# When node key already exists
# increase node frequency
node.frequency += 1
return tracker + node.count
end
end
end
return tracker
end
# Counting the number of smaller element of right side in each element of array
def countElement(arr, size)
# Create a tree
tree = BstTree.new()
# auxiliary space which is storing calculated result
auxiliary = Array.new(size) {0}
i = 0
i = size - 1
while (i >= 0)
# Add a tree node and
# Get number of smaller node of right side
auxiliary[i] = self.addNode(tree, arr[i])
i -= 1
end
# Display calculated result
i = 0
while (i < size)
print(" [", arr[i] ,"] : ", auxiliary[i] ," \n")
i += 1
end
end
end
def main()
task = Element.new()
arr = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8]
size = arr.length
task.countElement(arr, size)
end
main()Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0
/*
Scala program
Count smaller elements on right side
*/
//Binary Tree node
class TreeNode(var key: Int , var count: Int , var frequency: Int , var left: TreeNode , var right: TreeNode)
{
def this(key: Int)
{
this(key, 0, 1, null, null);
}
}
class BstTree(var root: TreeNode)
{
def this()
{
this(null);
}
}
class Element
{
// Add new node of binary search tree and
// Returns the number of smaller node in right side
def addNode(tree: BstTree, data: Int): Int = {
var tracker: Int = 0;
if (tree.root == null)
{
// When tree empty add first node
tree.root = new TreeNode(data);
}
else
{
// Get root node of tree
var node: TreeNode = tree.root;
// Add new node in binary search tree
while (node != null)
{
if (data < node.key)
{
// increase left child node count
node.count += 1;
if (node.left == null)
{
node.left = new TreeNode(data);
return tracker;
}
else
{
// Visit to left child
node = node.left;
}
}
else if (data > node.key)
{
tracker = tracker + (node.count + node.frequency);
if (node.right == null)
{
node.right = new TreeNode(data);
return tracker;
}
else
{
// Visit to right child
node = node.right;
}
}
else
{
// When node key already exists
// increase node frequency
node.frequency += 1;
return tracker + node.count;
}
}
}
return tracker;
}
// Counting the number of smaller element of right side in each element of array
def countElement(arr: Array[Int], size: Int): Unit = {
// Create a tree
var tree: BstTree = new BstTree();
// auxiliary space which is storing calculated result
var auxiliary: Array[Int] = Array.fill[Int](size)(0);
var i: Int = 0;
i = size - 1;
while (i >= 0)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary(i) = this.addNode(tree, arr(i));
i -= 1;
}
i = 0;
// Display calculated result
while (i < size)
{
print(" [" + arr(i) + "] : " + auxiliary(i) + " \n");
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Element = new Element();
var arr: Array[Int] = Array(7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8);
var size: Int = arr.length;
task.countElement(arr, size);
}
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0/*
Swift 4 program
Count smaller elements on right side
*/
//Binary Tree node
class TreeNode
{
var key: Int;
var count: Int;
var frequency: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ key: Int)
{
self.key = key;
self.left = nil;
self.right = nil;
self.count = 0;
self.frequency = 1;
}
}
class BstTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
}
class Element
{
// Add new node of binary search tree and
// Returns the number of smaller node in right side
func addNode(_ tree: BstTree? , _ data : Int)->Int
{
var tracker: Int = 0;
if (tree!.root == nil)
{
// When tree empty add first node
tree!.root = TreeNode(data);
}
else
{
// Get root node of tree
var node: TreeNode? = tree!.root;
// Add new node in binary search tree
while (node != nil)
{
if (data < node!.key)
{
// increase left child node count
node!.count += 1;
if (node!.left == nil)
{
node!.left = TreeNode(data);
return tracker;
}
else
{
// Visit to left child
node = node!.left;
}
}
else if (data > node!.key)
{
tracker = tracker + (node!.count + node!.frequency);
if (node!.right == nil)
{
node!.right = TreeNode(data);
return tracker;
}
else
{
// Visit to right child
node = node!.right;
}
}
else
{
// When node key already exists
// increase node frequency
node!.frequency += 1;
return tracker + node!.count;
}
}
}
return tracker;
}
// Counting the number of smaller element of right side in each element of array
func countElement(_ arr: [Int], _ size: Int)
{
// Create a tree
let tree: BstTree? = BstTree();
// auxiliary space which is storing calculated result
var auxiliary: [Int] = Array(repeating: 0, count: size);
var i: Int = 0;
i = size - 1;
while (i >= 0)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary[i] = self.addNode(tree, arr[i]);
i -= 1;
}
i = 0;
// Display calculated result
while (i < size)
{
print(" [", arr[i],"] : ", auxiliary[i]," ");
i += 1;
}
}
}
func main()
{
let task: Element = Element();
let arr: [Int] = [7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8];
let size: Int = arr.count;
task.countElement(arr, size);
}
main();Output
[ 7 ] : 6
[ 2 ] : 1
[ 6 ] : 3
[ 9 ] : 5
[ 13 ] : 7
[ 5 ] : 2
[ 11 ] : 4
[ 12 ] : 4
[ 6 ] : 2
[ 3 ] : 1
[ 1 ] : 0
[ 8 ] : 0/*
Kotlin program
Count smaller elements on right side
*/
//Binary Tree node
class TreeNode
{
var key: Int;
var count: Int;
var frequency: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(key: Int)
{
this.key = key;
this.left = null;
this.right = null;
this.count = 0;
this.frequency = 1;
}
}
class BstTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
}
class Element
{
// Add new node of binary search tree and
// Returns the number of smaller node in right side
fun addNode(tree: BstTree ? , data : Int): Int
{
var tracker: Int = 0;
if (tree?.root == null)
{
// When tree empty add first node
tree?.root = TreeNode(data);
}
else
{
// Get root node of tree
var node: TreeNode ? = tree.root;
// Add new node in binary search tree
while (node != null)
{
if (data < node.key)
{
// increase left child node count
node.count += 1;
if (node.left == null)
{
node.left = TreeNode(data);
return tracker;
}
else
{
// Visit to left child
node = node.left;
}
}
else if (data >node.key)
{
tracker = tracker + (node.count + node.frequency);
if (node.right == null)
{
node.right = TreeNode(data);
return tracker;
}
else
{
// Visit to right child
node = node.right;
}
}
else
{
// When node key already exists
// increase node frequency
node.frequency += 1;
return tracker + node.count;
}
}
}
return tracker;
}
// Counting the number of smaller element of right side in each element of array
fun countElement(arr: Array<Int>, size: Int): Unit
{
// Create a tree
var tree: BstTree ? = BstTree();
// auxiliary space which is storing calculated result
var auxiliary: Array<Int> = Array(size)
{
0
};
var i: Int = size - 1;
while (i >= 0)
{
// Add a tree node and
// Get number of smaller node of right side
auxiliary[i] = this.addNode(tree, arr[i]);
i -= 1;
}
i = 0;
// Display calculated result
while (i<size)
{
print(" [" + arr[i] + "] : " + auxiliary[i] + " \n");
i += 1;
}
}
}
fun main(args: Array<String>): Unit
{
var task: Element = Element();
var arr: Array<Int> = arrayOf(7, 2, 6, 9, 13, 5, 11, 12, 6, 3, 1, 8);
var size: Int = arr.count();
task.countElement(arr, size);
}Output
[7] : 6
[2] : 1
[6] : 3
[9] : 5
[13] : 7
[5] : 2
[11] : 4
[12] : 4
[6] : 2
[3] : 1
[1] : 0
[8] : 0
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment