Rearrange an array with O(1) extra space

 

PROBLEM 61: Rearrange an array with O(1) extra space

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 16/05/2023

Given an array arr[] of size N where every element is in the range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]].

 

Example 1:

Input:
N = 2
arr[] = {1,0}
Output: 0 1
Explanation: 
arr[arr[0]] = arr[1] = 0.
arr[arr[1]] = arr[0] = 1.

 

Example 2:

Input:
N = 5
arr[] = {4,0,2,1,3}
Output: 3 4 2 0 1
Explanation: 
arr[arr[0]] = arr[4] = 3.
arr[arr[1]] = arr[0] = 4.
and so on. 

Solution:

class Solution:
  def arrange(self,arr, n): 
        #Your code here
        l = []
        for i in range(0,n):
            j = arr[i]
            l.append(arr[j])
        return l

import math
def main():

        T=int(input())
        while(T>0):
            
            n=int(input())
            
            arr=[int(x) for x in input().strip().split()]
            
            ob=Solution()
            ob.arrange(arr,n)
            
            for i in arr:
                print(i,end=" ")

 

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

 

Constraints:
1 <= N <= 107

0 <= Arr[i] < N

Print Pattern

 

PROBLEM 60: Print Pattern

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 14/05/2023

Print a sequence of numbers starting with N where A[0] = N, in which  A[i+1] = A[i] - 5,  until A[i] > 0. After that A[i+1] = A[i] + 5  repeat it until A[i] = N.

Example 1:

Input: N = 16
Output: 16 11 6 1 -4 1 6 11 16
Explaination: The value decreases until it 
is greater than 0. After that it increases 
and stops when it becomes 16 again.

Example 2:

Input: N = 10
Output: 10 5 0 5 10
Explaination: It follows the same logic as 
per the above example.

Solution:

class Solution:
    def pattern(self, N):
        # code here
        l = []
        k = 0
        N1 = N
        while True:
            if k == 0:
                l.append(N)
                N = N - 5
                if N <= 0:
                    k = 1
            else:
                l.append(N)
                N = N + 5
                if N1 == N:
                    l.append(N1)
                    return l
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        N = int(input())
        
        ob = Solution()
        ans = ob.pattern(N)
        for i in ans:
            print(i, end = " ")
        print()

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

Constraints:
1 ≤ N ≤ 104 

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