Smaller Sum

 

PROBLEM 59: Smaller Sum

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 22/04/2023

You are given an array arr of n integers. For each index i, you have to find the sum of all integers present in the array with a value less than arr[i].

Example 1:

Input:
n = 3
arr = {1, 2, 3}
Output:
0 1 3
Explanation:
For 1, there are no elements lesser than itself.
For 2, only 1 is lesser than 2.
And for 3, 1 and 2 are lesser than 3, so the sum is 3.

Example 2:

Input:
n = 2
arr = {4, 4}
Output:
0 0
Explanation:
For 4, there are no elements lesser than itself. 
For 4, there are no elements lesser than itself.
There are no smaller elements than 4.

SOLUTION:

from typing import List
class Solution:
    def smallerSum(self, n : int, arr : List[int]) -> List[int]:
        # code here
        ar = set(arr)
        arr1 = list(ar)
        arr1.reverse()
        l = []
        def sum1(i):
            j = arr1.index(i)
            s1 = sum(arr1[j+1:])
            l.append(s1)
        
            
        for i in arr:
            sum1(i)
        return l


class IntArray:
    def __init__(self) -> None:
        pass
    def Input(self,n):
        arr=[int(i) for i in input().strip().split()]#array input
        return arr
    def Print(self,arr):
        for i in arr:
            print(i,end=" ")
        print()

if __name__=="__main__":
    t = int(input())
    for _ in range(t):

        n = int(input())
        arr=IntArray().Input(n)
        obj = Solution()
        res = obj.smallerSum(n, arr)
        
        IntArray().Print(res)

        

Expected Time Complexity:O(n log n)
Expected Space Complexity:O(n)

Constraints:
1 <= n <= 105
0 <= arr[i] <= 109