SkylineWebZ

Problem Statement: You are given two binary strings, a and b. Each string represents a non-negative integer, where each character is either ‘0’ or ‘1’. You need to return their sum, also as a binary string. Example: Input:a = “1010” b = “1011”Output:”10101″ Approach: The problem can be solved by simulating the binary addition process, similar to how we add numbers by hand. We’ll start adding from the rightmost bit (the least significant bit) and move leftwards. We need to keep track of the carry that might result from the addition of two bits. Steps: Algorithm: Time Complexity: The time complexity is O(max(n, m)), where n and m are the lengths of the two binary strings a and b. We go through both strings at most once. Space Complexity: The space complexity is O(max(n, m)) due to the space used to store the result string. Code Implementations 1. C #include <stdio.h>#include <string.h>#include <stdlib.h>char* addBinary(char* a, char* b) { int i = strlen(a) – 1, j = strlen(b) – 1, carry = 0; int size = (i > j ? i : j) + 2; // Maximum length needed char* result = (char*)malloc(sizeof(char) * (size + 1)); int k = 0; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result[k++] = (sum % 2) + ‘0’; carry = sum / 2; } result[k] = ‘\0’; // Reverse the result string for (int start = 0, end = k – 1; start < end; start++, end–) { char temp = result[start]; result[start] = result[end]; result[end] = temp; } return result;}int main() { char a[] = “1010”, b[] = “1011”; char* result = addBinary(a, b); printf(“Sum: %s\n”, result); free(result); return 0;} 2. C++ #include <iostream>#include <string>using namespace std;string addBinary(string a, string b) { int i = a.length() – 1, j = b.length() – 1, carry = 0; string result = “”; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result = char(sum % 2 + ‘0’) + result; carry = sum / 2; } return result;}int main() { string a = “1010”, b = “1011”; cout << “Sum: ” << addBinary(a, b) << endl; return 0;} 3. Java public class Solution { public String addBinary(String a, String b) { int i = a.length() – 1, j = b.length() – 1, carry = 0; StringBuilder result = new StringBuilder(); while (i >= 0 || j >= 0 || carry != 0) { int sum = carry; if (i >= 0) sum += a.charAt(i–) – ‘0’; if (j >= 0) sum += b.charAt(j–) – ‘0’; result.append(sum % 2); carry = sum / 2; } return result.reverse().toString(); } public static void main(String[] args) { Solution sol = new Solution(); String a = “1010”, b = “1011”; System.out.println(“Sum: ” + sol.addBinary(a, b)); }} 4. Python def addBinary(a: str, b: str) -> str: i, j, carry = len(a) – 1, len(b) – 1, 0 result = [] while i >= 0 or j >= 0 or carry: sum = carry if i >= 0: sum += int(a[i]) i -= 1 if j >= 0: sum += int(b[j]) j -= 1 result.append(str(sum % 2)) carry = sum // 2 return ”.join(reversed(result))# Testa = “1010”b = “1011”print(“Sum:”, addBinary(a, b)) 5. C# using System;using System.Text;class Solution { public string AddBinary(string a, string b) { int i = a.Length – 1, j = b.Length – 1, carry = 0; StringBuilder result = new StringBuilder(); while (i >= 0 || j >= 0 || carry != 0) { int sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result.Append(sum % 2); carry = sum / 2; } char[] resultArr = result.ToString().ToCharArray(); Array.Reverse(resultArr); return new string(resultArr); } public static void Main() { Solution sol = new Solution(); string a = “1010”, b = “1011”; Console.WriteLine(“Sum: ” + sol.AddBinary(a, b)); }} 6. JavaScript function addBinary(a, b) { let i = a.length – 1, j = b.length – 1, carry = 0; let result = []; while (i >= 0 || j >= 0 || carry) { let sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result.push(sum % 2); carry = Math.floor(sum / 2); } return result.reverse().join(”);}// Testlet a = “1010”, b = “1011”;console.log(“Sum:”, addBinary(a, b)); Summary:

