Scribd
Upload
6 views4 pages

Final Question Set On Array and STR

The document presents two programming tasks: rotating an unsorted array to the left by D steps and calculating the product of two numbers represented as strings. The first task requires an in-place rotation with O(N) time complexity, while the second task involves string manipulation to compute the product without using built-in functions, with an expected time complexity of O(n1 * n2). Both tasks include example inputs and outputs, along with constraints and expected complexities.

Uploaded by

22- XI-B- Ratikanta Rout
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
6 views4 pages

Final Question Set On Array and STR

The document presents two programming tasks: rotating an unsorted array to the left by D steps and calculating the product of two numbers represented as strings. The first task requires an in-place rotation with O(N) time complexity, while the second task involves string manipulation to compute the product without using built-in functions, with an expected time complexity of O(n1 * n2). Both tasks include example inputs and outputs, along with constraints and expected complexities.

Uploaded by

22- XI-B- Ratikanta Rout
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

FINAL QUESTION SET ON ARRAY AND STRINGS.

1.Given an unsorted array arr[] of size N. Rotate the array to the left (counter-
clockwise direction) by D steps, where D is a positive integer.

Example 1:

Input:
N = 5, D = 2
arr[] = {1,2,3,4,5}
Output: 3 4 5 1 2
Explanation: 1 2 3 4 5 when rotated
by 2 elements, it becomes 3 4 5 1 2.
Example 2:

Input:
N = 10, D = 3
arr[] = {2,4,6,8,10,12,14,16,18,20}
Output: 8 10 12 14 16 18 20 2 4 6
Explanation: 2 4 6 8 10 12 14 16 18 20
when rotated by 3 elements, it becomes
8 10 12 14 16 18 20 2 4 6.

Your Task:
You need not print or read anything. You need to complete the function rotateArr()
which takes the array, D and N as input parameters and rotates the array by D
elements. The array must be modified in-place without using extra space.

Expected Time Complexity: O(N)


Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 106
1 <= D <= 106
0 <= arr[i] <= 105

2. Given two numbers as strings s1 and s2. Calculate their Product.

Note: The numbers can be negative and You are not allowed to use any built-in
function or convert the strings to integers. There can be zeros in the begining of
the numbers. You don't need to specify '+' sign in the begining of positive
numbers.

Example 1:

Input:
s1 = "0033"
s2 = "2"
Output:
66
Example 2:
Input:
s1 = "11"
s2 = "23"
Output:
253
Your Task: You don't need to read input or print anything. Your task is to complete
the function multiplyStrings() which takes two strings s1 and s2 as input and
returns their product as a string.

Expected Time Complexity: O(n1* n2)


Expected Auxiliary Space: O(n1 + n2); where n1 and n2 are sizes of strings s1 and
s2 respectively.

Constraints:
1 ≤ length of s1 and s2 ≤ 103

SOLUTION PAGE:

1. public class Solution{

public void reverseArray(int arr[],int start , int end){

while(start<end){

int temp = arr[start];


arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

public void rotateArray(int arr[],int d,int n){

d = d%n;

reverseArray(arr, 0, d-1);

reverseArray(arr, d , n-1);

reverseArray(arr, 0 , n-1);

2. class Solution {
public String multiplyStrings(String s1, String s2) {
int n1 = s1.length();
int n2 = s2.length();
int a = s1.charAt(0) == '-' ? -1 : 0;
int b = s2.charAt(0) == '-' ? -1 : 0;

int[] arr = new int[n1 + n2];

for (int i = n1 - 1; i >= 0; i--) {


int k = i + n2;

if (s1.charAt(i) != '-') {
int carry = 0;

for (int j = n2 - 1; j >= 0; j--) {


if (s2.charAt(j) != '-') {
int x = (s1.charAt(i) - '0') * (s2.charAt(j) - '0') + carry
+ arr[k];
arr[k] = x % 10;
carry = x / 10;
k--;
}
}
while (carry > 0) {
arr[k] = carry % 10;
carry /= 10;
k--;
}
}
}

int i = 0;
while (i < n1 + n2 && arr[i] == 0) {
i++;
}

StringBuilder sb = new StringBuilder();


if (i == n1 + n2) {
return "0";
}

if ((a < 0 && b >= 0) || (b < 0 && a >= 0)) {


sb.append('-');
}

for (; i < n1 + n2; i++) {


sb.append(arr[i]);
}

return sb.toString();
}
}

You might also like