Array III
When working with arrays, a common task is to count how many times a particular element appears in the array. This is often needed in scenarios where we want to analyze the frequency of specific values or simply check the occurrence of a target element. Let’s explore how to achieve this by writing a program that takes an array and a target number as input and counts the number of times the target number appears in the array.
7. Write a program that takes an array and a target number as input and counts the number of times the target number appears in the array.
Example
Input: nums = [1, 2, 3, 4, 2, 2, 5], target = 2
Output: Count: 3
Explanation: The number 2 appears 3 times in the array [1, 2, 3, 4, 2, 2, 5].
Input: nums = [5, 6, 7, 8, 5, 9], target = 5
Output: Count: 2
Explanation: The number 5 appears 2 times in the array [5, 6, 7, 8, 5, 9].
Approach
In this problem, our task is to count how many times the target number appears in an array. So first we create a variable “count” and set it to 0 this is our counter. We need a counter to keep track of how many times the target number appears in the array. Without a counter, we would not be able to record the events as we traverse the array. Now use a loop to iterate over each element in the array. For each element, we need to check whether the element corresponds to the target number. If so, increment the count by 1. After the loop checks all the elements, the count variable contains the number of times the target number appeared in the array. Output or return this value.
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to count occurrences of the target number in the array
int countOccurrences(int nums[], int size, int target) {
// Initialize a counter to keep track of occurrences
int count = 0;
// Loop through the array to count occurrences of the target number
for (int index = 0; index < size; ++index) {
// If the current element matches the target, increment the count
if (nums[index] == target) {
++count;
}
}
// Return the final count
return count;
}
int main() {
// Read the size of the array
int size;
cin >> size;
// Declare the array
int nums[size];
// Read array elements
for (int i = 0; i < size; ++i) {
cin >> nums[i];
}
// Read the target value
int target;
cin >> target;
// Call the function and output the result
cout << countOccurrences(nums, size, target);
return 0;
}
Java
import java.util.Scanner;
public class CountOccurrences {
// Function to count occurrences of the target number in the array
static int countOccurrences(int[] nums, int target) {
// Initialize a counter to keep track of occurrences
int count = 0;
// Loop through the array to count occurrences of the target number
for (int num : nums) {
// If the current element matches the target, increment the count
if (num == target) {
count++;
}
}
// Return the final count
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Read the size of the array
int size = sc.nextInt();
// Declare the array
int[] nums = new int[size];
// Read array elements
for (int i = 0; i < size; i++) {
nums[i] = sc.nextInt();
}
// Read the target value
int target = sc.nextInt();
// Call the function and print the result
System.out.println(countOccurrences(nums, target));
}
}
Python
# Function to count occurrences of the target number in the array
def count_occurrences(nums, target):
# Initialize a counter to keep track of occurrences
count = 0
# Loop through the array to count occurrences of the target number
for num in nums:
# If the current element matches the target, increment the count
if num == target:
count += 1
# Return the final count
return count
# Read the size of the array
size = int(input())
# Read the array elements
nums = list(map(int, input().split()))
# Read the target value
target = int(input())
# Call the function and print the result
print(count_occurrences(nums, target))
Javascript
// Function to count occurrences of the target number in the array
function countOccurrences(nums, target) {
// Initialize a counter to keep track of occurrences
let count = 0;
// Loop through the array to count occurrences of the target number
for (let num of nums) {
// If the current element matches the target, increment the count
if (num === target) {
count++;
}
}
// Return the final count
return count;
}
// Read input data
const size = parseInt(prompt());
const nums = Array.from({ length: size }, () => parseInt(prompt()));
const target = parseInt(prompt());
// Call the function and log the result
console.log(countOccurrences(nums, target));
Time Complexity: O(n)
The loop iterates through each element in the array exactly once, checking if it matches the target number. Since this is a linear scan, the time complexity is O(n), where n is the number of elements in the array.
Space Complexity: O(n)
Total Space Complexity: O(n)
The input array itself takes up space equal to its size, O(n). The only additional space used is for the count variable, which is O(1).
Auxiliary Space Complexity: O(1)
The auxiliary space is the extra space used by the algorithm beyond the input data. In this approach, the only extra space used is the count variable, which requires constant space, O(1).
As we continue our progress in this article, as arrays which is a fundamental data structure representing a collection of similar elements—it's essential to consider the array's organization, particularly whether it is sorted or unsorted. The state of sorting is a crucial property, as it directly influences the efficiency and feasibility of various algorithms and operations. For instance, determining whether an array is sorted is often a preliminary step before executing more complex tasks, such as binary search, where the correct functioning of the algorithm depends on the ordered arrangement of elements. Understanding whether an array is sorted allows us to make informed decisions about which algorithms to apply, thereby optimizing performance and ensuring accurate outcomes.
8. Write a program that takes an array as input and checks if it is sorted in forward order, backward order, or not sorted at all.
Example
Input: nums = [1, 2, 3, 4, 5]
Output: Sorted in Forward Order
Explanation: The array [1, 2, 3, 4, 5] is in ascending order, meaning it is sorted in forward order.
Input: nums = [5, 4, 3, 2, 1]
Output: Sorted in Backward Order
Explanation: The array [5, 4, 3, 2, 1] is in descending order, meaning it is sorted in backward order.
Input: nums = [3, 1, 4, 2, 5]
Output: Not Sorted
Explanation: The array [3, 1, 4, 2, 5] is neither in ascending nor descending order, so it is not sorted.
Approach
In this problem, we want to determine whether a given array is sorted in ascending order (forward order), descending order (backward order), or if it is not sorted at all. So there is an elementary logic to say whether an array is sorted in ascending or descending order or it is unsorted which is :
- Ascending Order (Forward Order): An array is in ascending order if each element is less than or equal to the next element. For example, [1, 2, 3, 4, 5] is in ascending order.
- Descending Order (Backward Order): An array is in descending order if each element is greater than or equal to the next element. For example, [5, 4, 3, 2, 1] is in descending order.
- Not Sorted: If an array does not follow either of the above rules, it is not sorted. For example, [3, 1, 4, 2, 5] is not sorted because it does not consistently increase or decrease.
From the above 3 points, we know the necessary conditions for an array to be sorted. An array will be sorted if and only if all its elements follow either the ascending order or the descending order condition. Therefore, if at any comparison either of the conditions is not met, the array will be considered unsorted.
How do we know that a comparison failed in between?
For that we will declare 2 flags. These flags are booleans which help us track whether the array is in ascending or descending order as we go through it.
- isAscending: We set this to true initially, assuming the array might be in ascending order. If for any comparison the condition is not satisfied we will change it to false.
- isDescending: We set this to true initially, assuming the array might be in descending order. If for any comparison the condition is not satisfied we will change it to false.
Now we will start traversing the array
We use a loop to go through the array from the first element to the second-to-last element.
Why looping till second last index not the last index?
If the loop runs from 0 to n-1, the last iteration would attempt to compare the element at index n-1 with the element at index n, which does not exist. This would result in accessing memory out of bounds and potentially cause a runtime error.
For each element, we compare it with the next one:
- Check for Ascending Order: If the current element is greater than the next one, it means the array is not in ascending order, so we set isAscending to false.
- Check for Descending Order: If the current element is less than the next one, it means the array is not in descending order, so we set isDescending to false.
- Why do we do this?: By checking both ascending and descending conditions as we move through the array, we can determine the array's order with a single pass.
After the loop finishes we will check the flags there are 3 possibilities for that
- If isAscending is still true, the array is sorted in ascending (forward) order.
- If isDescending is still true, the array is sorted in descending (backward) order.
- If both flags are false, the array is not sorted.
Based on the flag’s values, we return or print whether the array is sorted in forward order, backward order, or not sorted at all.
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to check if the array is sorted forward, backward, or not sorted
string checkSorted(int nums[], int size) {
// Initialize flags for ascending and descending order
bool isAscending = true;
bool isDescending = true;
// Iterate through the array to check order
for (int i = 0; i < size - 1; ++i) {
// If current element is greater than the next, it's not ascending
if (nums[i] > nums[i + 1]) {
isAscending = false;
}
// If current element is smaller than the next, it's not descending
if (nums[i] < nums[i + 1]) {
isDescending = false;
}
}
// Return results based on the flags
if (isAscending) {
return "Sorted in Forward Order";
} else if (isDescending) {
return "Sorted in Backward Order";
} else {
return "Not Sorted";
}
}
int main() {
// Read the size of the array
int size;
cin >> size;
// Declare the array
int nums[size];
// Read array elements
for (int i = 0; i < size; ++i) {
cin >> nums[i];
}
// Call the function and output the result
cout << checkSorted(nums, size);
return 0;
}
Java
import java.util.Scanner;
public class CheckArraySorted {
// Function to check if the array is sorted forward, backward, or not sorted
static String checkSorted(int[] nums, int size) {
// Initialize flags for ascending and descending order
boolean isAscending = true;
boolean isDescending = true;
// Iterate through the array to check order
for (int i = 0; i < size - 1; i++) {
// If current element is greater than the next, it's not ascending
if (nums[i] > nums[i + 1]) {
isAscending = false;
}
// If current element is smaller than the next, it's not descending
if (nums[i] < nums[i + 1]) {
isDescending = false;
}
}
// Return results based on the flags
if (isAscending) {
return "Sorted in Forward Order";
} else if (isDescending) {
return "Sorted in Backward Order";
} else {
return "Not Sorted";
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Read the size of the array
int size = sc.nextInt();
// Declare and initialize the array
int[] nums = new int[size];
// Read array elements
for (int i = 0; i < size; i++) {
nums[i] = sc.nextInt();
}
// Call the function and print the result
System.out.println(checkSorted(nums, size));
}
}
Python
# Function to check if the array is sorted forward, backward, or not sorted
def check_sorted(nums):
# Initialize flags for ascending and descending order
is_ascending = True
is_descending = True
# Iterate through the array to check order
for i in range(len(nums) - 1):
# If current element is greater than the next, it's not ascending
if nums[i] > nums[i + 1]:
is_ascending = False
# If current element is smaller than the next, it's not descending
if nums[i] < nums[i + 1]:
is_descending = False
# Return results based on the flags
if is_ascending:
return "Sorted in Forward Order"
elif is_descending:
return "Sorted in Backward Order"
else:
return "Not Sorted"
# Read the size of the array
size = int(input())
# Read the array elements
nums = list(map(int, input().split()))
# Call the function and print the result
print(check_sorted(nums))
Javascript
// Function to check if the array is sorted forward, backward, or not sorted
function checkSorted(nums) {
// Initialize flags for ascending and descending order
let isAscending = true;
let isDescending = true;
// Iterate through the array to check order
for (let i = 0; i < nums.length - 1; i++) {
// If current element is greater than the next, it's not ascending
if (nums[i] > nums[i + 1]) {
isAscending = false;
}
// If current element is smaller than the next, it's not descending
if (nums[i] < nums[i + 1]) {
isDescending = false;
}
}
// Return results based on the flags
if (isAscending) {
return "Sorted in Forward Order";
} else if (isDescending) {
return "Sorted in Backward Order";
} else {
return "Not Sorted";
}
}
// Read input size and elements
const size = parseInt(prompt());
const nums = Array.from({ length: size }, () => parseInt(prompt()));
// Call the function and log the result
console.log(checkSorted(nums));
Time Complexity: O(n)
The time complexity of this problem is O(n), where n is the number of elements in the array.
This is because we traverse the array exactly once, comparing each element with the next one to check for ascending or descending order. Since the loop iterates from the first element to the second-to-last element, performing a constant-time comparison at each step, the total number of operations scales linearly with the size of the array.
Space Complexity : O(n)
- Total Space Complexity: The total space complexity considers both the input space and any extra space used by the algorithm. For this problem, the total space complexity is O(n), where n is the number of elements in the input array. This is because the input array itself requires space proportional to its size.
- Auxiliary Space Complexity: The auxiliary space complexity refers to the extra space required by the algorithm, excluding the input data. In this problem, the auxiliary space complexity is O(1) because we only use a fixed amount of extra space, regardless of the input array size.
In the process of analyzing data within arrays, it's often crucial to differentiate between unique elements and duplicate elements. This can provide insights into the diversity of data, help detect redundancies, or even optimize storage by identifying repeated values. Understanding the frequency of unique versus duplicate elements is a key step in many data analysis tasks. So let’s see how we can identify a unique element and a duplicate in a given array.
9. Write a program that takes an array whose value lies from 1 to 100 as input and counts the number of unique and duplicate elements.
Examples
Input: nums = [1, 2, 2, 3, 4, 4, 4, 5]
Output: Unique Count = 3, Duplicate Count = 3
Explanation: In the array [1, 2, 2, 3, 4, 4, 4, 5], the elements 1, 3, and 5 are unique because they appear only once. The elements 2 and 4 are duplicates. Specifically, 2 appears twice (1 duplicate), and 4 appears three times (2 duplicates), giving a total of 3 duplicates.
Input: nums = [7, 7, 7, 7]
Output: Unique Count = 0, Duplicate Count = 3
Explanation: In the array [7, 7, 7, 7], the element 7 appears four times, with 3 duplicates, and no unique elements.
Approach
To determine whether an element is unique or a duplicate, we need to count the frequency of each element in the array. A value is considered unique if it appears exactly once in the array, and it is considered a duplicate if it appears more than once.
In a previous problem, we counted the occurrences of a single target value in an array by using a simple counter. However, this problem requires us to track the frequency of all elements in the array, not just one. Since the values in the array range from 1 to 100, using a separate variable for each possible value would be inefficient and cumbersome.
Instead, we can use a Hash Array
What is a Hash Array?
A hash array is a simple data structure that uses an array to store values based on their hash (or mapped index). In the context of this problem, a hash array is essentially a regular array where the index corresponds to the value in the input array, and the value at that index represents the frequency (or count) of that element.
Example:
Consider an array with elements ranging from 1 to 100. We can create a hash array of size 101 (to cover indices 1 through 100) where:
- The index of the hash array represents the element from the input array.
- The value at that index stores the frequency of that element.
If the element 7 appears three times in the input array, we would increment the value at index 7 in the hash array to 3. This way, the hash array allows us to efficiently track the frequency of every element.
So the first step towards writing the code is to declare and initialize the hash array. A hash array can be declared like a regular array. For this specific problem, since the array elements are expected to be within the range of 1 to 100, the hash array should have 101 elements (index 0 to 100). An initialize the all its values to 0.
Why Do We Take Its Size as 101 Instead of 100?
We take the size of the hash array as 101 rather than 100 as the elements in the input array range from 1 to 100. To directly map each element to an index in the hash array, we need an index that corresponds to each value in this range.If we used a size of 100, the highest index in the array would be 99, which would not allow us to store the frequency of the element 100.
Why is it Initialized with 0?
The purpose of the hash array is to count the occurrences of elements in the input array. Before any elements are processed, the frequency of all elements is zero. Initializing the array with 0 ensures that every index starts with a count of zero. As we traverse the input array, we will increment the corresponding index in the hash array to track how many times each element appears.
After filling the hash_table we will declare two variables unique_count and duplicate_count to count the number of unique and duplicate elements respectively and then, we loop through the array from index 1 to 100:
- If the value at an index is 1 or hash_table[x] == 1, it means the element x is unique, so we increment unique_count.
- If the value is greater than 1 or hash_table[x] > 1, it means the element x has duplicates. We calculate the number of duplicates for that element as frequency - 1 or hash_table[x] -1, and add this to duplicate_count.
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to count the number of unique and duplicate elements in the array
void countUniqueAndDuplicates(int nums[], int n) {
// Initialize a hash table (array) for values 1 to 100
int hash_table[101] = {0};
// Count frequencies of each element using the hash table
for (int i = 0; i < n; ++i) {
// Increment the frequency count for this number in the hash table
hash_table[nums[i]]++;
}
// Variables to store the counts of unique and duplicate elements
int unique_count = 0, duplicate_count = 0;
// Calculate unique and duplicate counts by traversing the hash table
for (int i = 1; i <= 100; ++i) {
// If the frequency is 1, the element is unique
if (hash_table[i] == 1) {
unique_count++;
}
// If the frequency is greater than 1, the element has duplicates
else if (hash_table[i] > 1) {
// The number of duplicates for this element is (frequency - 1)
duplicate_count += hash_table[i] - 1;
}
}
// Output the results
cout << unique_count << " " << duplicate_count << endl;
}
int main() {
// Read the size of the array
int n;
cin >> n;
// Declare the array
int nums[n];
// Read the array elements
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
// Call the function to count unique and duplicate elements
countUniqueAndDuplicates(nums, n);
return 0;
}
Java
import java.util.Scanner;
public class UniqueAndDuplicateCount {
// Function to count the number of unique and duplicate elements in the array
static void countUniqueAndDuplicates(int[] nums, int n) {
// Initialize a hash table for values 1 to 100
int[] hashTable = new int[101];
// Count frequencies of each element using the hash table
for (int i = 0; i < n; i++) {
// Increment the frequency count for this number in the hash table
hashTable[nums[i]]++;
}
// Variables to store the counts of unique and duplicate elements
int uniqueCount = 0, duplicateCount = 0;
// Calculate unique and duplicate counts by traversing the hash table
for (int i = 1; i <= 100; i++) {
// If the frequency is 1, the element is unique
if (hashTable[i] == 1) {
uniqueCount++;
}
// If the frequency is greater than 1, the element has duplicates
else if (hashTable[i] > 1) {
// The number of duplicates for this element is (frequency - 1)
duplicateCount += hashTable[i] - 1;
}
}
// Output the results
System.out.println(uniqueCount + " " + duplicateCount);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Read the size of the array
int n = sc.nextInt();
// Declare and initialize the array
int[] nums = new int[n];
// Read the array elements
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// Call the function to count unique and duplicate elements
countUniqueAndDuplicates(nums, n);
}
}
Python
# Function to count the number of unique and duplicate elements in the array
def count_unique_and_duplicates(nums):
# Initialize a hash table (list) for values 1 to 100
hash_table = [0] * 101
# Count frequencies of each element using the hash table
for num in nums:
# Increment the frequency count for this number in the hash table
hash_table[num] += 1
# Variables to store the counts of unique and duplicate elements
unique_count = 0
duplicate_count = 0
# Calculate unique and duplicate counts by traversing the hash table
for freq in hash_table[1:]: # Only iterate from 1 to 100
# If the frequency is 1, the element is unique
if freq == 1:
unique_count += 1
# If the frequency is greater than 1, the element has duplicates
elif freq > 1:
# The number of duplicates for this element is (frequency - 1)
duplicate_count += freq - 1
# Output the results
print(unique_count, duplicate_count)
# Read the size of the array
n = int(input())
# Read the array elements
nums = list(map(int, input().split()))
# Call the function to count unique and duplicate elements
count_unique_and_duplicates(nums)
Javascript
// Function to count the number of unique and duplicate elements in the array
function countUniqueAndDuplicates(nums) {
// Initialize a hash table (array) for values 1 to 100
const hashTable = Array(101).fill(0);
// Count frequencies of each element using the hash table
for (const num of nums) {
// Increment the frequency count for this number in the hash table
hashTable[num]++;
}
// Variables to store the counts of unique and duplicate elements
let uniqueCount = 0, duplicateCount = 0;
// Calculate unique and duplicate counts by traversing the hash table
for (let i = 1; i <= 100; i++) {
// If the frequency is 1, the element is unique
if (hashTable[i] === 1) {
uniqueCount++;
}
// If the frequency is greater than 1, the element has duplicates
else if (hashTable[i] > 1) {
// The number of duplicates for this element is (frequency - 1)
duplicateCount += hashTable[i] - 1;
}
}
// Output the results
console.log(uniqueCount, duplicateCount);
}
// Read input data
const n = parseInt(prompt());
const nums = Array.from({ length: n }, () => parseInt(prompt()));
// Call the function to count unique and duplicate elements
countUniqueAndDuplicates(nums);
Time Complexity : O(n+m)
The time complexity of this problem is O(n + m), where n is the number of elements in the input array, and m is the range of possible values (the size of the frequency table). We first go through the array to build the frequency table, which takes O(n) time. Then, we traverse the frequency table to count unique and duplicate elements, taking O(m) time.
The total time complexity is the sum of both of these complexities which is nothing but
O(n) + O(m) = O(n+m)
Space Complexity : O(m)
1. Total Space Complexity: O(n + m)
O(n): This represents the space taken up by the input array. If the input array has n elements, storing this array requires O(n) space. This is often considered part of the total space complexity because the input data itself occupies memory.
O(m): This refers to the space used by the frequency table (or any other auxiliary data structure). The frequency table typically stores the count of unique elements, and if there are m unique elements, the space required for this table is O(m).
Thus, the total space complexity is O(n + m)
2. Auxiliary Space Complexity: O(m)
O(m): Auxiliary space complexity measures the extra space used by the algorithm that is not part of the input. In this case, the extra space is used by the frequency table, which stores counts for m unique elements.
Therefore, the auxiliary space complexity is O(m).