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