Array II
When working with arrays, there are situations where we may need to perform operations or modifications on an array while preserving the original data. In such cases, it's common to create a copy of the original array. By doing this, any modifications or operations can be performed on the duplicate array, ensuring that the original array remains unchanged. This approach allows us to retain the original array in its unaltered state while working on the duplicate.
4. Write a program that takes an array as input and creates a duplicate of the given array.
Example:
Input: nums = [4, 8, 15, 16, 23, 42]
Output: [4, 8, 15, 16, 23, 42]
Explanation: The duplicate array is identical to the input array, preserving the original array for future use.
Input: nums = [10, 20, 30, 40, 50]
Output: [10, 20, 30, 40, 50]
Approach
To create a duplicate array of nums called d_nums, we first need to declare d_nums with the same size as nums. After the declaration, we will assign values to each element in d_nums such that they match the corresponding elements in nums. This will be done by iterating over the array nums, and for every index i from 0 to n-1 (where n is the size of nums), we will set d_nums[i] = nums[i]. This process ensures that each element in d_nums is an exact copy of the element at the same index in nums.
Dry Run
Input: nums = [10, 20, 30, 40, 50], size = 5
Output: [10, 20, 30, 40, 50]
- A new array d_nums is declared with the same size as nums.
Initially, d_nums = [ , , , , ] (empty array of size 5). - Start copying elements from nums to d_nums:
- Iteration 1 (index = 0): d_nums[0] = nums[0]
d_nums = [10, , , , ] - Iteration 2 (index = 1): d_nums[1] = nums[1]
d_nums = [10, 20, , , ] - Iteration 3 (index = 2): d_nums[2] = nums[2]
d_nums = [10, 20, 30, , ] - Iteration 4 (index = 3): d_nums[3] = nums[3]
d_nums = [10, 20, 30, 40, ] - Iteration 5 (index = 4): d_nums[4] = nums[4]
d_nums = [10, 20, 30, 40, 50]
- Iteration 1 (index = 0): d_nums[0] = nums[0]
Final Output : The duplicate array is printed exactly as the input array: [10, 20, 30, 40, 50]
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to create a duplicate of the array and print it
void createAndPrintDuplicate(int nums[], int size) {
// Declare a new array d_nums with the same size as nums
int d_nums[size];
// Copy each element from nums to d_nums
for (int index = 0; index < size; ++index) {
d_nums[index] = nums[index];
}
// Print the elements of the duplicate array d_nums
for (int index = 0; index < size; ++index) {
cout << d_nums[index] << " ";
}
}
Java
import java.util.Scanner;
public class LearnYard {
// Function to create a duplicate of the array and print it
static void createAndPrintDuplicate(int[] nums, int size) {
// Declare a new array d_nums with the same size as nums
int[] d_nums = new int[size];
// Copy each element from nums to d_nums
for (int index = 0; index < size; index++) {
d_nums[index] = nums[index];
}
// Print the elements of the duplicate array d_nums
for (int index = 0; index < size; index++) {
System.out.print(d_nums[index] + " ");
}
}
}Python
# Function to create a duplicate of the array and print it
def createAndPrintDuplicate(nums, size):
# Declare a new list d_nums with the same size as nums
d_nums = [0] * size
# Copy each element from nums to d_nums
for index in range(size):
d_nums[index] = nums[index]
# Print the elements of the duplicate array d_nums
print(*d_nums)
Javascript
// Function to create a duplicate of the array and print it
function createAndPrintDuplicate(nums, size) {
// Declare a new array d_nums with the same size as nums
let d_nums = new Array(size);
// Copy each element from nums to d_nums
for (let index = 0; index < size; index++) {
d_nums[index] = nums[index];
}
// Print the elements of the duplicate array d_nums
console.log(d_nums.join(" "));
}Time Complexity : O(n)
The time complexity of the approach is determined by the iteration over the array nums. We iterate through each element of nums exactly once to copy it into d_nums. If n is the size of the array nums, the loop runs n times, and each assignment operation (d_nums[i] = nums[i]) takes constant time, O(1). Therefore, the total time complexity is O(n)
Space Complexity : O(n)
- Total Space Complexity: O(n)
- Input Array Space: The input array nums takes up space proportional to its size. If the array has n elements, the space required to store the array is O(n).
- Duplicate Array Space: The duplicate array d_nums also requires space proportional to its size, which is equal to the input array size. Thus, this adds an additional O(n) space.
- Variables: The variables size, index, and nums require constant space, O(1), because they do not grow with the size of the array.
- Overall, the total space complexity is O(n) + O(n) = O(n).
- Auxiliary Space Complexity: O(n)
- Auxiliary Space: This refers to the extra space used by the algorithm, excluding the input data. In this approach, the only auxiliary space used is for the duplicate array d_nums, which is O(n).
- Other temporary variables (like index) require constant space, O(1).
When working with arrays, there are situations where we may need to separate elements based on specific criteria, one of the most common of such criteria is whether they are odd or even. In such cases, it's common to create two separate arrays: one for odd elements and one for even elements. By doing this, we can process or analyze odd and even elements independently, ensuring that the original array remains unchanged. This approach allows us to work with the separated elements while preserving the original array for future use.
5. Write a program that takes an array as input and creates two separate arrays: one containing all the odd elements and the other containing all the even elements.
Example
Input: nums = [4, 8, 15, 16, 23, 42]
Output:
Odd elements: [15, 23]
Even elements: [4, 8, 16, 42]
Explanation: The original array is split into two arrays: one containing the odd elements [15,23] and the other containing the even elements [4, 8, 16, 42].
Input: nums = [10, 21, 30, 43, 52]
Output:
Odd elements: [21, 43]
Even elements: [10, 30, 52]
Approach
The task is to create two separate arrays: one for odd elements and another for even elements. To achieve this, we first need to determine the size of these two arrays, which depends on the count of odd and even elements in the original array, nums.
We start by iterating through nums to count the number of odd and even elements. After counting, we can declare two new arrays: odd_nums and even_nums. The size of odd_nums will be equal to the count of odd elements, and the size of even_nums will be equal to the count of even elements. Now, we need two variables, odd_index and even_index, both initialized to 0.
Why Do We Need These Variables?
These variables act as counters that tell us the current position in the odd_nums and even_nums arrays. Without them, we wouldn't know where to place the next odd or even element as we iterate through the original array.
Why Initialize to 0?
We initialize odd_index and even_index to 0 because arrays in most programming languages, including C++, start indexing from 0. This means the first element in an array is at position 0. By starting these variables at 0, we ensure that the first odd or even element will be placed at the beginning of the respective array.
Now, Iterate through the original array nums again. For each element, Check if the element is odd or even:
- If the element is even (nums[index] % 2 == 0), assign it to the even_nums array at the position indicated by even_index, and then increment the even_index pointer by 1.
- If the element is odd(nums[index] % 2 == 1), assign it to the odd_nums array at the position indicated by odd_index, and then increment the odd_index pointer by 1.
Why Increment by 1 Every Time?
Every time we add an element to either odd_nums or even_nums, we increment the respective variable (odd_index or even_index) by 1. This ensures that the next element is placed in the next available position in the array. If we didn't increment the variables, we would overwrite the previous element in the array, which would lead to incorrect results.
After completing the iteration, the odd_nums array will contain all the odd elements from the original array, and the even_nums array will contain all the even elements. Print them them in separate lines.
Dry Run
Input: nums = [4, 8, 15, 16, 23, 42]
- Initialization:
odd_count = 0
even_count = 0 - First Loop - Counting Odd and Even Elements:
We loop through the nums array and count odd and even numbers:After the loop: - nums[0] = 4 → Even, so increment even_count to 1.
- nums[1] = 8 → Even, so increment even_count to 2.
- nums[2] = 15 → Odd, so increment odd_count to 1.
- nums[3] = 16 → Even, so increment even_count to 3.
- nums[4] = 23 → Odd, so increment odd_count to 2.
- nums[5] = 42 → Even, so increment even_count to 4.
odd_count = 2
even_count = 4
- Create Arrays for Odd and Even Elements:
Create odd_nums[2] and even_nums[4] to store the odd and even elements. - Second Loop - Separating Odd and Even Elements:
We loop through the nums array again to separate the odd and even elements:After the loop: - nums[0] = 4 → Even, so add to even_nums[0], even_index increments to 1.
- nums[1] = 8 → Even, so add to even_nums[1], even_index increments to 2.
- nums[2] = 15 → Odd, so add to odd_nums[0], odd_index increments to 1.
- nums[3] = 16 → Even, so add to even_nums[2], even_index increments to 3.
- nums[4] = 23 → Odd, so add to odd_nums[1], odd_index increments to 2.
- nums[5] = 42 → Even, so add to even_nums[3], even_index increments to 4.
odd_nums = [15, 23]
even_nums = [4, 8, 16, 42]
- Output:
Print Odd elements: [15, 23]
Print Even elements: [4, 8, 16, 42]
Final Output:
Odd elements: [15, 23]
Even elements: [4, 8, 16, 42]
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to separate odd and even elements
void separateOddEven(int nums[], int size) {
int odd_count = 0, even_count = 0;
// Count odd and even elements
for (int index = 0; index < size; ++index) {
if (nums[index] % 2 == 0) {
++even_count;
}
else {
++odd_count;
}
}
int odd_nums[odd_count];
int even_nums[even_count];
int odd_index = 0, even_index = 0;
// Separate elements into odd and even arrays
for (int index = 0; index < size; ++index) {
if (nums[index] % 2 == 0) {
even_nums[even_index++] = nums[index];
}
else {
odd_nums[odd_index++] = nums[index];
}
}
// Print the elements of the odd array
cout << "Odd elements: ";
for (int index = 0; index < odd_count; ++index) {
cout << odd_nums[index] << " ";
}
cout << endl;
// Print the elements of the even array
cout << "Even elements: ";
for (int index = 0; index < even_count; ++index) {
cout << even_nums[index] << " ";
}
cout << endl;
}
Java
import java.util.Scanner;
public class LearnYard {
// Function to separate odd and even elements
public static void separateOddEven(int[] nums, int size) {
int oddCount = 0, evenCount = 0;
// Count odd and even elements
for (int i = 0; i < size; ++i) {
if (nums[i] % 2 == 0) {
evenCount++;
} else {
oddCount++;
}
}
int[] oddNums = new int[oddCount];
int[] evenNums = new int[evenCount];
int oddIndex = 0, evenIndex = 0;
// Separate elements into odd and even arrays
for (int i = 0; i < size; ++i) {
if (nums[i] % 2 == 0) {
evenNums[evenIndex++] = nums[i];
}
else {
oddNums[oddIndex++] = nums[i];
}
}
// Print the elements of the odd array
System.out.print("Odd elements: ");
for (int i = 0; i < oddCount; ++i) {
System.out.print(oddNums[i] + " ");
}
System.out.println();
// Print the elements of the even array
System.out.print("Even elements: ");
for (int i = 0; i < evenCount; ++i) {
System.out.print(evenNums[i] + " ");
}
System.out.println();
}
}
Python
# Function to separate odd and even elements
def separateOddEven(nums, size):
odd_count = 0
even_count = 0
# Count odd and even elements
for num in nums:
if num % 2 == 0:
even_count += 1
else:
odd_count += 1
odd_nums = [0] * odd_count
even_nums = [0] * even_count
odd_index = 0
even_index = 0
# Separate elements into odd and even arrays
for num in nums:
if num % 2 == 0:
even_nums[even_index] = num
even_index += 1
else:
odd_nums[odd_index] = num
odd_index += 1
# Print the elements of the odd array
print("Odd elements:", " ".join(map(str, odd_nums)))
# Print the elements of the even array
print("Even elements:", " ".join(map(str, even_nums)))
Javascript
// Function to separate odd and even elements
function separateOddEven(nums, size) {
let odd_count = 0, even_count = 0;
// Count odd and even elements
for (let i = 0; i < size; ++i) {
if (nums[i] % 2 === 0) {
even_count++;
} else {
odd_count++;
}
}
let odd_nums = new Array(odd_count);
let even_nums = new Array(even_count);
let odd_index = 0, even_index = 0;
// Separate elements into odd and even arrays
for (let i = 0; i < size; ++i) {
if (nums[i] % 2 === 0) {
even_nums[even_index++] = nums[i];
} else {
odd_nums[odd_index++] = nums[i];
}
}
// Print the elements of the odd array
console.log("Odd elements: " + odd_nums.join(" "));
// Print the elements of the even array
console.log("Even elements: " + even_nums.join(" "));
}Time Complexity : O(n)
The time complexity of the approach is determined by the two iterations over the array nums.
- First Iteration (Counting Elements): We first iterate through each element of nums to count the number of odd and even elements. If n is the size of the array nums, this loop runs n times, and each counting operation takes constant time, O(1).
- Second Iteration (Separating Elements): We then iterate through each element of nums again to place them into the odd_nums and even_nums arrays. This loop also runs n times, and each assignment operation (e.g., odd_nums[odd_index] = nums[i]) takes constant time, O(1).
Since both loops run independently, the total time complexity is O(n) + O(n) = O(n).
Space Complexity : O(n)
Total Space Complexity: O(n)
- Input Array (nums):
The input array nums contains n elements, so it takes up O(n) space. - New Arrays (odd_nums and even_nums):
Two new arrays, odd_nums and even_nums, are created to store the odd and even elements respectively. - The size of odd_nums is proportional to the number of odd elements, and the size of even_nums is proportional to the number of even elements.
- Together, these two arrays will store all n elements from the original array nums. Therefore, the space required for these arrays is O(n).
Thus, the total space used by the algorithm, including the input and the new arrays, is O(n).
Auxiliary Space Complexity: O(n)
Auxiliary space refers to the extra space used by the algorithm excluding the input data.
- New Arrays (odd_nums and even_nums):
These two arrays are used to store the separated odd and even elements. Their combined size is O(n), as they store all elements of the original array. - Other Variables:
The algorithm uses a few additional variables like odd_count, even_count, odd_index, and even_index, which only require constant space O(1).
Since the primary extra space used by the algorithm is for the odd_nums and even_nums arrays, the auxiliary space complexity is O(n).
As we progress in this discussion, we often need to perform operations such as finding the collective sum, product, or any other operation such as (GCD, or applying bitwise operations) on the entire array. Let’s now explore how these tasks can be accomplished. Since sum and product are the basic ones, we will discuss those here.
6. Write a program that takes an array as input and calculates both the sum and the product of all the elements in the array.
Example
Input: nums = [1, 2, 3, 4]
Output:
Sum: 10
Product: 24
Explanation: The sum of the elements (1 + 2 + 3 + 4) is 10, and the product (1 * 2 * 3 * 4) is 24.
Input: nums = [5, 6, 7]
Output:
Sum: 18
Product: 210
Explanation: The sum of the elements (5 + 6 + 7) is 18, and the product (5 * 6 * 7) is 210.
Approach
To solve the problem of finding the sum and product of all elements in an array, we need to focus on two main tasks: adding the values of all elements together to get the sum, and multiplying the values of all elements together to get the product.
Imagine you have a list of numbers, and you want to know two things:
- What is the total when you add all the numbers together?
- What is the result when you multiply all the numbers together?
For example, if you have numbers [2, 3, 4], you would want to:
- Add them: 2 + 3 + 4 = 9
- Multiply them: 2 * 3 * 4 = 24
To keep track of the sum and product as we go through the list, we use two variables:
- sum will start at 0 because adding 0 to any number doesn't change the number.
- product will start at 1 because multiplying by 1 doesn’t change the number.
We will use a loop to go through each number in the array. As we encounter each number:
- Add the number to our sum variable. (sum += nums[index])
- Multiply the number with our product variable. (product *= nums[index])
Once we’ve gone through the entire array, sum will hold the total sum of all the numbers, and product will hold the total product of all the numbers.
Dry Run
Input: nums = [1, 2, 3, 4]
- Initialization:
- sum = 0
- product = 1
- First Iteration (index = 0):
- Current number = 1
- sum = sum + 1 = 0 + 1 = 1
- product = product * 1 = 1 * 1 = 1
- Second Iteration (index = 1):
- Current number = 2
- sum = sum + 2 = 1 + 2 = 3
- product = product * 2 = 1 * 2 = 2
- Third Iteration (index = 2):
- Current number = 3
- sum = sum + 3 = 3 + 3 = 6
- product = product * 3 = 2 * 3 = 6
- Fourth Iteration (index = 3):
- Current number = 4
- sum = sum + 4 = 6 + 4 = 10
- product = product * 4 = 6 * 4 = 24
- Output:
- Sum: 10
- Product: 24
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to calculate the sum and product of the array
void calculateSumAndProduct(int nums[], int size) {
// Initialize variables to store the sum and product
int sum = 0;
int product = 1;
// Loop through the array to calculate the sum and product
for (int index = 0; index < size; ++index) {
// Add the value at the current index to the sum
sum += nums[index];
// Multiply the value at the current index to the product
product *= nums[index];
}
// Print the calculated sum
cout << "Sum: " << sum << endl;
// Print the calculated product
cout << "Product: " << product << endl;
}Java
import java.util.Scanner;
public class LearnYard {
// Function to calculate the sum and product of the array
public static void calculateSumAndProduct(int[] nums, int size) {
// Initialize variables to store the sum and product
int sum = 0;
int product = 1;
// Loop through the array to calculate the sum and product
for (int index = 0; index < size; ++index) {
// Add the value at the current index to the sum
sum += nums[index];
// Multiply the value at the current index to the product
product *= nums[index];
}
// Print the calculated sum
System.out.println("Sum: " + sum);
// Print the calculated product
System.out.println("Product: " + product);
}
}Python
# Function to calculate the sum and product of the array
def calculate_sum_and_product(nums):
# Initialize variables to store the sum and product
sum = 0
product = 1
# Loop through the array to calculate the sum and product
for num in nums:
# Add the current number to the sum
sum += num
# Multiply the current number to the product
product *= num
# Print the calculated sum
print("Sum:", sum)
# Print the calculated product
print("Product:", product)Javascript
// Function to calculate the sum and product of the array
function calculateSumAndProduct(nums) {
// Initialize variables to store the sum and product
let sum = 0;
let product = 1;
// Loop through the array to calculate the sum and product
for (let i = 0; i < nums.length; i++) {
// Add the current number to the sum
sum += nums[i];
// Multiply the current number to the product
product *= nums[i];
}
// Print the calculated sum
console.log("Sum:", sum);
// Print the calculated product
console.log("Product:", product);
}
Time Complexity: O(n)
Here, n is the number of elements in the array. The loop iterates through each element in the array exactly once, performing a constant-time operation (addition and multiplication) for each element. Therefore, the time complexity is linear, or O(n).
Space Complexity: O(1)
When discussing space complexity, it's important to consider both the total space used by the algorithm and the auxiliary space—the extra space used beyond the input.
1. Total Space Complexity: O(n)
- Input Array Space: The array itself takes up space, which is proportional to its size. If the array has n elements, the space required to store the array is O(n).
- Variables (sum, product): These two variables require constant space, O(1), because they are independent of the size of the array.
2. Auxiliary Space Complexity: O(1)
- Auxiliary Space: This refers to the extra space used by the algorithm, excluding the input data. In this approach, the only extra space used is for the two variables sum and product.
- Since these variables do not depend on the size of the array, the auxiliary space complexity is O(1).