Bit by Bit Vol 2

Lexicographically Smallest Palindrome

Given a string s, transform it into the lexicographically smallest palindrome by replacing characters in the string. You can only replace characters such that the resulting string is a palindrome.

Input Format:

A single line containing string s of length n.

Output Format:

A single string, the lexicographically smallest palindrome possible.

Constraints:

1 ≤ n ≤ 1000
s consists of lowercase English letters only.

Sample Test Case:

Input:

bcaacb

Output:

abccba

C++ Solution

// C++ Solution
#include <iostream>
#include <string>
using namespace std;

string makeSmallestPalindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; ++i) {
        if (s[i] != s[n - i - 1]) {
            s[i] = s[n - i - 1] = min(s[i], s[n - i - 1]);
        }
    }
    return s;
}

int main() {
    string s;
    cin >> s;
    cout << makeSmallestPalindrome(s) << endl;
    return 0;
}

Python3 Solution

# Python Solution
def make_smallest_palindrome(s):
    s = list(s)
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            s[i] = s[n - i - 1] = min(s[i], s[n - i - 1])
    return ''.join(s)

if __name__ == "__main__":
    s = input().strip()
    print(make_smallest_palindrome(s))

Remove Duplicates from Sorted Array

Given a sorted integer array, remove duplicate elements in-place, so that each element appears only once. Return the updated array without extra space.

Input Format:

First line: Integer n (size of the array).
Second line: n space-separated integers (sorted array).

Output Format:

The modified array without duplicates, maintaining the original order.

Constraints:

1 ≤ n ≤ 10^4
-10^4 ≤ arr[i] ≤ 10^4

Sample Test Case:

Input:

6
1 1 2 2 3 3

Output:

1 2 3

C++ Solution

// C++ Solution
#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int index = 1;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] != nums[i - 1]) {
            nums[index++] = nums[i];
        }
    }
    return index;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    int newLength = removeDuplicates(nums);
    for (int i = 0; i < newLength; ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}

Python3 Solution

# Python Solution
def remove_duplicates(nums):
    if not nums:
        return 0
    index = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            nums[index] = nums[i]
            index += 1
    return index

if __name__ == "__main__":
    n = int(input().strip())
    nums = list(map(int, input().strip().split()))
    new_length = remove_duplicates(nums)
    print(" ".join(map(str, nums[:new_length])))

Intersection of Two Arrays

Given two arrays, return the intersection of the arrays (i.e., common elements without duplicates).

Input Format:

First line: Integer n (size of array1).
Second line: n space-separated integers (array1).
Third line: Integer m (size of array2).
Fourth line: m space-separated integers (array2).

Output Format:

Space-separated integers representing the intersection of the arrays in any order.

Constraints:

1 ≤ n, m ≤ 1000
-10^4 ≤ arr[i] ≤ 10^4

Sample Test Case:

Input:

Output:

3 4

C++ Solution

// C++ Solution
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> set1(nums1.begin(), nums1.end());
    unordered_set<int> resultSet;
    for (int num : nums2) {
        if (set1.count(num)) {
            resultSet.insert(num);
        }
    }
    return vector<int>(resultSet.begin(), resultSet.end());
}