Problem Statement: Given a string, determine if it represents a valid number. A valid number can be any of the following: The string may contain leading or trailing whitespace characters, and may include a decimal point and an exponent (denoted by e or E). Input: Output: Example 1: Input: “123”Output: true Example 2: Input: “3.14159”Output: true Example 3: Input: “1e10″Output: true Example 4: Input: “abc”Output: false Example 5: Input: “1e”Output: false Approach: The problem can be solved using state machine or regular expressions. The state machine is preferred here due to better control over transitions. Steps: Time Complexity: Code Implementation: 1. C: #include <stdio.h>#include <ctype.h>#include <stdbool.h>bool isNumber(char* s) { if (s == NULL) return false; int i = 0, n = 0; // Trim leading whitespace while (s[i] == ‘ ‘) i++; // Handle optional sign if (s[i] == ‘+’ || s[i] == ‘-‘) i++; bool numSeen = false, dotSeen = false, eSeen = false; // Process each character while (s[i] != ‘\0’) { if (isdigit(s[i])) { numSeen = true; } else if (s[i] == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (s[i] == ‘e’ || s[i] == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (s[i] == ‘+’ || s[i] == ‘-‘) { if (s[i – 1] != ‘e’ && s[i – 1] != ‘E’) return false; } else { return false; // Invalid character } i++; } return numSeen;}int main() { char s[] = “3.14159”; if (isNumber(s)) { printf(“Valid Number\n”); } else { printf(“Invalid Number\n”); } return 0;} 2. C++: #include <iostream>#include <string>#include <cctype>using namespace std;bool isNumber(string s) { int i = 0, n = s.length(); // Trim leading spaces while (i < n && s[i] == ‘ ‘) i++; if (i == n) return false; bool numSeen = false, dotSeen = false, eSeen = false; // Check each character while (i < n) { if (isdigit(s[i])) { numSeen = true; } else if (s[i] == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (s[i] == ‘e’ || s[i] == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (s[i] == ‘+’ || s[i] == ‘-‘) { if (s[i – 1] != ‘e’ && s[i – 1] != ‘E’) return false; } else { return false; } i++; } return numSeen;}int main() { string s = “3.14”; if (isNumber(s)) { cout << “Valid Number” << endl; } else { cout << “Invalid Number” << endl; } return 0;} 3. Java: public class ValidNumber { public static boolean isNumber(String s) { s = s.trim(); int n = s.length(); if (n == 0) return false; boolean numSeen = false, dotSeen = false, eSeen = false; for (int i = 0; i < n; i++) { char c = s.charAt(i); if (Character.isDigit(c)) { numSeen = true; } else if (c == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (c == ‘e’ || c == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (c == ‘+’ || c == ‘-‘) { if (i > 0 && s.charAt(i – 1) != ‘e’ && s.charAt(i – 1) != ‘E’) return false; } else { return false; } } return numSeen; } public static void main(String[] args) { String s = “3.14”; System.out.println(isNumber(s) ? “Valid Number” : “Invalid Number”); }} 4. Python: def isNumber(s: str) -> bool: s = s.strip() if not s: return False num_seen, dot_seen, e_seen = False, False, False for i in range(len(s)): char = s[i] if char.isdigit(): num_seen = True elif char == ‘.’: if dot_seen or e_seen: return False dot_seen = True elif char == ‘e’ or char == ‘E’: if e_seen or not num_seen: return False e_seen = True num_seen = False # Reset numSeen after exponent elif char == ‘+’ or char == ‘-‘: if i > 0 and s[i-1] not in (‘e’, ‘E’): return False else: return False return num_seen# Example Usages = “3.14”print(“Valid Number” if isNumber(s) else “Invalid Number”) 5. C#: using System;public class Solution { public bool IsNumber(string s) { s = s.Trim(); if (string.IsNullOrEmpty(s)) return false; bool numSeen = false, dotSeen = false, eSeen = false; for (int i = 0; i < s.Length; i++) { char c = s[i]; if (Char.IsDigit(c)) { numSeen = true; } else if (c == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (c == ‘e’ || c == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (c == ‘+’ || c == ‘-‘) { if (i > 0 && s[i – 1] != ‘e’ && s[i – 1] != ‘E’) return false; } else { return false; } } return numSeen; } public static void Main() { Solution solution = new Solution(); string s = “3.14”; Console.WriteLine(solution.IsNumber(s) ? “Valid Number” : “Invalid Number”); }} 6. JavaScript: function isNumber(s) { s = s.trim(); if (s.length === 0) return false; let numSeen = false, dotSeen = false, eSeen = false; for (let i = 0; i < s.length; i++) { let char = s[i]; if (/\d/.test(char)) { numSeen = true; } else if (char === ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (char === ‘e’ || char === ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (char === ‘+’ || char === ‘-‘) { if (i > 0 && (s[i-1] !== ‘e’ && s[i-1] !== ‘E’)) return false; } else { return false; } } return numSeen;}// Example Usagelet s = “3.14”;console.log(isNumber(s) ? “Valid Number” : “Invalid Number”); Summary:

