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

Prefix Suffix String

 

PROBLEM 58: Prefix Suffix String

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 21/04/2023

Given two Lists of strings s1 and s2, you have to count the number of strings in s2 which is either a suffix or prefix of at least one string of s1.

Example 1:

Input:
s1 = ["cat", "catanddog", "lion"]
s2 = ["cat", "dog", "rat"]
Output: 
2
Explanation: 
String "cat" of s2 is prefix of "catanddog"
& string "dog" of s2 is suffix of "catanddog" 

Example 2:

Input: 
s1 = ["jrjiml", "tchetn", "ucrhye", "ynayhy", 
       "cuhffd", "cvgpoiu", "znyadv"]
s2 = ["jr", "ml", "cvgpoi", "gpoiu", "wnmkmluc", 
      "geheqe", "uglxagyl", "uyxdroj"] 
Output: 
4
Explanation: 
String "jr" of s2 is prefix of "jrjiml", 
"ml" of s2 is suffix of "jrjiml", 
"cvgpoi" of s2 is prefix of "cvgpoiu" &
"gpoiu" of s2 is suffix of "cvgpoiu"

SOLUTION:

class Solution:
    def prefixSuffixString(self, s1, s2) -> int:
        #code here
        cnt = 0
        for i in s1:
            for j in s2:
                if i != j:
                    if j == i[:len(j)]:
                        cnt = cnt + 1
                        
                    h = len(i) - len(i[:len(j)]) 
                    if j == i[h:]:
                        cnt = cnt + 1
        return(cnt)

if __name__=="__main__":
    for _ in range(int(input())):
        s1 = list(map(str, input().split()))
        s2 = list(map(str, input().split()))
        obj=Solution()
        print(obj.prefixSuffixString(s1, s2))

Expected Time Complexity: O(max(len(s1) , len(s2) ))
Expected Space Complexity: O(1)

Constraints:
   1 <= s1,s2 < 5 * 10^3
   5 <= len(s1[i]), len(s2[i]) < 25

Search insert position of K in a sorted array

 

PROBLEM 57: Search insert position of K in a sorted array

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 20/04/2023

Given a sorted array Arr[](0-index based) consisting of N distinct integers and an integer k, the task is to find the index of k, if its present in the array Arr[]. Otherwise, find the index where k must be inserted to keep the array sorted.

Example 1:

Input:
N = 4
Arr = {1, 3, 5, 6}
k = 5
Output: 2
Explaination: Since 5 is found at index 2 
as Arr[2] = 5, the output is 2.

Example 2:

Input:
N = 4
Arr = {1, 3, 5, 6}
k = 2
Output: 1
Explaination: Since 2 is not present in 
the array but can be inserted at index 1 
to make the array sorted.

SOLUTION:

class Solution:
    def searchInsertK(self, Arr, N, k):
        # code here
        if k in Arr:
            a = Arr.index(k)
            return a
        else:
            cnt = 0
            for i in Arr:
                if i < k:
                    cnt = cnt + 1
                else:
                    return cnt
            else:
                return len(Arr)


if __name__ == '__main__':
    t = int(input())
    for _ in range (t):
        N = int(input())
        Arr = input().split()
        for itr in range(N):
            Arr[itr] = int(Arr[itr])
        k = int(input())
        ob = Solution()
        print(ob.searchInsertK(Arr, N, k))

Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 104
-103 ≤ Arr[i] ≤ 103
-103 ≤ k ≤ 103

Maximum number of zeroes

 

PROBLEM 56: Maximum number of zeroes

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 18/04/2023

Given an array arr[] of N values, the task is to find the number which has the maximum number of zeroes. If there are no zeroes then print -1.

Note: If there are multiple numbers with the same (max) number of zeroes then print the Maximum number among them.

Example 1:

Input: N = 5
arr[] = {10, 20, 3000, 9999, 200}
Output:  3000
Explanation: 3000 contains 3 zero's 
in it.

Example 2:

Input: N = 4
arr[] = {1, 2, 3, 4}
Output:  -1
Explanation: No zero is present.

 SOLUTION:

