CareerCup

The code in this link makes use of BST to do it efficiently using a nice trick.

onestopinterviewprep.blogspot.com/2014/03/sum-of-previous-smaller-numbers-in-array.html

Can we improve the efficiency.further ?

F***ER is trying to advertize his blog.

codechamp, are you sure Zynga asked someone this exact question?

i have written a simple program can any one help to optimize this and is there any other data structure we should use to solve this problem

#include<iostream>
using namespace std;
int main() {

// int arr[100];
int length = 5;
int sum[100];
int arr[]= {2,5,1,9,3};

for (int k = 0; k < length ; k++) {
sum[arr[k]] = 0;
}

for (int i = 0; i < length ; i++) {

for (int j = 0; j < length ; j++) {

if (arr[i] > arr[j]) {
sum[arr[i]] = sum[arr[i]] + arr[j];
}
}

}

//print the output
for(int l=0;l<length;l++){
cout<<"sum of number less then :"<<arr[l]<<"is "<<sum[arr[l]]<<endl;

}
return 0;
}

public class SumOfPrevMins 
{
	public static void main(String[] args) 
	{
		int[] a = new int[]{2, 5, 1, 9, 3, 10}; //1,2,3,5,9,10
		long[] b = findSumOfPrevMins(a);
		for(long sum : b)
			System.out.println(sum);
	}
	
	public static long[] findSumOfPrevMins(int a[])
	{
		if(a.length == 0)
			return null;
		int i = 0;
		long buildNum = 0;
		long b[] = new long[a.length];	
		while(i < a.length)
		{
			long tmpNum = buildNum;
			buildNum = (buildNum*10) + a[i];
			long sum = 0;						
			while(tmpNum > 0)
			{
				if(tmpNum % 10 < a[i])
					sum = sum + (tmpNum%10);
				tmpNum /= 10;
			}
			b[i] = sum;
			i++;
		}
		
		return b;
	}		
}

public class SumOfPrevMins
{
public static void main(String[] args)
{
int[] a = new int[]{2, 5, 1, 9, 3, 10}; //1,2,3,5,9,10
long[] b = findSumOfPrevMins(a);
for(long sum : b)
System.out.println(sum);
}

public static long[] findSumOfPrevMins(int a[])
{
if(a.length == 0)
return null;
int i = 0;
long buildNum = 0;
long b[] = new long[a.length];
while(i < a.length)
{
long tmpNum = buildNum;
buildNum = (buildNum*10) + a[i];
long sum = 0;
while(tmpNum > 0)
{
if(tmpNum % 10 < a[i])
sum = sum + (tmpNum%10);
tmpNum /= 10;
}
b[i] = sum;
i++;
}

return b;
}
}

package FindingSumOfSmallerElementsOnLeft;

public class FindingSumOfSmallerElementsOnLeft {

    public static void main(String[] args) {
     int[] Arr = { 2, 3, 8, 6, 1 ,10};

            //Sum of prev small numbers in arr
            BST ob = new BST();
            for (int i = 0; i < Arr.length; i++)
            {
                System.out.println(ob.AddNodeAndReturnSumOfPrevSmallNumInArr(Arr[i]));
            }
            
            ob.inOrder();
    
}
}


class BST
    {
        class TreeNode
        {
            public int data;
            public TreeNode left;
            public TreeNode right;
            public int Sum; //for SumOfPrevSmallNumInArr

            public TreeNode(int val)
            {
                this.data = val;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }

            public TreeNode(int val, int index)
            {
                this.data = val;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }

            public TreeNode()
            {
                this.data = 0;
                this.left = null;
                this.right = null;
                this.Sum = 0;
            }
        }

        TreeNode Root;
        public BST()
        {
            Root = null;
        }

        public int AddNodeAndReturnSumOfPrevSmallNumInArr(int val)
        {
            TreeNode Node = new TreeNode(val);
            if (Root == null)
            {
                Root = Node;
                return 0;
            }

            TreeNode cur = Root;
            TreeNode Prev = null;
            int Sum = 0;

            while (cur != null)
            {
                Prev = cur;
                //If moving towards right add the current node's value and its 
                //sum value to the sum being calculated to return.
                if (val >= cur.data)
                {
                    Sum += cur.data + cur.Sum;
                    cur = cur.right;
                }
                //If moving towards left add the value to current node's sum.
                else
                {
                    cur.Sum += val;
                    cur = cur.left;
                }
            }
            if (val >= Prev.data)
                Prev.right = Node;
            else 
                Prev.left = Node;
            
            return Sum;
        }
        
         public void inOrder(){
             inOrder(Root);
         }
        
        public void inOrder(TreeNode t){
            if(t==null) return;
            
            inOrder(t.left);
            System.out.print(t.data + " ");
            inOrder(t.right);
        }
}

In python
=============

import json
x_inp=input("Enter the array:")
x=json.loads(x_inp)
y=int(input("Enter the index value:"))
def mini(x,y):
    val=x[y]
    summed=0
    for i in range(0,(y+1)):
        if x[i]<val:
            summed+=x[i]
    return summed
mini(x,y)

Using Priority Queue will work.

Maintain a min heap priority queue (i.e. smallest element is on the top)

For each element in Array 
{
   For current number N, 
   Pop elements from Heap till root is smaller than N and maintain sum
   Push all poped elements back and push current
}