The “Length of Last Word“ problem is a classic problem often asked in coding interviews. The task is to determine the length of the last word in a given string. A word is defined as a sequence of non-space characters, and the words in the string are separated by spaces. Problem Statement: Given a string s, return the length of the last word in it. Example: Input: “Hello World” Output: 5 Explanation: The last word is “World”, and its length is 5. Input: arduinoCopy code” fly me to the moon ” Output: 4 Explanation: The last word is “moon”, and its length is 4. Input: “luffy is still joyboy” Output: 6 Explanation: The last word is “joyboy”, and its length is 6. Approach: We can solve this problem in two main ways: Solution Approach 1: Iteration from the end Solution Approach 2: Using built-in functions (trim, split) Code Implementations: 1. C++ #include <iostream>#include <string>#include <algorithm>using namespace std;int lengthOfLastWord(string s) { int n = s.length(); int length = 0; // Start from the end of the string int i = n – 1; // Skip trailing spaces while (i >= 0 && s[i] == ‘ ‘) { i–; } // Count the length of the last word while (i >= 0 && s[i] != ‘ ‘) { length++; i–; } return length;}int main() { string str = “Hello World”; cout << “Length of last word: ” << lengthOfLastWord(str) << endl; // Output: 5 return 0;} 2. C #include <stdio.h>#include <string.h>int lengthOfLastWord(char *s) { int len = strlen(s); int length = 0; // Skip trailing spaces while (len > 0 && s[len – 1] == ‘ ‘) { len–; } // Count the length of the last word while (len > 0 && s[len – 1] != ‘ ‘) { length++; len–; } return length;}int main() { char str[] = “Hello World”; printf(“Length of last word: %d\n”, lengthOfLastWord(str)); // Output: 5 return 0;} 3. Java public class LengthOfLastWord { public int lengthOfLastWord(String s) { int length = 0; int n = s.length(); // Skip trailing spaces int i = n – 1; while (i >= 0 && s.charAt(i) == ‘ ‘) { i–; } // Count the length of the last word while (i >= 0 && s.charAt(i) != ‘ ‘) { length++; i–; } return length; } public static void main(String[] args) { LengthOfLastWord solution = new LengthOfLastWord(); String str = “Hello World”; System.out.println(“Length of last word: ” + solution.lengthOfLastWord(str)); // Output: 5 }} 4. Python def lengthOfLastWord(s: str) -> int: s = s.strip() # Remove leading/trailing spaces words = s.split() # Split the string into words return len(words[-1]) # Return the length of the last word# Test the functionprint(lengthOfLastWord(“Hello World”)) # Output: 5 5. C# using System;public class Solution { public int LengthOfLastWord(string s) { s = s.Trim(); // Remove leading/trailing spaces string[] words = s.Split(); // Split the string into words return words[words.Length – 1].Length; // Return the length of the last word } public static void Main() { Solution solution = new Solution(); string str = “Hello World”; Console.WriteLine(solution.LengthOfLastWord(str)); // Output: 5 }} 6. JavaScript function lengthOfLastWord(s) { s = s.trim(); // Remove leading/trailing spaces const words = s.split(‘ ‘); // Split the string into words return words[words.length – 1].length; // Return the length of the last word}// Test the functionconsole.log(lengthOfLastWord(“Hello World”)); // Output: 5 Time Complexity: Space Complexity: Summary: The “Length of Last Word” problem can be solved using either an iterative approach from the end of the string or by trimming and splitting the string. Both approaches have a time complexity of O(n), but the iterative approach can be more space-efficient, using O(1) extra space.

