November 26, 2021 – My Programming Notes

Daily Archives: November 26, 2021

C# || How To Search In Rotated Sorted Array Using C#

November 26, 2021 admin No comments

The following is a module with functions which demonstrates how to search for a target value in a rotated sorted array using C#.

1. Search – Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Example 3:

Input: nums = [1], target = 0 Output: -1

2. Search – Solution

The following is a solution which demonstrates how to search for a target value in a rotated sorted array.

The idea of this solution is to use binary search, and for each loop iteration we compare the midpoint element with the right side of the array to determine the search area of where the target element might be.





		
		
			2. Search - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to search for a target in a rotated array
// ============================================================================
public class Solution {
    public int Search(int[] nums, int target) {
        var lo = 0;
        var hi = nums.Length - 1;

        while (lo <= hi) {
            var mid = lo + (hi - lo) / 2;

            // Target element found
            if (nums[mid] == target) {
                return mid;

            // Midpoint element is greater than right side of array
            } else if (nums[mid] > nums[hi]) {
                // Determine which side of array to adjust
                if (target < nums[mid] && target >= nums[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }

            // Midpoint element is less than right side of array
            } else {
                // Determine which side of array to adjust
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to search for a target in a rotated array
// ============================================================================
public class Solution {
    public int Search(int[] nums, int target) {
        var lo = 0;
        var hi = nums.Length - 1;
 
        while (lo <= hi) {
            var mid = lo + (hi - lo) / 2;
 
            // Target element found
            if (nums[mid] == target) {
                return mid;
 
            // Midpoint element is greater than right side of array
            } else if (nums[mid] > nums[hi]) {
                // Determine which side of array to adjust
                if (target < nums[mid] && target >= nums[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
 
            // Midpoint element is less than right side of array
            } else {
                // Determine which side of array to adjust
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

4 -1 -1

C# || How To Find Product Of Array Except Self Using C#

November 26, 2021 admin No comments

The following is a module with functions which demonstrates how to find the product of an array except itself using C#.

1. Product Except Self – Problem Statement

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

2. Product Except Self – Solution

The following is a solution which demonstrates how to find the product of an array except itself.

In this solution, the product for result[i] is calculated by scanning the input array, and multiplying the numbers that come before the current i, and the numbers that come after the current i.

First, the running product of the numbers that come before the current i is calculated by scanning the array starting from the beginning (prefix).

Then, the running product of the numbers that come after the current i is calculated by scanning the array starting from the end (suffix).





		
		
			2. Product Except Self - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find product of array except self
// ============================================================================
public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        var result = new int[nums.Length];

        // Prefix
        var runningPrefix = 1;
        for (int index = 0; index < nums.Length; ++index) {
            result[index] = runningPrefix;
            runningPrefix *= nums[index];
        }

        // Suffix
        var runningSufix = 1;
        for (int index = nums.Length - 1; index >= 0; --index) {
            result[index] *= runningSufix;
            runningSufix *= nums[index];
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find product of array except self
// ============================================================================
public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        var result = new int[nums.Length];
 
        // Prefix
        var runningPrefix = 1;
        for (int index = 0; index < nums.Length; ++index) {
            result[index] = runningPrefix;
            runningPrefix *= nums[index];
        }
 
        // Suffix
        var runningSufix = 1;
        for (int index = nums.Length - 1; index >= 0; --index) {
            result[index] *= runningSufix;
            runningSufix *= nums[index];
        }
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[24,12,8,6] [0,0,9,0,0]

Daily Archives: November 26, 2021

C# || How To Search In Rotated Sorted Array Using C#

C# || How To Find Product Of Array Except Self Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories