Rotate image (square matrix) by 90 deg
Tue, 06 May 2025
Array k Output
--------------------- ------ --------------
{2, 4, 17, 9, 6, 3} 18 FOUND. arr[3] thru arr[5]
{1, 0, 4, 0, 2} 7 FOUND. arr[0] thru arr[4]
{1, 0, 4, 0, 2} 3 NOT FOUND.
Solution:
Method-1: Bruite-Force (Consider all sub arrays)
Algorithm:
Consider all subarrays one by one.
If the sum = k
print the indexes and return TRUE
else
return FALSE
Code:
/* Print the Indexes of the sub array and return true if founds
* a continuous sub-array with sum = k
* else returns false.
* Parameters: arr, n - Array and size of array.
*/
int findSubArray(int *arr, int n, int k)
{
// Loop will check for sub-array starting at i.
for (int i = 0; i<n; i++)
{
int sum = 0;
for (int j = i; j < n; j++)
{
sum = sum + arr[j];
if (sum == k){
printf ("FOUND: %d - %d", i, j);
return true;
}
// Don't need to check further if sum > k..
// because array does not have -ve integers
if (sum > k)
break;
}
}
printf("NOT FOUND");
return false;
}
Time complexity: O(n2) (There are n sub-arrays with 1, 2, 3, ... n. elements and we are considering all of them)
Method-2: Using Single Iteration Algorithm:Let 'sum' Indicate the sum of sub-array under consideration.
sum = arr[0]
FOR i= 1 TO n-1
IF sum IS EQUAL TO k
FOUND the sub array, print the indexes and return.
IF sum IS GREATER THAN k
remove the initial elements from SUM until it becomes < k
Print NOT FOUND
Code:
/* Print the Indexes of the sub array and return true if founds
* a continuous sub-array with sum = k
* else returns false.
* Parameters: arr, n - Array and size of array.
*/
int findSubArray(int *arr, int n, int k)
{
int sum = 0;
int startIdx = 0; // Represent the Start Index of sub-array
for (int i = 0; i <= n; i++)
{
sum = sum + arr[i];
// If curr_sum becomes equal to sum, then return true
if (sum == k)
{
printf ("FOUND: %d - %d", startIdx, i-1);
return true;
}
while (sum > k && startIdx < i)
{
sum = sum - arr[startIdx];
startIdx++;
}
}
printf("NOT FOUND");
return false;
}
Time complexity: O(n)
Please let me know your comments / feedback / suggestions.
Tue, 06 May 2025
Tue, 06 May 2025
Tue, 06 May 2025
Leave a comment