The problem of Group Anagrams is a common algorithmic challenge that asks to group a list of strings such that each group consists of anagrams. Two words are considered anagrams if one can be formed by rearranging the letters of the other, i.e., they contain the same characters in the same frequency. Problem Statement: Given an array of strings, group the anagrams together. Input: Output: Example: Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] Output: [[“eat”, “tea”, “ate”], [“tan”, “nat”], [“bat”]] Approach: The key observation for solving the Group Anagrams problem is that two strings are anagrams if and only if their sorted versions are identical. So, one approach is to sort each string and use the sorted version as a key to group the anagrams. Algorithm (in pseudocode): Complexity Analysis: Code Implementations: 1. C++ #include <iostream>#include <vector>#include <unordered_map>#include <algorithm>using namespace std;vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> anagramGroups; for (string s : strs) { string sorted_str = s; sort(sorted_str.begin(), sorted_str.end()); anagramGroups[sorted_str].push_back(s); } vector<vector<string>> result; for (auto& pair : anagramGroups) { result.push_back(pair.second); } return result;}int main() { vector<string> strs = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; vector<vector<string>> result = groupAnagrams(strs); for (auto& group : result) { for (string word : group) { cout << word << ” “; } cout << endl; } return 0;} 2. C #include <stdio.h>#include <string.h>#include <stdlib.h>#include <ctype.h>#define MAX_STR_LEN 100#define MAX_STRINGS 100// Function to compare two strings (used by qsort)int compareStrings(const void *a, const void *b) { return strcmp(*(const char **)a, *(const char **)b);}// Function to sort the characters of a stringvoid sortString(char *str) { int len = strlen(str); qsort(str, len, sizeof(char), compareStrings);}int main() { char *strs[] = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; int n = 6; // Temporary array to store sorted strings char *sortedStrs[n]; for (int i = 0; i < n; i++) { sortedStrs[i] = strdup(strs[i]); sortString(sortedStrs[i]); } // Grouping logic can be done manually (using hash maps, or just printing similar sorted strings) // This is just a simple illustration printf(“Grouped Anagrams:\n”); for (int i = 0; i < n; i++) { printf(“%s\n”, strs[i]); } return 0;} 3. Java import java.util.*;public class GroupAnagrams { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> anagramGroups = new HashMap<>(); for (String s : strs) { char[] chars = s.toCharArray(); Arrays.sort(chars); String sortedStr = new String(chars); anagramGroups.putIfAbsent(sortedStr, new ArrayList<>()); anagramGroups.get(sortedStr).add(s); } return new ArrayList<>(anagramGroups.values()); } public static void main(String[] args) { GroupAnagrams solution = new GroupAnagrams(); String[] strs = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; List<List<String>> result = solution.groupAnagrams(strs); for (List<String> group : result) { System.out.println(group); } }} 4. Python from collections import defaultdictdef group_anagrams(strs): anagram_groups = defaultdict(list) for s in strs: sorted_str = ”.join(sorted(s)) anagram_groups[sorted_str].append(s) return list(anagram_groups.values())# Test the functionstrs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]result = group_anagrams(strs)for group in result: print(group) 5. C# using System;using System.Collections.Generic;public class GroupAnagrams { public List<List<string>> GroupAnagramsMethod(string[] strs) { var anagramGroups = new Dictionary<string, List<string>>(); foreach (string s in strs) { char[] chars = s.ToCharArray(); Array.Sort(chars); string sortedStr = new string(chars); if (!anagramGroups.ContainsKey(sortedStr)) { anagramGroups[sortedStr] = new List<string>(); } anagramGroups[sortedStr].Add(s); } var result = new List<List<string>>(); foreach (var group in anagramGroups.Values) { result.Add(group); } return result; } public static void Main() { GroupAnagrams solution = new GroupAnagrams(); string[] strs = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; var result = solution.GroupAnagramsMethod(strs); foreach (var group in result) { foreach (var word in group) { Console.Write(word + ” “); } Console.WriteLine(); } }} 6. JavaScript function groupAnagrams(strs) { const anagramGroups = {}; for (let str of strs) { const sortedStr = str.split(”).sort().join(”); if (!anagramGroups[sortedStr]) { anagramGroups[sortedStr] = []; } anagramGroups[sortedStr].push(str); } return Object.values(anagramGroups);}// Test the functionconst strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”];const result = groupAnagrams(strs);console.log(result); Summary: The Group Anagrams problem can be efficiently solved by using sorting or character counting and storing results in a hash map. The sorting method is the most straightforward and commonly used. The time complexity of the solution depends on the time to sort each string, which is O(klog⁡k)O(k \log k)O(klogk), where kkk is the average length of a string.

