HOMEWORK DAY: 10
13 September 2023 17:21
https://www.linkedin.com/in/manojoffcialmj/
1. Re-arrange array elements (Leetcode-2149)
2. Find pivot element (Leetcode-724)
Example 1: Example 2:
Input: nums = [1,7,3,6,5,6] Input: nums = [1,2,3]
Output: 3 Output: -1
Explanation: Explanation:
The pivot index is 3. There is no index that satisfies the conditions in the
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 problem statement.
Right sum = nums[4] + nums[5] = 5 + 6 = 11
Example 1:
APPROACH PSEUDO CODE:
Step 01: find total sum of array as right sum
Step 02: subtract element one by one from right sum until left sum is equal to right sum
Step 03: return the index which terminate the loop
3. Find Duplicate Number (Leetcode-287)
Example 1: Example 3:
Input: nums = [1,3,4,2,2] Input: nums = [2,2,2,2,2]
Output: 2 Output: 2
Example 2: Example 4:
Input: nums = [3,1,3,4,2] Input: nums = [1,2,3,4]
Output: 3 Output: -1
APPROACH:
Method 01: Sorting approach
Method 02: Negative marking approach
Method 03: Position and swapping approach
Method 01: Sorting approach
Step 01: Sort the array
Step 01: Iterate the array
Step 02: Mark visited
Step 03: Already visited position then return duplicate
Iteration 0
Iteration 1
Iteration 2
Iteration 3
Method 03: Position and swapping approach (Position index==Element)
4. Missing Element From An Array With Duplicates (GFG)
Problem: Given an array arr[] of size N having integers in the range [1, N] with some of the elements missing.
The task is to find the missing elements.
Note: There can be duplicates in the array.
EXAMPLE 01: EXAMPLE 02: EXAMPLE 03:
Input: arr[] = {1, 3, 5, 3, 4}, N = 5 Input: arr[] = {1, 3, 3, 3, 5}, N = 5 Input: arr[] = {1, 2, 3, 4, 4, 7, 7}, N = 7
Output: 2 Output: 2 4 Output: 5 6
Approach:
- Negative marking approach
- Sorting approach
1. Negative marking approach
Step 01: Apply Visited Method
Step 02: All positive index are missing
Step 01: Apply Visited Method
Iteration:0
Iteration:1
Iteration:2
Iteration:3
Iteration:4
Brute force approach
Optimal approach with hashing technique
Step 01: Traverse array and store it's element as hashing
Step 02: Traverse array to check each element if it has occurrence in future
Hashing: We can use unordered map to store array's element in pair of key and value
Declaration of unordered map
Read more from this resource: https://www.geeksforgeeks.org/unordered_map-in-cpp-stl
6. Common Element in 3 Sorted Array (GFG)
Example 01: Example 02:
Input: Input:
n1 = 6; A = {1, 5, 10, 20, 40, 80} n1 = 3; A = {3, 3, 3}
n2 = 5; B = {6, 7, 20, 80, 100} n2 = 3; B = {3, 3, 3}
n3 = 8; C = {3, 4, 15, 20, 30, 70, 80, 120} n3 = 3; C = {3, 3, 3}
Output: 20 80 Output: 3
Optimal Approach:
Step 01: remove duplicates from sorted array
Step 02: store common value of all three arrays in new array
Step 01: store unique element in new array with the help of C++ STL Data Structure is set(dataType)
Declaration of set
Read more from this resource: https://www.geeksforgeeks.org/set-in-cpp-stl/
Step 02: store common value of all three arrays in new array
7. Wave Print A Matrix (GFG)
Approach:
- When number of column is even then print row top to bottom
- When number of column is odd then print row bottom to top
8. Spiral Print A Matrix (Leetcode-54)
Output:
1 2 3 4 5 6 12 18 24 30 29 28 27 26 25
19 13 7 8 9 10 11 17 23 22 21 14 15 16
startingRow = 0 startingRow = 1 startingRow = 2
endingCol = 5 endingCol = 4 endingCol = 3
endingRow = 4 endingRow = 3 endingRow = 2
startingCol = 0 startingCol = 1 startingCol = 2
Optimal Approach:
Step 01: find total elements
Step 02: iterate matrix till end of the total element and print
- Print startingRow
- Print endingCol
- Print endingRow
- Print startingCol
15. Add two numbers represented by two array (GFG)
Example 01: Example 03:
Input : A[] = {1, 2}, B[] = {2, 1} Input : A[] = {2, 1, 4}, B[] = {9, 5, 4, 9}
Output : 33 Output : 9763
Example 02: Example 04:
Input : A[] = {9, 5, 4, 9}, B[] = {2, 1, 4} Input : A[] = {9, 1, 4}, B[] = {8, 1, 4}
Output : 9763 Output : 1728
Example 05:
Input : A[] = {0, 0, 2, 1, 4}, B[] = {0, 0, 2, 1, 4}
Output : 428
Example 02:
Iteration 0
Iteration 1
Iteration 2
Iteration 1
Iteration 2
Iteration 3
Iteration 4
9. Factorial of A Large Number (GFG)
Example 01: Example 02:
Enter number: 5 Enter number: 100
120 93326215443944152681699238856266700490715968264381621
4685929638952175999932299156089414639761565182862536
Example 01: Example 02:
Enter number: 5 Enter number: 100
120 93326215443944152681699238856266700490715968264381621
4685929638952175999932299156089414639761565182862536
97920827223758251185210916864000000000000000000000000