def MaxZero(arr, n):
    # Your code goes here
    cnt = 0
    l = []
    for i in arr:
        ii = str(i)
        iii = ii.count('0')
        if iii >= cnt:
            cnt = iii
            l.append(i)
            
    if cnt == 0:
        return -1
    else:
        ll = []
        for i in l:
            if str(i).count('0') == cnt:
                ll.append(i)
        return(max(ll))
        
if __name__ == '__main__': 
     t=int(input())
    for _ in range(0,t):
        n=int(input())
        a=list(map(int,input().split()))
        print(MaxZero(a,n))

Expected Time Complexity: O(N*M). where N is the size of array and M is the maximum length of a number in the array
Expected Auxiliary Space: O(1).

 

Constraints:
1 ≤ N ≤ 105
1 < A[i] < 10100

Convert a sentence into its equivalent mobile numeric keypad sequence

 

PROBLEM 55: Convert a sentence into its equivalent mobile numeric keypad sequence

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 17/04/2023

Given a sentence in the form of a string in uppercase, convert it into its equivalent mobile numeric keypad sequence. Please note there might be spaces in between the words in a sentence and we can print spaces by pressing 0.

 

SOLUTION:

class Solution:
    def printSequence(self,S):
         s1 = ""
         for i in S:
            if i == 'A':
                s1 = s1 + '2'
            elif i == 'B':
                s1 = s1 + '22'
            elif i == 'C':
                s1 = s1 + '222'
            elif i == 'D':
                s1 = s1 + '3'
            elif i == 'E':
                s1 = s1 + '33'
            elif i == 'F':
                s1 = s1 + '333'
            elif i == 'G':
                s1 = s1 + '4'
            elif i == 'H':
                s1 = s1 + '44' 
            elif i == 'I':
                s1 = s1 + '444' 
            elif i == 'J':
                s1 = s1 + '5' 
            elif i == 'K':
                s1 = s1 + '55'
            elif i == 'L':
                s1 = s1 + '555' 
            elif i == 'M':
                s1 = s1 + '6' 
            elif i == 'N':
                s1 = s1 + '66' 
            elif i == 'O':
                s1 = s1 + '666' 
            elif i == 'P':
                s1 = s1 + '7'
            elif i == 'Q':
                s1 = s1 + '77'
            elif i == 'R':
                s1 = s1 + '777'
            elif i == 'S':
                s1 = s1 + '7777'
            elif i == 'T':
                s1 = s1 + '8'
            elif i == 'U':
                s1 = s1 + '88'
            elif i == 'V':
                s1 = s1 + '888' 
            elif i == 'W':
                s1 = s1 + '9' 
            elif i == 'X':
                s1 = s1 + '99' 
            elif i == 'Y':
                s1 = s1 + '999'
            elif i == 'Z':
                s1 = s1 + '9999' 
            else:
                s1 = s1 + '0'
        print(s1)

Example 1:

Input:
S = "GFG"
Output: 43334
Explanation: For 'G' press '4' one time.
For 'F' press '3' three times.

Example 2:

Input:
S = "HEY U"
Output: 4433999088
Explanation: For 'H' press '4' two times.
For 'E' press '3' two times. For 'Y' press '9' 
three times. For white space press '0' one time.
For 'U' press '8' two times.

 Expected Time Complexity: O(Length of String)

Expected Auxiliary Space: O(Length of String)
 

Constraints:

1 <= Length of String <= 105
Characters of string can be empty space or capital alphabets.

Sum of Middle Elements of two sorted arrays

 

PROBLEM 54: Sum of Middle Elements of two sorted arrays

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 14/04/2023

Given 2 sorted arrays Ar1 and Ar2 of size N each. Merge the given arrays and find the sum of the two middle elements of the merged array.

 

Example 1:

Input:
N = 5
Ar1[] = {1, 2, 4, 6, 10}
Ar2[] = {4, 5, 6, 9, 12}
Output: 11
Explanation: The merged array looks like
{1,2,4,4,5,6,6,9,10,12}. Sum of middle
elements is 11 (5 + 6).

 

Example 2:

Input:
N = 5
Ar1[] = {1, 12, 15, 26, 38}
Ar2[] = {2, 13, 17, 30, 45}
Output: 32
Explanation: The merged array looks like
{1, 2, 12, 13, 15, 17, 26, 30, 38, 45} 
sum of middle elements is 32 (15 + 17).

 SOLUTION:

   class Solution:

    def findMidSum(self, ar1, ar2, n): 
        # code here 
        ar1.extend(ar2)
        ar1.sort()
        sum = ar1[n-1] + ar1[n]
        return sum
        


if __name__ == "__main__":         
    tc=int(input())
    while tc > 0:
        n=int(input())
        ar1=list(map(int, input().strip().split()))
        ar2=list(map(int, input().strip().split()))
        ob = Solution()
        ans = ob.findMidSum(ar1, ar2, n)
        print(ans)
        tc=tc-1

Your Task:

You don't need to read input or print anything. Your task is to complete the function findMidSum() which takes  ar1, ar2 and n as input parameters and returns the sum of middle elements. 

 

Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)

 

Constraints:
1 <= N <= 103
1 <= Ar1[i] <= 106
1 <= Ar2[i] <= 106

Row with max 1s

 

PROBLEM 53: Row with max 1s

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 11/04/2023

Given a boolean 2D array of n x m dimensions where each row is sorted. Find the 0-based index of the first row that has the maximum number of 1's.

Example 1:

Input: 
N = 4 , M = 4
Arr[][] = {{0, 1, 1, 1},
           {0, 0, 1, 1},
           {1, 1, 1, 1},
           {0, 0, 0, 0}}
Output: 2
Explanation: Row 2 contains 4 1's (0-based
indexing).

Example 2:

Input: 
N = 2, M = 2
Arr[][] = {{0, 0}, {1, 1}}
Output: 1
Explanation: Row 1 contains 2 1's (0-based
indexing).

Solution :

class Solution:

    def rowWithMax1s(self,arr, n, m):
        # code here
        cnt = 0
        ii = 0
        m = 0
        for i in arr:
            ii = ii + 1
            if i.count(1) > cnt:
                cnt = i.count(1)
                m = ii
        return m-1

if __name__ == '__main__':
    tc = int(input())
    while tc > 0:
        n, m = list(map(int, input().strip().split()))
        
        inputLine = list(map(int, input().strip().split()))
        arr = [[0 for j in range(m)] for i in range(n)]
        
        for i in range(n):
            for j in range(m):
                arr[i][j] = inputLine[i * m + j]
        ob = Solution()
        ans = ob.rowWithMax1s(arr, n, m)
        print(ans)
        tc -= 1

Expected Time Complexity: O(Nlog(M))

Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N, M ≤ 103
0 ≤ Arr[i][j] ≤ 1 

Trapping Rain Water

 

PROBLEM 52: Trapping Rain Water

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 11/04/2023

Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.

Solution:

class Solution:

    def trappingWater(self, arr,n):

        cnt = 0

        h = arr[len(arr)-1]

        for i in range(len(arr)-2,-1,-1):

            if arr[i] <= h:

                cnt = cnt + (h-arr[i])

            else:

                h = arr[i]

        

        i = 0 

        s = 0

        if arr[0] < h:

            while arr[i] != h:

                if arr[i] >= s:

                    s = arr[i]

                cnt = cnt + (s-arr[i])

                cnt = cnt - (h-arr[i])

                i = i + 1

        return cnt

import math

def main():

        T=int(input())

        while(T>0):

            n=int(input())

            arr=[int(x) for x in input().strip().split()]

            obj = Solution()

            print(obj.trappingWater(arr,n))

            T-=1

if __name__ == "__main__":

    main()

Example 1:

Input:
N = 6
arr[] = {3,0,0,2,0,4}
Output:
10
Explanation: 

Example 2:

Input:
N = 4
arr[] = {7,4,0,9}
Output:
10
Explanation:
Water trapped by above 
block of height 4 is 3 units and above 
block of height 0 is 7 units. So, the 
total unit of water trapped is 10 units.

Example 3:

Input:
N = 3
arr[] = {6,9,9}
Output:
0
Explanation:
No water will be trapped.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
3 < N < 106
0 < Ai < 108