Maximum Sum of Subarray:
Average of Subarrays:
Smallest Subarray with a Given Sum:
Longest Subarray of 1's After Replacement:
Longest Substring With Distinct Characters:
Maximum Sum Subarray of At Least Size K:
Minimum Size Subarray Sum:
Longest Subarray with Sum Equals K:
Number of Subarrays with Odd Sum:
Diet Plan Performance:
Problem: Create a C program that evaluates the diet plan performance with a score. The score is calculated as the sum of calories over each contiguous subarray of days k. If the sum is lower than lower, score decreases by 1. If the sum is higher than upper, score increases by 1. The program should return the final score.
Example:
Input: calories[] = {1, 2, 3, 4, 5}, k = 3, lower = 5, upper = 10
Output: 0 (The subarrays are {1,2,3}, {2,3,4}, {3,4,5} with sums 6, 9, and 12. The score increments and decrements balance out to 0.)
Pair with Target Sum:
Remove Duplicates from Sorted Array:
Squaring a Sorted Array:
Backspace String Compare:
Trapping Rain Water:
Find the Maximum and Minimum Number in an Array:
Problem: Write a C program to find both the maximum and minimum numbers in a given array using a divide and conquer approach. The program should divide the array into two halves, recursively find the maximum and minimum in each half, and then compare them.
Example:
Input: arr[] = {3, 5, 1, 8, 4, 2}
Output: Max = 8, Min = 1
All Permutations of an Array:
Combination Sum:
Distinct Permutations of an Array:
Problem: Write a C program to generate all distinct permutations of a given array that may contain duplicates. Use a backtracking method to ensure that permutations with identical numbers are not repeated.
Example:
Input: arr[] = {1, 2, 2}
Output: [1, 2, 2], [2, 1, 2], [2, 2, 1]
Details: The program should account for repeated elements and avoid generating duplicate permutations. This can be managed by sorting the array first and then using a boolean array to keep track of elements that have been used in the current recursive call.
Combinations Sum II:
Problem: Develop a C program that finds all unique combinations in a given array where the candidate numbers sum to a target number T. Each number in the array may only be used once in the combination.
Example:
Input: arr[] = {10, 1, 2, 7, 6, 1, 5}, T = 8
Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Details: The array may contain duplicates, which may lead to duplicate combinations if not handled properly. Sort the array to handle duplicates more easily and use backtracking to explore possible combinations. Skip over consecutive duplicate elements to avoid generating duplicate combinations.
Approach, solution, and explanation:
- Maximum Sum of Subarray:
To solve the problem of finding the maximum sum of a subarray of size k, we can utilize the "sliding window" technique, which is an optimized way to handle problems involving subarrays or substrings. Here’s a detailed approach:
Approach using Sliding Window Technique
Understanding the Problem: You are given an array and a number k. You need to find the maximum sum of any subarray with the size exactly k.
Sliding Window Concept: The idea is to maintain a window of size k that slides through the array from the beginning to the end. As the window slides, it encapsulates different parts of the array, and you need to calculate and compare the sums of these windows.
Implementation Steps:
Initialize the sum of the first k elements.
Slide the window across the array by moving one position to the right at a time.
Update the sum by subtracting the element that is left out of the window and adding the element that is newly included in the window.
Keep track of the maximum sum encountered as you slide the window.
Implementation
#include <stdio.h>
int maxSumSubarray(int arr[], int n, int k) {
if (n < k) {
printf("Invalid input");
return -1;
}
int max_sum = 0;
for (int i = 0; i < k; i++) {
max_sum += arr[i];
}
int window_sum = max_sum;
for (int i = k; i < n; i++) {
window_sum += arr[i] - arr[i - k];
if (window_sum > max_sum) {
max_sum = window_sum;
}
}
return max_sum;
}
int main() {
int arr[] = {2, 1, 5, 1, 3, 2};
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = maxSumSubarray(arr, n, k);
printf("Maximum sum of a subarray of size %d is %d\n", k, max_sum);
return 0;
}
Example and Explanation
Let’s take the array {2, 1, 5, 1, 3, 2} with k = 3.
- Initially, calculate the sum of the first three elements:
2 + 1 + 5 = 8.
Initial window: [2, 1, 5], 1, 3, 2
Initial sum = 8
- Slide the window right by one element, updating the sum:
Previous window: [2, 1, 5], 1, 3, 2
Slide to: 2, [1, 5, 1], 3, 2
New sum = 8 - 2 + 1 = 7
- Continue sliding and updating the sum:
Previous window: 2, [1, 5, 1], 3, 2
Slide to: 2, 1, [5, 1, 3], 2
New sum = 7 - 1 + 3 = 9 (Maximum so far)
Previous window: 2, 1, [5, 1, 3], 2
Slide to: 2, 1, 5, [1, 3, 2]
New sum = 9 - 5 + 2 = 6
The maximum sum encountered was 9 from the subarray {5, 1, 3}.
This solution effectively uses the sliding window technique to efficiently compute the maximum sum subarray of size k, ensuring a time complexity of O(n), which is optimal for this problem.
- Average of Subarrays:
To solve the problem of calculating the average of all contiguous subarrays of size k in a given array, we can utilize the "sliding window" technique, which efficiently handles problems involving subarrays or substrings. Here’s a step-by-step approach:
Approach using Sliding Window Technique
Understanding the Problem: You need to find the average of all subarrays of size k within a given array.
Sliding Window Concept: This involves maintaining a window of size k that slides through the array from start to end, computing the sum and then the average of elements within the window at each step.
Implementation Steps:
Compute the sum of the first k elements.
Calculate and store the average of this initial window.
Slide the window across the array by one element at a time:
Implementation
#include <stdio.h>
void findAverages(int arr[], int n, int k) {
if (n < k) {
printf("Invalid input.");
return;
}
double windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
printf("[%0.1f", windowSum / k);
for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k];
printf(", %0.1f", windowSum / k);
}
printf("]\n");
}
int main() {
int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
findAverages(arr, n, k);
return 0;
}
Example and Explanation
Let’s use the array {1, 3, 2, 6, -1, 4, 1, 8, 2} with k = 5.
Initial Setup:
First, sum the elements of the first window of size k: 1 + 3 + 2 + 6 - 1 = 11.
The average is 11 / 5 = 2.2.
Initial window: [1, 3, 2, 6, -1], 4, 1, 8, 2
Initial average = 2.2
First Slide:
Slide the window right: subtract 1 (first element of the old window) and add 4 (first element outside the old window).
New sum is 11 - 1 + 4 = 14.
New average is 14 / 5 = 2.8.
Slide to: 1, [3, 2, 6, -1, 4], 1, 8, 2
New average = 2.8
Subsequent Slides:
- Continue sliding, updating the sum, and calculating the new average as shown.
Slide to: 1, 3, [2, 6, -1, 4, 1], 8, 2
New average = 2.4
Slide to: 1, 3, 2, [6, -1, 4, 1, 8], 2
New average = 3.6
Slide to: 1, 3, 2, 6, [-1, 4, 1, 8, 2]
New average = 2.8
Final output: [2.4, 2.8, 3.6, 3.4].
This method ensures that the computation is efficient with a time complexity of (O(n)), avoiding redundant recalculations by smartly adjusting the sum for each new window.
- Smallest Subarray with a Given Sum:
To solve the problem of finding the smallest subarray with a sum greater than or equal to a given value s, the "sliding window" or "two pointer" technique is highly effective. This approach dynamically adjusts the size of the window (subarray) based on the running sum compared to s.
Approach using Two Pointer Technique
Understanding the Problem: You need to determine the smallest subarray whose sum is at least s.
Sliding Window/Two Pointer Concept: Maintain a window that can expand and contract as needed. Begin with both pointers at the start of the array, expand the window by moving the right pointer to increase the sum, and contract by moving the left pointer to decrease the sum once it exceeds s.
Implementation Steps:
Initialize two pointers at the start of the array and a variable to keep track of the minimum length found.
Expand the right pointer to include more elements until the sum ≥ s.
Contract the window by moving the left pointer to the right to try and find a smaller subarray once the current window's sum is sufficient.
Update the minimum length each time a valid subarray is found.
Implementation
#include <stdio.h>
#include <limits.h>
int minSubArrayLen(int s, int arr[], int n) {
int min_len = INT_MAX;
int left = 0;
int sum = 0;
for (int right = 0; right < n; right++) {
sum += arr[right];
while (sum >= s) {
min_len = (right - left + 1 < min_len) ? (right - left + 1) : min_len;
sum -= arr[left++];
}
}
return (min_len == INT_MAX) ? 0 : min_len;
}
int main() {
int arr[] = {4, 2, 2, 7, 8, 1, 2, 8, 1, 0};
int s = 8;
int n = sizeof(arr) / sizeof(arr[0]);
int result = minSubArrayLen(s, arr, n);
printf("Smallest subarray length with sum >= %d is %d\n", s, result);
return 0;
}
Example and Explanation
Using the array {4, 2, 2, 7, 8, 1, 2, 8, 1, 0} with s = 8.
Initial Setup:
- Start with both pointers at the beginning. No sum yet.
Array: [4, 2, 2, 7, 8, 1, 2, 8, 1, 0]
^
| (both pointers start here)
Sum = 0
Expand Right Pointer:
Move right, increasing sum: 4, 6 (4+2), 8 (4+2+2).
When the sum reaches 8 with the elements {4, 2, 2}, check if smaller subarray possible.
Array: [4, 2, 2, 7, 8, 1, 2, 8, 1, 0]
^ ^
left right
Sum = 8 (valid, but keep trying for smaller subarray)
Contract and Expand Again:
Start contracting from the left to see if a smaller valid subarray exists.
Eventually, find {8} as the smallest subarray with a sum ≥ 8.
Array: [4, 2, 2, 7, 8, 1, 2, 8, 1, 0]
^
| (both pointers here on single `8`)
Min Length = 1
The output for this example is 1, indicating the smallest subarray is {8}. This solution provides a very efficient way to find the minimum length subarray, with a time complexity of (O(n)) due to each element being processed at most twice (once for expansion and once for contraction).
- Longest Subarray of 1's After Replacement:
To solve the problem of finding the length of the longest contiguous subarray of 1's with a maximum of k replacements of 0's, we use the "sliding window" or "two pointer" technique. This method allows us to efficiently manage the subarray bounds while keeping track of the number of 0's that could be converted to 1's.
Approach using Two Pointer Technique
Understanding the Problem: You need to determine the maximum length of a subarray that consists only of 1's after replacing at most k zeros in the array.
Sliding Window Concept: This involves maintaining a window that can dynamically adjust its size by moving the start (left pointer) and end (right pointer) based on the number of zeros within the window compared to k.
Implementation Steps:
Initialize two pointers (left and right) at the start of the array and a variable to track the number of zeros in the current window.
Expand the right pointer to include new elements in the window. Increment the zero count if the element is a zero.
If the zero count exceeds k, contract the window from the left until the zero count is less than or equal to k.
Update the maximum length of the window each time the conditions are met.
Implementation
#include <stdio.h>
int longestOnes(int arr[], int n, int k) {
int left = 0, right = 0;
int zeroCount = 0;
int maxLength = 0;
for (right = 0; right < n; right++) {
if (arr[right] == 0) {
zeroCount++;
}
while (zeroCount > k) {
if (arr[left] == 0) {
zeroCount--;
}
left++;
}
maxLength = (right - left + 1 > maxLength) ? right - left + 1 : maxLength;
}
return maxLength;
}
int main() {
int arr[] = {0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1};
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
int result = longestOnes(arr, n, k);
printf("The longest subarray of 1's after replacing at most %d zero(s) is %d\n", k, result);
return 0;
}
Example and Explanation
Let's use the example {0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1} with k = 2.
Initial Setup:
- Start with both pointers at the beginning. The window expands as the right pointer moves.
Array: [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
^
| (both pointers start here)
Zero count = 0 (initially)
Expanding Right Pointer:
- As the right pointer expands, include zeros and ones. Update zero count and adjust the left pointer if needed.
Expanding to include more elements:
Array: [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
^ ^
left right
Zero count = 2 (after including two zeros)
Contracting When Necessary:
- When zero count exceeds
k (not the case here), adjust the left pointer.
Ideal adjustment:
Array: [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
^ ^
left right
Zero count = 2
Maximum length = 6 (after replacement)
The output is 6, which is the maximum length of a subarray consisting of 1's after replacing at most two zeros. This solution provides an efficient way to maintain and adjust the subarray dynamically with a time complexity of (O(n)), processing each element a constant number of times.
- Longest Substring With Distinct Characters:
To solve the problem of finding the length of the longest substring with all distinct characters, we can effectively utilize the "sliding window" technique with two pointers. This approach ensures that you can dynamically adjust the window size to maintain only unique characters within the substring.
Approach using Sliding Window Technique
Understanding the Problem: You need to find the longest substring (a contiguous block of characters) within a given string where all characters are distinct.
Sliding Window Concept: This method involves maintaining a window that grows and shrinks based on the distinctiveness of characters within it.
Implementation Steps:
Initialize two pointers (left and right) at the start of the string to define the window boundaries.
Use a frequency array to keep track of the count of each character within the window.
Expand the window by moving the right pointer and update the character count.
If a character count exceeds 1 (indicating a repeat), shrink the window from the left until all characters in the window are unique again.
Keep track of the maximum window size encountered that satisfies the distinct character condition.
Implementation
#include <stdio.h>
#include <string.h>
#define MAX_CHARS 256
int longestDistinctSubstring(char *str) {
int n = strlen(str);
int left = 0, maxLength = 0;
int charCount[MAX_CHARS] = {0};
for (int right = 0; right < n; right++) {
charCount[str[right]]++;
while (charCount[str[right]] > 1) {
charCount[str[left]]--;
left++;
}
int currentLength = right - left + 1;
maxLength = (currentLength > maxLength) ? currentLength : maxLength;
}
return maxLength;
}
int main() {
char str[] = "araaci";
int result = longestDistinctSubstring(str);
printf("The longest substring with all distinct characters is of length %d\n", result);
return 0;
}
Example and Explanation
Let's take the example string "araaci".
Initial Setup:
- Start with both pointers at the beginning. The window size expands as the right pointer moves.
String: "araaci"
^
| (both pointers start here)
Expanding the Window:
String: "araaci"
^ ^
left right
Window: "araa" (distinct until the second 'a')
Contracting When Necessary:
- Once a duplicate character is encountered ('a'), contract from the left until all characters are unique.
String: "araaci"
^ ^
left right
Window: "raac" (now distinct, but smaller)
Continuing Expansion:
- Continue expanding and contracting as necessary to find the longest distinct substring.
The maximum length encountered here seems to be incorrectly mentioned in the initial example given ("araa" is not distinct). The correct output for "araaci" should be 3 for the substring "aci". The ASCII art examples and sliding window adjustments illustrate the dynamic checking and adjustment of the window to ensure all characters within it are unique, maximizing the substring length efficiently.
- Maximum Sum Subarray of At Least Size K:
To solve the problem of finding the maximum sum of any subarray with a size of at least k, we can utilize a variation of the "sliding window" technique combined with some dynamic programming principles. The challenge here is that the subarray size isn't fixed, but instead must be at least k.
Approach using a Modified Sliding Window Technique
Understanding the Problem: Determine the maximum sum of a subarray where the subarray's length is at least k.
Modified Sliding Window Concept: This involves using the sliding window technique to find the maximum sum subarray for a fixed size and then adjusting the technique to account for the variability in the subarray size.
Implementation Steps:
Compute the sum of the first k elements as the initial subarray.
Expand the window dynamically while keeping track of the maximum sum observed.
Use a cumulative sum or prefix sum approach to efficiently calculate the sum of the subarray as it expands beyond k elements.
Implementation
#include <stdio.h>
#include <limits.h> // For INT_MIN
int maxSumSubarray(int arr[], int n, int k) {
if (k > n) {
printf("Invalid input: k is larger than the array size.\n");
return -1;
}
int maxSum = INT_MIN;
int currentSum = 0;
for (int i = 0; i < k; i++) {
currentSum += arr[i];
}
maxSum = currentSum;
for (int i = k; i < n; i++) {
currentSum += arr[i] - arr[i - k];
maxSum = (currentSum > maxSum) ? currentSum : maxSum;
int tempSum = currentSum;
for (int j = i - k + 1; j < i; j++) {
tempSum += arr[j];
maxSum = (tempSum > maxSum) ? tempSum : maxSum;
}
}
return maxSum;
}
int main() {
int arr[] = {4, 3, 5, 2, 1, 3, 2};
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
int result = maxSumSubarray(arr, n, k);
printf("Maximum sum of a subarray of at least size %d is %d\n", k, result);
return 0;
}
Example and Explanation
Using the array {4, 3, 5, 2, 1, 3, 2} with k = 3.
Initial Setup:
- Start by calculating the sum of the first three elements.
Array: [4, 3, 5, 2, 1, 3, 2]
^ ^ ^
Initial window: 4 + 3 + 5 = 12
Sliding the Window:
- Slide the window and update the sum by adding the next element and subtracting the leftmost element of the previous window.
Slide 1:
Array: 4, [3, 5, 2, 1], 3, 2
Update window: 3 + 5 + 2 = 10 (remove 4, add 2)
Expand window: 3 + 5 + 2 + 1 = 11 (add 1)
Continue Expanding:
- Continue to update and optionally expand the window to find the maximum sum.
Final stages:
Array: 4, 3, [5, 2, 1, 3, 2]
Max window update: 5 + 2 + 1 + 3 + 2 = 13
The maximum sum found for a subarray of at least size k is 15 from the subarray {4, 3, 5, 2, 1}. This approach ensures efficient computation while maintaining the flexibility of varying subarray sizes.
- Minimum Size Subarray Sum:
To solve the problem of finding the minimum length of a contiguous subarray with a sum that is greater than or equal to a given value s, the optimal approach is to use the "sliding window" or "two pointer" technique. This method helps to find the minimal subarray length efficiently by adjusting the subarray boundaries dynamically based on the sum condition.
Approach using Sliding Window Technique
Understanding the Problem: You are to determine the minimal length of a subarray whose sum is at least s. The subarray must be contiguous.
Sliding Window Concept:
Start with two pointers, both initialized at the beginning of the array.
Expand the window by moving the right pointer and adding to the sum until the sum is greater than or equal to s.
Once the sum condition is met, attempt to minimize the window by moving the left pointer inward until the sum is less than s, then expand the window again. Track the minimum length during these adjustments.
Implementation Steps:
Initialize pointers and variables for the current sum and minimum length.
Expand the right pointer to include more elements in the sum.
Contract from the left when the sum condition is met to try and find a smaller valid subarray.
Record the minimum length each time a valid window is found.
Implementation
#include <stdio.h>
#include <limits.h> // For INT_MAX
int minSubArrayLen(int s, int arr[], int n) {
int minLength = INT_MAX;
int left = 0;
int sum = 0;
for (int right = 0; right < n; right++) {
sum += arr[right];
while (sum >= s) {
int currentLength = right - left + 1;
minLength = (currentLength < minLength) ? currentLength : minLength;
sum -= arr[left];
left++;
}
}
return (minLength == INT_MAX) ? 0 : minLength;
}
int main() {
int arr[] = {2, 3, 1, 2, 4, 3};
int s = 7;
int n = sizeof(arr) / sizeof(arr[0]);
int result = minSubArrayLen(s, arr, n);
printf("Minimal length of a subarray with sum >= %d is %d\n", s, result);
return 0;
}
Example and Explanation
Using the array {2, 3, 1, 2, 4, 3} with s = 7.
Initial Setup:
- Start with both pointers at the beginning. No sum yet.
Array: [2, 3, 1, 2, 4, 3]
^
| (both pointers start here)
Current Sum = 0
Expanding the Window:
- Expand by moving the right pointer and update the sum.
Step:
Array: [2, 3, 1, 2, 4, 3]
^ ^
left right
Sum = 2 + 3 + 1 + 2 = 8 (meets condition, sum ≥ 7)
Contracting the Window:
- Once the sum exceeds
s, start contracting from the left to find the minimal length.
Contracting:
Array: [2, 3, 1, 2, 4, 3]
^ ^
left right
Current Sum = 2 + 4 = 6 (below s, stop contracting, expand again)
Continue Expanding and Contracting:
- Continue this process to find the smallest window.
Final minimal window:
Array: [2, 3, 1, 2, 4, 3]
^ ^
left right
Minimum Length = 2 (subarray {4, 3})
This method ensures efficient computation with a time complexity of (O(n)), processing each element only once during the expansion and contraction phases. This makes it a highly effective way to solve the problem of finding the minimum subarray sum greater than or equal to s.
- Longest Subarray with Sum Equals K:
To solve the problem of finding the length of the longest contiguous subarray which sums to a given value k, we can utilize a technique involving prefix sums combined with a hashmap (in languages that support it, such as Python or Java). However, since C does not natively support hashmaps easily, we'll use a slightly less efficient approach using an array to store prefix sums and a brute force search to find the longest subarray with the desired sum.
Approach Using Prefix Sums
Understanding the Problem: The objective is to find a contiguous subarray where the sum of elements equals k.
Prefix Sum Concept: The sum of elements from index i to j in an array can be quickly calculated using the prefix sum array where prefix[j] - prefix[i-1] = sum(i to j).
Implementation Steps:
Compute a prefix sum array.
For each index, look back through earlier prefix sums to check if prefix[j] - k exists; if it does, calculate the subarray length from the difference in indices.
Maintain a record of the maximum length found.
Implementation
#include <stdio.h>
int longestSubarrayWithSumK(int arr[], int n, int k) {
int prefixSum[n];
int maxLength = 0;
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int sum = (start == 0) ? prefixSum[end] : prefixSum[end] - prefixSum[start - 1];
if (sum == k) {
int length = end - start + 1;
if (length > maxLength) {
maxLength = length;
}
}
}
}
return maxLength;
}
int main() {
int arr[] = {1, -1, 5, -2, 3};
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
int result = longestSubarrayWithSumK(arr, n, k);
printf("The longest subarray with sum %d is %d\n", k, result);
return 0;
}
Example and Explanation
Let's use the example {1, -1, 5, -2, 3} with k = 3.
Prefix Sum Calculation:
- Calculate prefix sums for the array:
[1, 0, 5, 3, 6].
Array: [ 1, -1, 5, -2, 3]
Prefix Sum:[ 1, 0, 5, 3, 6]
Find Longest Subarray:
- For each pair
(start, end), calculate the sum using the prefix sum and check if it matches k.
Check:
- For subarray starting at 0 and ending at 3, the sum is `prefix[3] = 3` (matches k)
- Length = end - start + 1 = 4 - 0 + 1 = 4
Result:
- The longest subarray with the sum
3 is found to be of length 4.
Longest Subarray:
[ 1, -1, 5, -2 ] -> Sum = 3, Length = 4
The use of a prefix sum simplifies the computation of the sum of any subarray, but checking every possible subarray can be inefficient. However, in C, without the use of additional data structures like hashmaps, this brute force method provides a clear and straightforward way to determine the longest subarray with the given sum.
- Number of Subarrays with Odd Sum:
To solve the problem of finding the number of subarrays with an odd sum in C, we can use a brute force approach by iterating through all possible subarrays, summing their elements, and counting how many have an odd sum. This method is straightforward but can be inefficient for very large arrays due to its quadratic time complexity.
Approach Using a Brute Force Technique
Understanding the Problem: The goal is to count all subarrays where the sum of the elements is odd.
Brute Force Method:
Iterate through each possible starting point of the subarray.
For each starting point, iterate through each possible ending point.
Sum the elements of the subarray from the starting point to the ending point.
Check if the sum is odd and increment a counter if it is.
Implementation Steps:
Use nested loops: the outer loop to set the starting point of the subarray, and the inner loop to set the ending point.
Calculate the sum of elements within the bounds set by the outer and inner loops.
Use a simple condition to check if the sum is odd (e.g., sum % 2 != 0).
Implementation
#include <stdio.h>
int countOddSumSubarrays(int arr[], int n) {
int count = 0;
for (int start = 0; start < n; start++) {
int sum = 0;
for (int end = start; end < n; end++) {
sum += arr[end];
if (sum % 2 != 0) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int result = countOddSumSubarrays(arr, n);
printf("Number of subarrays with odd sum: %d\n", result);
return 0;
}
Example and Explanation
Let's take the example {1, 2, 3, 4, 5}.
Initial Setup:
- Start with calculating subarrays beginning from the first element.
Array: [1, 2, 3, 4, 5]
Subarray Calculation:
- Iterate through subarrays starting with each element.
Starting at 0:
Subarrays: [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]
Odd sums: 1 3 6 10 15
O O E E O (O = Odd, E = Even)
Starting at 1:
Subarrays: [2], [2, 3], [2, 3, 4], [2, 3, 4, 5]
Odd sums: 2 5 9 14
E O O E
...and so on for each starting element
Counting:
- As shown, subarrays such as
{1}, {1, 2}, and {2, 3} have odd sums. You continue this for all starting positions and count all subarrays with odd sums.
The code example calculates the sum of each possible subarray and checks if it is odd. This approach ensures that all subarrays are considered, and though it might not be the most efficient for large input sizes, it accurately solves the problem for moderately sized arrays.
- Diet Plan Performance:
To tackle the problem of evaluating a diet plan's performance based on calorie intake over a specified number of days (k), we can efficiently utilize the "sliding window" technique. This method is ideal for analyzing consecutive subarrays of a fixed size.
Approach Using Sliding Window Technique
Understanding the Problem: You need to calculate the score based on sums of contiguous subarrays of size k from the given array of calories. The score changes based on how these sums compare to predefined lower and upper limits.
Sliding Window Technique:
Compute the sum of the first k days to initialize the first window.
Slide the window across the calories array by adding the next day's calories and subtracting the first day's calories from the previous window.
Adjust the score based on how the sum of calories in the current window compares to the lower and upper limits.
Implementation Steps:
Initialize the score and the first window's sum.
For each new position of the window, update the sum and adjust the score based on the sum's relation to the lower and upper limits.
Return the final score.
Implementation
#include <stdio.h>
int dietPlanPerformance(int calories[], int n, int k, int lower, int upper) {
int score = 0;
int currentSum = 0;
for (int i = 0; i < k; i++) {
currentSum += calories[i];
}
if (currentSum < lower) score--;
else if (currentSum > upper) score++;
for (int i = k; i < n; i++) {
currentSum += calories[i] - calories[i - k];
if (currentSum < lower) score--;
else if (currentSum > upper) score++;
}
return score;
}
int main() {
int calories[] = {1, 2, 3, 4, 5};
int k = 3, lower = 5, upper = 10;
int n = sizeof(calories) / sizeof(calories[0]);
int result = dietPlanPerformance(calories, n, k, lower, upper);
printf("Final score of the diet plan: %d\n", result);
return 0;
}
Example and Explanation
Let's take the example {1, 2, 3, 4, 5} with k = 3, lower = 5, and upper = 10.
Initial Setup:
- Compute the sum of the first
k elements.
Array: [1, 2, 3, 4, 5]
Initial window: [1, 2, 3]
Sum = 6
Evaluate and Slide:
After initial sum:
Score = 0 (6 is between 5 and 10)
First slide:
Array: [1, 2, 3, 4, 5]
Old window: [1, 2, 3], New window: [2, 3, 4]
Updated sum = 9 (remove 1, add 4)
Score remains 0 (9 is still between 5 and 10)
Second slide:
Array: [1, 2, 3, 4, 5]
Old window: [2, 3, 4], New window: [3, 4, 5]
Updated sum = 12 (remove 2, add 5)
Score increments by 1 (12 is above 10)
Final Score Calculation:
- The score adjusts through subsequent window evaluations.
Final score:
Score = 0 (the initial increment from the last window is balanced by earlier evaluations)
This approach ensures efficient computation of the diet plan score, maintaining optimal time complexity using the sliding window technique. Each window transition only requires constant time since it updates the sum with only two operations: subtracting the outgoing element and adding the incoming one.
- Pair with Target Sum:
To solve the problem of finding a pair in a sorted array that adds up to a specific target sum, you can effectively use the two-pointer technique. This approach takes advantage of the sorted nature of the array to adjust pointers based on the sum of the elements they point to.
Approach using Two Pointer Technique
Understanding the Problem: Given a sorted array, find two numbers such that they add up to a specific target.
Two Pointer Technique:
Place one pointer at the beginning (left) and another at the end (right) of the array.
If the sum of the elements at these pointers is equal to the target sum, you've found your pair.
If the sum is less than the target, move the left pointer to the right to increase the sum.
If the sum is more than the target, move the right pointer to the left to decrease the sum.
Continue this until the pointers meet.
Implementation Steps:
Initialize two pointers, one at the start and one at the end of the array.
Loop through the array while left pointer is less than right pointer.
Adjust pointers based on the comparison of their sum to the target.
Implementation
#include <stdio.h>
void findPairWithSum(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left < right) {
int currentSum = arr[left] + arr[right];
if (currentSum == target) {
printf("Pair found at indices %d and %d: (%d, %d)\n", left, right, arr[left], arr[right]);
return;
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
printf("No pair found that adds up to the target sum.\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 6};
int target = 6;
int n = sizeof(arr) / sizeof(arr[0]);
findPairWithSum(arr, n, target);
return 0;
}
Example and Explanation
Given the array {1, 2, 3, 4, 6} with the target sum 6:
Initial Setup:
- Place two pointers,
left at the start and right at the end of the array.
Array: [1, 2, 3, 4, 6]
^ ^
left right
Evaluate Sum and Adjust Pointers:
- Calculate the sum of elements at
left and right.
First check:
Sum = 1 + 6 = 7 (greater than 6, so decrease the sum by moving the right pointer left)
Second check:
Array: [1, 2, 3, 4, 6]
^ ^
left right
Sum = 1 + 4 = 5 (less than 6, so increase the sum by moving the left pointer right)
Find the Pair:
- Continue adjusting the pointers until the pair that adds up to the target is found.
Third check:
Array: [1, 2, 3, 4, 6]
^ ^
left right
Sum = 2 + 4 = 6 (equals target, pair found)
The output in this scenario would be the indices 1 and 3, which correspond to the elements 2 and 4 in the array that sum up to 6. This solution efficiently finds the required pair with a time complexity of (O(n)), making it very effective for sorted arrays.
- Remove Duplicates from Sorted Array:
To solve the problem of removing duplicates from a sorted array without using additional space, we can utilize the two-pointer technique. This technique involves using one pointer for iterating through the array and another pointer to store the position of the last unique element found.
Approach using Two Pointer Technique
Understanding the Problem: Since the array is already sorted, duplicate elements will be adjacent. The goal is to modify the array in-place to remove duplicates and return the new length.
Two Pointer Technique:
Use one pointer (i) to explore the array from the first to the last element.
Use another pointer (uniqueIndex) to keep track of the last position where a unique number was placed.
Compare each element pointed by i with the last unique element, and if they are different, update the position of uniqueIndex and copy the new unique element there.
Implementation Steps:
Start with the uniqueIndex pointer at the first element since the first element is always unique.
Incrementally move through the array with the i pointer, starting from the second element.
If a new unique element is found (different from the one at uniqueIndex), increment uniqueIndex and update that position with the new element.
Implementation
#include <stdio.h>
int removeDuplicates(int arr[], int n) {
if (n == 0) return 0;
int uniqueIndex = 0;
for (int i = 1; i < n; i++) {
if (arr[i] != arr[uniqueIndex]) {
uniqueIndex++;
arr[uniqueIndex] = arr[i];
}
}
return uniqueIndex + 1;
}
int main() {
int arr[] = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int newLength = removeDuplicates(arr, n);
printf("New length: %d\n", newLength);
printf("Modified array: ");
for (int i = 0; i < newLength; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Example and Explanation
Given the array {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}:
Initial Setup:
- The
uniqueIndex starts at the first element because it's always unique.
Array: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
^
uniqueIndex
Iterate with i Pointer:
- Move
i from the second element and compare each element with the one at uniqueIndex.
Initial Compare:
Array: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
^ ^
uniqueIndex i
After several iterations:
Array: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
^ ^
uniqueIndex i
Final Array State:
- The first five elements of the array now contain all unique values.
Final Array:
Array: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
^
unique elements up to the new length
The output is 5, as the first five elements are unique, and this technique ensures that the space complexity remains (O(1)) since we modify the array in-place.
- Squaring a Sorted Array:
To solve the problem of squaring a sorted array and ensuring the result is also sorted, we can effectively utilize the two-pointer technique. This technique is especially useful because the input array can contain both negative and positive numbers, and while squaring these numbers, the order can change due to the nature of squaring negative numbers.
Approach Using Two Pointer Technique
Understanding the Problem: The goal is to transform the array by squaring each element and ensuring that the resulting array remains sorted. Negative numbers, when squared, can become larger than the squares of smaller positive numbers, complicating direct squaring and sorting.
Two Pointer Technique:
Place one pointer at the beginning of the array segment containing negative numbers and another pointer at the start of the positive numbers.
Compare the absolute values of the positions pointed to by the two pointers, square the smaller absolute value, and place it in the output array, starting from the end of the array moving backwards.
Move the pointers inward based on which side was squared and placed in the output array.
Implementation Steps:
Identify the split point between negative and non-negative numbers.
Use two pointers to track the largest absolute values in the negative and positive segments.
Square the numbers and place them into the result array from the highest index down to zero.
Implementation
#include <stdio.h>
#include <stdlib.h> // For abs() function
void squareAndSortArray(int arr[], int n, int result[]) {
int left = 0;
int right = n - 1;
int index = n - 1;
while (left <= right) {
if (abs(arr[left]) > abs(arr[right])) {
result[index] = arr[left] * arr[left];
left++;
} else {
result[index] = arr[right] * arr[right];
right--;
}
index--;
}
}
int main() {
int arr[] = {-4, -1, 0, 3, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int result[n];
squareAndSortArray(arr, n, result);
printf("Squared and sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}
Example and Explanation
Given the array {-4, -1, 0, 3, 10}, we'll square each element and sort the result.
Initial Setup:
Array: [-4, -1, 0, 3, 10]
^ ^
left right
Processing Squares:
Compare the absolute values of the numbers at left and right.
Place the square of the larger absolute value in the result array, starting from the end.
First iteration (comparing 4 and 10):
Result: [ , , , , 100]
Second iteration (comparing 4 and 3):
Result: [ , , , 16, 100]
Continue:
- Continue the process, filling the result array from the highest index to zero.
Continued iterations fill in:
Result: [0, 1, 9, 16, 100]
The resulting array is {0, 1, 9, 16, 100}, which is correctly sorted. This method uses O(1) additional space (excluding the output array) and O(n) time complexity, making it highly efficient for the given problem.
- Backspace String Compare:
To solve the problem of comparing two strings accounting for backspace characters (#), where # represents a backspace operation, we can efficiently use the two-pointer technique from the end of each string towards the beginning. This approach allows us to process each string from back to front, skipping characters that have been "backspaced".
Approach Using Two Pointer Technique
Understanding the Problem: Given two strings, simulate the typing of each string into a text editor where # signifies a backspace. The challenge is to determine if the resultant text of both strings is identical.
Two Pointer Technique:
Use two pointers, one for each string, starting at the end of the strings.
Move each pointer backwards, accounting for backspaces (#).
Compare the next valid character of both strings at each step.
Handle cases where multiple backspaces occur consecutively.
Implementation Steps:
Initialize pointers at the ends of both strings.
Use a loop to traverse both strings from the end to the start.
Use helper counters to manage the number of backspaces encountered.
Compare characters only when both are not supposed to be backspaced.
Implementation
#include <stdio.h>
#include <string.h>
int getNextValidCharIndex(const char *str, int index) {
int backspaceCount = 0;
while (index >= 0) {
if (str[index] == '#') {
backspaceCount++;
} else if (backspaceCount > 0) {
backspaceCount--;
} else {
break;
}
index--;
}
return index;
}
int backspaceCompare(const char *str1, const char *str2) {
int i = strlen(str1) - 1;
int j = strlen(str2) - 1;
while (i >= 0 || j >= 0) {
i = getNextValidCharIndex(str1, i);
j = getNextValidCharIndex(str2, j);
if (i < 0 && j < 0) {
return 1;
}
if (i < 0 || j < 0) {
return 0;
}
if (str1[i] != str2[j]) {
return 0;
}
i--;
j--;
}
return 1;
}
int main() {
const char *str1 = "ab#c";
const char *str2 = "ad#c";
if (backspaceCompare(str1, str2)) {
printf("true\n");
} else {
printf("false\n");
}
return 0;
}
Example and Explanation
Given the input strings str1 = "ab#c" and str2 = "ad#c":
Initial Setup:
- Place pointers at the end of both strings.
str1: "ab#c"
^
pointer
str2: "ad#c"
^
pointer
Processing Each String:
- Traverse each string from end to start, adjusting for
#.
Processing str1:
- 'c' is a valid character.
- Skip 'b' due to the '#' after it.
- 'a' is the next valid character.
Processing str2:
- 'c' is a valid character.
- Skip 'd' due to the '#' after it.
- 'a' is the next valid character.
Comparison:
- Both strings result in
"ac" after processing backspaces.
Final Strings After Processing:
str1 and str2 both equal to "ac"
The program correctly identifies that both strings are the same after accounting for backspaces. The two-pointer approach from the end of the strings makes it efficient by avoiding the need to build the resultant strings explicitly and instead compares them on the fly.
- Trapping Rain Water:
To solve the problem of calculating how much water can be trapped between bars in an elevation map, an efficient approach involves using the two-pointer technique. This method is well-suited for the problem because it allows simultaneous assessment from both ends of the array, maximizing the amount of water trapped based on the encountered bar heights.
Approach Using Two Pointer Technique
Understanding the Problem: The objective is to calculate the total volume of water that can be trapped within the given height of bars after rainfall, where each bar has a width of 1 unit.
Two Pointer Technique:
Initialize two pointers, one at the start (left) and one at the end (right) of the array.
Use two variables to keep track of the maximum height encountered from the left (left_max) and from the right (right_max).
Move the pointer with the lower maximum height towards the center, updating the maximum heights and calculating trapped water as you go.
Implementation Steps:
Compare height[left] and height[right].
If height[left] is less than height[right], compute potential trapped water at left, update left_max and move left pointer to the right.
Otherwise, compute trapped water at right, update right_max, and move right pointer to the left.
Continue this until the two pointers meet in the middle.
Implementation
#include <stdio.h>
int trap(int height[], int n) {
int left = 0, right = n - 1;
int left_max = 0, right_max = 0;
int water_trapped = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
} else {
water_trapped += left_max - height[left];
}
left++;
} else {
if (height[right] >= right_max) {
right_max = height[right];
} else {
water_trapped += right_max - height[right];
}
right--;
}
}
return water_trapped;
}
int main() {
int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int n = sizeof(height) / sizeof(height[0]);
int result = trap(height, n);
printf("Total trapped rain water is %d units.\n", result);
return 0;
}
Example and Explanation
Given the input array {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}:
Initial Setup:
left points to the first element, right points to the last element.
Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
^ ^
left right
Process Trapping Water:
- Move
left and right pointers towards each other based on the comparison of height[left] and height[right].
First few steps:
- left_max = 0, right_max = 0 initially.
- height[0] < height[11], move `left` to right. `left_max` is still 0, no water trapped.
- height[1] > height[11], now move `right` to left. `right_max` = 1, calculate trapped water at position 11 if any.
...
Continue Until Pointers Meet:
- Compute trapped water based on the current
left_max and right_max.
Trapped water calculations:
- At each step, trapped water at a position is the minimum of `left_max` and `right_max` minus the current height.
...
Final trapped water volume is 6 units.
The output is 6 units of trapped water, and the two-pointer approach efficiently calculates this with a single pass through the array, making the time complexity (O(n)). This method avoids the need for auxiliary space, except for a few variables to track the maximum heights and pointers.
- Find the Maximum and Minimum Number in an Array:
To solve the problem of finding the maximum and minimum numbers in an array using a divide and conquer approach, we will recursively split the array into two halves until each subarray contains only one or two elements. This method resembles the merge sort algorithm in its division phase but instead of sorting, it focuses on finding and comparing extremes.
Approach Using Divide and Conquer
Understanding the Problem: The task is to find both the maximum and minimum elements in an array without scanning through it linearly. Instead, using a recursive method that divides the array into smaller parts, finds maxima and minima in these parts, and combines results.
Divide and Conquer Technique:
Divide: Split the array into two halves.
Conquer: Recursively find the maximum and minimum in each half.
Combine: Compare the results from the two halves to determine the overall maximum and minimum.
Implementation Steps:
If the array has only one element, return it as both max and min.
If the array has two elements, directly compare them to determine the max and min.
For larger arrays, split the array into two, recursively find max and min for both halves, and then determine the global max and min by comparing the results from both halves.
Implementation
#include <stdio.h>
typedef struct {
int max;
int min;
} MinMax;
MinMax getMaxMin(int arr[], int low, int high) {
MinMax result, leftResult, rightResult;
if (low == high) {
result.max = result.min = arr[low];
return result;
}
if (high == low + 1) {
if (arr[low] > arr[high]) {
result.max = arr[low];
result.min = arr[high];
} else {
result.max = arr[high];
result.min = arr[low];
}
return result;
}
int mid = (low + high) / 2;
leftResult = getMaxMin(arr, low, mid);
rightResult = getMaxMin(arr, mid + 1, high);
result.max = (leftResult.max > rightResult.max) ? leftResult.max : rightResult.max;
result.min = (leftResult.min < rightResult.min) ? leftResult.min : rightResult.min;
return result;
}
int main() {
int arr[] = {3, 5, 1, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
MinMax result = getMaxMin(arr, 0, n - 1);
printf("Max = %d, Min = %d\n", result.max, result.min);
return 0;
}
Example and Explanation
Initial Array:
- Divide the array into two halves:
{3, 5, 1} and {8, 4, 2}.
Array: [3, 5, 1, 8, 4, 2]
-----------------
Divide
/ \
[3, 5, 1] [8, 4, 2]
Recursive Division:
- Further split each half until each subarray has one or two elements, then determine max and min in each.
Further Division:
[3, 5, 1]
/ \
[3, 5] [1] -> Min = 1, Max = 1
[8, 4, 2]
/ \
[8, 4] [2] -> Min = 2, Max = 2
... and so on, until all parts are compared
Combine Results:
- Compare results of two halves to find the global maximum and minimum.
Combine Results:
Max of [3, 5, 1] is 5, Min is 1
Max of [8, 4, 2] is 8, Min is 2
Global Max = 8, Global Min = 1
The final output from this example is Max = 8, Min = 1, achieved by recursively comparing subarrays. This approach effectively uses the divide and conquer strategy to solve the problem efficiently and elegantly.
- All Permutations of an Array:
Generating all permutations of an array is a classic problem that can be elegantly solved using a recursive backtracking approach. This technique allows us to construct permutations by making a sequence of choices, where for each choice, we explore all further choices through recursion. If the permutation isn't complete or doesn't satisfy the condition, we undo the last choice (backtrack) and try the next option.
Approach Using Backtracking
Understanding the Problem: The task is to generate all possible orders of elements in an array. This means that for each element in the array, it can be the starting point of a permutation.
Recursive Backtracking:
Fix one element at a time to the first position, and recursively handle the rest of the array.
Once an element is fixed in the first position, swap it back to its original position after the recursive call (this is the backtracking step).
Continue this for each element in the array to generate all possible permutations.
Implementation Steps:
Start with the initial complete array and recursively swap each element with the current position.
After placing each element at the current position, recurse to fill the next position.
Once a permutation is printed/completed, swap the elements back to their original positions to restore the order and try the next possibility.
Implementation
#include <stdio.h>
void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
void printArray(int arr[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d", arr[i]);
if (i < n - 1) printf(", ");
}
printf("], ");
}
void permute(int arr[], int start, int n) {
if (start == n) {
printArray(arr, n);
return;
}
for (int i = start; i < n; i++) {
swap(&arr[start], &arr[i]);
permute(arr, start + 1, n);
swap(&arr[start], &arr[i]);
}
}
int main() {
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("All permutations of the array are: \n");
permute(arr, 0, n);
return 0;
}
Example and Explanation
Given the input array {1, 2, 3}:
Initial Call:
- Start by swapping each element with itself and then with every other element.
Initial array: [1, 2, 3]
Recursive Exploration:
Fix the first element and permute the rest:
Swap 1 with 1 (fix 1), then permute [2, 3].
Permutations with 1 fixed:
[1, 2, 3]
[1, 3, 2]
Further Recursion and Backtracking:
Backtrack to the original array configuration after each complete permutation and move to the next element:
Swap 1 with 2 and 3 in subsequent recursive calls and explore all permutations for each configuration.
After backtracking to [1, 2, 3], swap and fix next:
[2, 1, 3]
[2, 3, 1]
... and so on for `3`:
[3, 2, 1]
[3, 1, 2]
Completion:
- Each recursion depth handles one position in the array, fixing it and then moving on to permute the rest. Backtracking ensures elements are swapped back, allowing for the exploration of new permutations.
This recursive and backtracking approach allows us to generate all permutations by continually swapping elements, exploring further permutations, and then undoing the swaps to try different sequences, effectively covering all possible combinations of the array elements.
- Combination Sum:
To solve the problem of finding all unique combinations in an array that sum to a given target ( T ), where elements can be reused, a recursive backtracking approach is ideal. This method allows for exploring all possible combinations of numbers that add up to the target sum, backtracking whenever a combination either reaches or exceeds the target without a match.
Approach Using Recursive Backtracking
Understanding the Problem: We need to identify combinations within the array that sum up to ( T ). The numbers can be used repeatedly, and we must ensure no duplicate combinations are output.
Backtracking Technique:
Utilize a recursive function to explore every possible combination.
Use a temporary array (or dynamic list in higher-level languages) to hold the current combination.
If the current combination's sum equals ( T ), store or print this combination.
If the sum exceeds ( T ), terminate the exploration for that path.
Continue to add the next number in the array to the current combination and recurse.
After exploring with a number included, backtrack by removing it and trying the next number.
Implementation Steps:
Begin with the smallest numbers to build up combinations.
Use a recursive function to attempt to add each number to the current combination and recurse until the combination is valid or invalid.
Backtrack after each recursive call to try the next potential number.
Implementation
This C code uses dynamic memory allocation for simplicity in managing combinations. It tracks each combination using a temporary array that adjusts as the recursive function explores each possibility.
#include <stdio.h>
#include <stdlib.h>
void printCombination(int temp[], int tempSize) {
printf("[");
for (int i = 0; i < tempSize; i++) {
printf("%d", temp[i]);
if (i < tempSize - 1) printf(", ");
}
printf("]");
}
void findCombinations(int arr[], int n, int start, int target, int temp[], int tempSize) {
if (target == 0) {
printCombination(temp, tempSize);
printf(", ");
return;
}
for (int i = start; i < n; i++) {
if (target < arr[i]) continue;
temp[tempSize] = arr[i];
findCombinations(arr, n, i, target - arr[i], temp, tempSize + 1);
}
}
void combinationSum(int arr[], int n, int target) {
int *temp = malloc(target * sizeof(int));
printf("[");
findCombinations(arr, n, 0, target, temp, 0);
printf("]\n");
free(temp);
}
int main() {
int arr[] = {2, 3, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7;
printf("Combinations that sum to %d are:\n", target);
combinationSum(arr, n, target);
return 0;
}
Example and Explanation
Given the input array {2, 3, 6, 7} with target ( T = 7 ):
Initial Setup:
- Start from the first element in the array and try to build combinations.
Array: [2, 3, 6, 7]
Target: 7
Recursive Exploration:
- Start with 2, recursively try to add 2 again, and then 3, until a combination equals the target or exceeds it.
Starting combination:
Trying [2], remaining target = 5
-> [2, 2], remaining target = 3
-> [2, 2, 2], remaining target = 1 (exceeds any single element, backtrack)
-> [2, 2, 3], exact match, print [2, 2, 3]
Continue with Other Elements:
- After exploring all possibilities starting with 2, move to 3, then 6, then 7.
Trying [3], remaining target = 4
-> [3, 3], remaining target = 1 (no match, backtrack)
Trying [6], remaining target = 1 (no match, backtrack)
Trying [7], exact match, print [7]
Final Output:
- The valid combinations are:
[[2, 2, 3], [7]]
This solution efficiently finds all combinations using recursion and backtracking, ensuring that every possibility is explored while avoiding unnecessary calculations when the remaining target becomes too small.
- Distinct Permutations of an Array:
To generate all distinct permutations of an array that may contain duplicates, the backtracking approach can be optimized by first sorting the array. This helps to easily skip over duplicates when generating permutations. Using a boolean array to track which elements have been used in the current recursion level prevents reusing the same element in the same permutation position and avoids duplicates in the output.
Approach Using Backtracking and Sorting
Understanding the Problem: The objective is to generate permutations of an array containing duplicates such that no permutation is repeated.
Optimized Backtracking Technique:
Sort the Array: Begin by sorting the array to bring duplicates together. This makes it easier to skip duplicates during the permutation process.
Backtracking with State Tracking: Use a recursive function to generate permutations. Use a boolean array to mark elements that are included in the current permutation to avoid using the same element twice.
Skip Duplicates: When backtracking, skip over adjacent duplicate elements to ensure unique permutations.
Implementation Steps:
Sort the array.
Use a recursive function with an additional boolean array to track which elements are already used in the permutation being constructed.
At each recursive call, consider elements that are not yet used and are not duplicates of the previously considered element unless the duplicate was used in the previous step.
Implementation
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void printArray(int arr[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d", arr[i]);
if (i < n - 1) printf(", ");
}
printf("], ");
}
void permute(int arr[], int start, int n, int *used) {
if (start == n) {
printArray(arr, n);
return;
}
for (int i = start; i < n; i++) {
if (used[i] || (i > start && arr[i] == arr[i - 1] && !used[i - 1]))
continue;
used[i] = 1;
swap(&arr[start], &arr[i]);
permute(arr, start + 1, n, used);
swap(&arr[start], &arr[i]);
used[i] = 0;
}
}
void sortArray(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {1, 2, 2};
int n = sizeof(arr) / sizeof(arr[0]);
sortArray(arr, n);
int *used = calloc(n, sizeof(int));
printf("Distinct permutations are:\n[");
permute(arr, 0, n, used);
printf("]\n");
free(used);
return 0;
}
Example and Explanation
Given the sorted input array {1, 2, 2}:
Initial Setup:
The array is sorted: [1, 2, 2].
Use a boolean array [0, 0, 0] to track used elements.
Recursive Exploration:
- Start with the first element
1:
Fix 1:
[1, 2, 2]
- Then try with
2 from position 1 and skip the duplicate 2 from position 2 during this call:
Fix 2 (first occurrence):
[2, 1, 2]
Fix 2 (second occurrence):
[2, 2, 1]
Backtracking:
- Backtrack to try the next set of permutations, ensuring that duplicates are skipped if not used in the permutation set.
Backtrack after each completion to try next potential permutations.
The output of the program is Distinct permutations are: [[1, 2, 2], [2, 1, 2], [2, 2, 1], ], effectively listing all unique permutations while avoiding duplicates through careful management of element use and skipping. This approach ensures each permutation is unique by managing how elements are chosen and backtracked with the use of the used array and duplicate checks.
- Combinations Sum II:
To solve the "Combination Sum II" problem, where you must find all unique combinations in a given array that sum to a target number ( T ) with each number used only once, a combination of sorting, backtracking, and careful element choice is required to ensure unique solutions, especially given potential duplicates in the input.
Approach Using Recursive Backtracking and Sorting
Understanding the Problem: The aim is to find unique sets of numbers that sum to a target value. Numbers in the candidate list can be used at most once, and the candidate list might contain duplicates.
Strategy:
Sort the Array: Begin by sorting the array to bring duplicates together. This setup makes it easier to skip duplicates during the recursive process.
Backtracking with Constraints: Use a recursive function to build combinations. Add constraints to ensure that each number is used at most once, and skip subsequent duplicate numbers immediately following the number just used.
Skip Duplicates: When starting a new recursive call from a specific loop index, skip over adjacent elements that are duplicates of the current element to avoid repeating the same combination.
Implementation Steps:
Sort the array to handle duplicates effectively.
Use a recursive function to explore possible combinations, adding elements to a temporary list and recursively attempting to add further elements.
If a combination matches the target sum, add it to the result list.
After exploring with a number, backtrack by removing it from the current combination and proceed to the next number in the array, skipping duplicates.
Implementation
#include <stdio.h>
#include <stdlib.h>
void printArray(int arr[], int size) {
printf("[");
for (int i = 0; i < size; i++) {
printf("%d", arr[i]);
if (i < size - 1) printf(", ");
}
printf("]");
}
void findCombinations(int arr[], int n, int start, int target, int* combo, int comboSize, int** results, int* resultSize, int* colSizes) {
if (target == 0) {
results[*resultSize] = (int*) malloc(comboSize * sizeof(int));
for (int i = 0; i < comboSize; i++) {
results[*resultSize][i] = combo[i];
}
colSizes[*resultSize] = comboSize;
(*resultSize)++;
return;
}
for (int i = start; i < n; i++) {
if (i > start && arr[i] == arr[i - 1]) continue;
if (arr[i] > target) break;
combo[comboSize] = arr[i];
findCombinations(arr, n, i + 1, target - arr[i], combo, comboSize + 1, results, resultSize, colSizes);
}
}
void sortArray(int* arr, int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
int main() {
int arr[] = {10, 1, 2, 7, 6, 1, 5};
int target = 8;
int n = sizeof(arr) / sizeof(arr[0]);
sortArray(arr, n);
int* combo = (int*) malloc(target * sizeof(int));
int** results = (int**) malloc(100 * sizeof(int*));
int* colSizes = (int*) malloc(100 * sizeof(int));
int resultSize = 0;
findCombinations(arr, n, 0, target, combo, 0, results, &resultSize, colSizes);
printf("Unique combinations are: [");
for (int i = 0; i < resultSize; i++) {
printArray(results[i], colSizes[i]);
if (i < resultSize - 1) printf(", ");
}
printf("]\n");
for (int i = 0; i < resultSize; i++) free(results[i]);
free(results);
free(colSizes);
free(combo);
return 0;
}
Example and Explanation
Given the sorted input array [1, 1, 2, 5, 6, 7, 10] and a target of 8:
Initial Setup:
The array is first sorted to [1, 1, 2, 5, 6, 7, 10].
Begin searching for combinations starting from index 0.
Recursive Exploration:
Start with the first 1 and attempt to build up to 8.
Continue exploring deeper with subsequent elements, skipping over the second 1 when the first has been included.
Skipping Duplicates:
- When encountering the second
1, skip it if the first 1 was used, preventing duplicate combinations like [1, 1, 6] and [1, 1, 6] repeated.
Successful Combinations:
- The combinations that meet the target are:
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]].
This solution efficiently ensures that each combination is unique and meets the target, utilizing sorting and careful handling of duplicates during the recursive process.