The objective is to rearrange a sorted array arr[] of size n so that every unique element appears at the beginning in sorted order. Return the length of this unique sorted subarray as well. Note: Since they have no bearing on the outcome, the items that follow the distinct ones can be in any sequence and have any value. Table of Content Hash Set Utilization: Effective for Unsorted Additionally, O(n) Space and O(n) Time C++ Java Python C# JavaScript Output 1 2 3 4 5

We don’t need to keep a hash set because the array is sorted. An element would appear one after the other. Therefore, our primary task is to determine whether the current element is identical to the prior one. Detailed implementation: C++ C Java Python Output 1 2 3 4 5

Considering an array arr[] that only contains 0s, 1s, and 2s. Sorting the array means placing all 0s first, followed by all 1s and all 2s last. This issue is identical to the well-known “Dutch National Flag problem.” Edsger Dijkstra was the one who introduced the problem. The following is the issue: Given a line of n balls in a random arrangement, they can be red, white, or blue. All of the balls must be arranged so that they are adjacent to each other in the same color order, which is red, white, and blue (that is, all red balls should be placed first, followed by white balls, and finally blue balls). Table of Content [Naive Approach] Sorting – O(n * log(n)) Time and O(1) Space Sorting the array with a conventional sorting algorithm or sort library function is the naïve option. This will merely arrange all of the zeros first, followed by all of the ones and twos last. This method uses O(1) space and O(n * log(n)) time. [Better Approach] Counting 0s, 1s and 2s – Two Pass – O(n) Time and O(1) Space Counting the number of 0s, 1s, and 2s—let’s say c0, c1, and c2—after one traversal of the array is a superior method. Go through the array once again now, entering c0 (count of 0s) 0s first, followed by c1 1s and c2 2s. Although this method is unstable and necessitates two array traversals, it operates in O(n) time. C++ C Python C# JavaScript Output 0 0 1 1 2 2 Time Complexity: O(2 * n), where n is the number of elements in the arrayAuxiliary Space: O(1) The issues with this approach are:

Navigate through the array until mid <= hi. Three scenarios can be identified based on the value of arr[mid]: C++ C Java Python C# JavaScript Output 0 0 1 1 2 2

Determine the location of X in the matrix, if it exists, given a N X N matrix and an integer X. Print “Element not found” otherwise. The matrix’s rows and columns are arranged in ascending order. Approaches to Search in row wise and column wise sorted matrix: [Naive Approach] Traversing the Complete Matrix – O(N^2) Time and O(1) Space Expected Approach] Removing row or column in each comparison – O(N) Time and O(1) Space [Naive Approach] Traversing the Complete Matrix – O(N^2) Time and O(1) Space: C++ C Java Python JS Output Element found at (2, 1) Time Complexity: O(N2)Auxiliary Space: O(1), since no extra space has been taken

In each comparison, the goal is to eliminate a row or column until an element is discovered. From the matrix’s upper-right corner, begin your search. Three scenarios could occur: C++ C Java Python C# JavaScript Output Element found at (2, 1)