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] : 0

In 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







© 2021, kalkicode.com, All rights reserved