int main() {
    int n, m;
    cin >> n;
    vector<int> nums1(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums1[i];
    }
    cin >> m;
    vector<int> nums2(m);
    for (int i = 0; i < m; ++i) {
        cin >> nums2[i];
    }
    vector<int> result = intersection(nums1, nums2);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Python3 Solution

# Python Solution
def intersection(nums1, nums2):
    set1 = set(nums1)
    result_set = {num for num in nums2 if num in set1}
    return list(result_set)

if __name__ == "__main__":
    n = int(input().strip())
    nums1 = list(map(int, input().strip().split()))
    m = int(input().strip())
    nums2 = list(map(int, input().strip().split()))
    result = intersection(nums1, nums2)
    print(" ".join(map(str, result)))

Move Zeros to End

Given an integer array nums, move all 0’s to the end while maintaining the relative order of the non-zero elements.

Input Format:

First line: Integer n (size of the array).
Second line: n space-separated integers.

Output Format:

The modified array with all zeroes at the end.

Constraints:

1 ≤ n ≤ 10^4

Sample Test Case:

Input:

6
0 3 0 5 2 0

Output:

3 5 2 0 0 0

C++ Solution

// C++ Solution
#include <iostream>
#include <vector>
using namespace std;

void moveZeroes(vector<int>& nums) {
    int index = 0;
    for (int num : nums) {
        if (num != 0) {
            nums[index++] = num;
        }
    }
    while (index < nums.size()) {
        nums[index++] = 0;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    moveZeroes(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Python3 Solution

# Python Solution
def move_zeroes(nums):
    index = 0
    for num in nums:
        if num != 0:
            nums[index] = num
            index += 1
    while index < len(nums):
        nums[index] = 0
        index += 1

if __name__ == "__main__":
    n = int(input().strip())
    nums = list(map(int, input().strip().split()))
    move_zeroes(nums)
    print(" ".join(map(str, nums)))

Merge Two Sorted Lists

Given two sorted arrays, merge them into one sorted array.

Input Format:

First line: Integer n (size of array1).
Second line: n space-separated integers (sorted).
Third line: Integer m (size of array2).
Fourth line: m space-separated integers (sorted).

Output Format:

A single sorted array.

Constraints:

0 ≤ n, m ≤ 50
-100 ≤ arr[i] ≤ 100

Sample Test Case:

Input:

Output:

1 2 3 4 5 6 8

C++ Solution

// C++ Solution
#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    vector<int> result;
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) {
            result.push_back(nums1[i++]);
        } else {
            result.push_back(nums2[j++]);
        }
    }
    while (i < nums1.size()) {
        result.push_back(nums1[i++]);
    }
    while (j < nums2.size()) {
        result.push_back(nums2[j++]);
    }
    return result;
}

int main() {
    int n, m;
    cin >> n;
    vector<int> nums1(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums1[i];
    }
    cin >> m;
    vector<int> nums2(m);
    for (int i = 0; i < m; ++i) {
        cin >> nums2[i];
    }
    vector<int> result = mergeSortedArrays(nums1, nums2);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Python3 Solution

# Python Solution
def merge_sorted_arrays(nums1, nums2):
    result = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

if __name__ == "__main__":
    n = int(input().strip())
    nums1 = list(map(int, input().strip().split()))
    m = int(input().strip())
    nums2 = list(map(int, input().strip().split()))
    result = merge_sorted_arrays(nums1, nums2)
    print(" ".join(map(str, result)))

Matrix Multiplication

Given two matrices A and B, multiply them if multiplication is possible.

Input Format:

First line: Integers n1 m1 (dimensions of matrix A).
Next n1 lines: Each contains m1 space-separated integers.
Next line: Integers n2 m2 (dimensions of matrix B).
Next n2 lines: Each contains m2 space-separated integers.

Output Format:

The resulting matrix if multiplication is possible.
Otherwise, print "Not Possible".

Constraints:

1 ≤ n1, m1, n2, m2 ≤ 100
-100 ≤ matrix elements ≤ 100

Sample Test Case:

Input:

Output:

58 64
139 154

C++ Solution

// C++ Solution
#include <iostream>
#include <vector>
using namespace std;

vector> multiplyMatrices(vector>& A, vector>& B) {
    int n1 = A.size(), m1 = A[0].size(), n2 = B.size(), m2 = B[0].size();
    if (m1 != n2) return {};
    vector> result(n1, vector(m2, 0));
    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < m2; ++j) {
            for (int k = 0; k < m1; ++k) {
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return result;
}

int main() {
    int n1, m1, n2, m2;
    cin >> n1 >> m1;
    vector> A(n1, vector(m1));
    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < m1; ++j) {
            cin >> A[i][j];
        }
    }
    cin >> n2 >> m2;
    vector> B(n2, vector(m2));
    for (int i = 0; i < n2; ++i) {
        for (int j = 0; j < m2; ++j) {
            cin >> B[i][j];
        }
    }
    if (m1 != n2) {
        cout << "Not Possible" << endl;
    } else {
        vector> result = multiplyMatrices(A, B);
        for (const auto& row : result) {
            for (int val : row) {
                cout << val << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

Python3 Solution

# Python Solution
def multiply_matrices(A, B):
    n1, m1 = len(A), len(A[0])
    n2, m2 = len(B), len(B[0])
    if m1 != n2:
        return "Not Possible"
    result = [[0] * m2 for _ in range(n1)]
    for i in range(n1):
        for j in range(m2):
            for k in range(m1):
                result[i][j] += A[i][k] * B[k][j]
    return result

if __name__ == "__main__":
    n1, m1 = map(int, input().strip().split())
    A = [list(map(int, input().strip().split())) for _ in range(n1)]
    n2, m2 = map(int, input().strip().split())
    B = [list(map(int, input().strip().split())) for _ in range(n2)]
    result = multiply_matrices(A, B)
    if result == "Not Possible":
        print(result)
    else:
        for row in result:
            print(" ".join(map(str, row)))

Valid Parentheses

Given a string containing only (), {}, and [], check if it is balanced.

Input Format:

A single string s containing only the given brackets.

Output Format:

Print "yes" if balanced, otherwise "no".

Constraints:

1 ≤ s.length ≤ 1000

Sample Test Case:

Input:

()[]{}

Output:

yes

C++ Solution

// C++ Solution
#include <iostream>
#include <stack>
using namespace std;

bool isValid(string s) {
    stack stk;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            stk.push(c);
        } else {
            if (stk.empty()) return false;
            char top = stk.top();
            if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false;
            }
            stk.pop();
        }
    }
    return stk.empty();
}

int main() {
    string s;
    cin >> s;
    cout << (isValid(s) ? "yes" : "no") << endl;
    return 0;
}

Python3 Solution

# Python Solution
def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return "no"
        else:
            stack.append(char)
    return "yes" if not stack else "no"

if __name__ == "__main__":
    s = input().strip()
    print(is_valid(s))

Collatz Sequence Simulation

Simulate the Collatz sequence:

If n is even, divide it by 2.
If n is odd, multiply it by 3 and add 1.
Repeat until n = 1.

Input Format:

A single integer n.

Output Format:

The sequence of numbers until n = 1.

Constraints:

1 ≤ n ≤ 10^6

Sample Test Case:

Input:

Output:

3 10 5 16 8 4 2 1

C++ Solution

// C++ Solution
#include <iostream>
#include <vector>
using namespace std;

vector<int> collatzSequence(int n) {
    vector<int> sequence;
    while (n != 1) {
        sequence.push_back(n);
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3 * n + 1;
        }
    }
    sequence.push_back(1);
    return sequence;
}

int main() {
    int n;
    cin >> n;
    vector<int> sequence = collatzSequence(n);
    for (int num : sequence) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Python3 Solution

# Python Solution
def collatz_sequence(n):
    sequence = []
    while n != 1:
        sequence.append(n)
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
    sequence.append(1)
    return sequence

if __name__ == "__main__":
    n = int(input().strip())
    sequence = collatz_sequence(n)
    print(" ".join(map(str, sequence)))

Longest Repetition in a DNA Sequence

Given a DNA sequence (a string composed of A, C, G, T), find the length of the longest contiguous repetition.

Input Format:

A single string containing n characters.

Output Format:

A single integer representing the length of the longest repetition.

Constraints:

1 ≤ n ≤ 10^6

Sample Test Case:

Input:

ATTCGGGA

Output:

C++ Solution

// C++ Solution
#include <iostream>
#include <string>
using namespace std;

int longestRepetition(string s) {
    int maxLen = 1, currentLen = 1;
    for (int i = 1; i < s.length(); ++i) {
        if (s[i] == s[i - 1]) {
            currentLen++;
            maxLen = max(maxLen, currentLen);
        } else {
            currentLen = 1;
        }
    }
    return maxLen;
}

int main() {
    string s;
    cin >> s;
    cout << longestRepetition(s) << endl;
    return 0;
}

Python3 Solution

# Python Solution
def longest_repetition(s):
    max_len = 1
    current_len = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            current_len += 1
            max_len = max(max_len, current_len)
        else:
            current_len = 1
    return max_len

if __name__ == "__main__":
    s = input().strip()
    print(longest_repetition(s))