Tag: algorithms

Developers flex on each with the strangest of ways. How green is your github commit history. Have you submitted a PR to a open source project. How well can you solve the silliest questions on leetcode / geeksforgeeks / hackerrank?
While normies use money and status as a measure of success. Coders have incelled their way into a paradise where the glow of the monitor is all you need.
Pray for death all you want, it’s not coming. Man up and start grinding.

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

A 0-indexed string num of length n + 1 is created using the following conditions:

• num consists of the digits '1' to '9', where each digit is used at most once.
• If pattern[i] == 'I', then num[i] < num[i + 1].
• If pattern[i] == 'D', then num[i] > num[i + 1].

Return the lexicographically smallest possible string num that meets the conditions.

Example 1:

Input: pattern = "IIIDIDDD"
Output: "123549876"
Explanation:
At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1].
At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1].
Some possible values of num are "245639871", "135749862", and "123849765".
It can be proven that "123549876" is the smallest possible num that meets the conditions.
Note that "123414321" is not possible because the digit '1' is used more than once.

Example 2:

Input: pattern = "DDD"
Output: "4321"
Explanation:
Some possible values of num are "9876", "7321", and "8742".
It can be proven that "4321" is the smallest possible num that meets the conditions.

Constraints:

• 1 <= pattern.length <= 8
• pattern consists of only the letters 'I' and 'D'.

class Solution {
public:
    string smallestNumber(string pattern) {
        string result;
        stack<int> st;
        for( int i = 0; i<= pattern.size(); i++ ){
            st.push(i+1);
             if ( i == pattern.length() || pattern[i] == 'I' )
                while(!st.empty()){
                    result+=to_string( st.top() );
                    st.pop();        
                }
                
        }
        return result;
    }
};

1863. Sum of All Subset XOR Totals
This is a good problem to grasp basics of backtracking

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

• For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums. 

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

class Solution {
    vector<vector<int>> subset;
    void backtrack(vector<int> &nums,vector<int> &current,int index){
        subset.push_back(current);
        for(int i = index; i < nums.size(); i++ ){
            current.push_back(nums[i]);
            backtrack( nums,  current, i+1);
            current.pop_back();
        }
    }
public:
    
    int subsetXORSum(vector<int>& nums) {
        vector<int> current;
        backtrack(nums,current,0);
        
        int total_sum = 0;
        for (const auto& sub : subset) {
            int xor_sum = 0;
            for (int num : sub) {
                //std::cout<<num<<" ";
                xor_sum ^= num;
            }
            //std::cout<<std::endl;
            total_sum += xor_sum;
        }
        
        return total_sum;
    }
};

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Constraints:

• 1 <= s1.length, s2.length <= 100
• s1.length == s2.length
• s1 and s2 consist of only lowercase English letters.

class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        vector<int> index;
        for( uint8_t i = 0; i < s1.length(); i++ ){
            if( s1[i] != s2[i] )
                index.push_back(i);
            if( index.size() > 2)
                return false;

        }
        if( index.size() == 2 ){
            int i = index[0];
            int j = index[1];
            if( s1[i] == s2[j] && s1[j] == s2[i] ) return true;
        }
    
        return index.size() == 0;
    }
};

https://leetcode.com/problems/remove-nth-node-from-end-of-list

Given the head of a linked list, remove the n<sup>th</sup> node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head);
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        // Move fast n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }

        // Move both pointers
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }

        // Remove the nth node
        slow->next = slow->next->next;

        return dummy.next;
    }
};

// Function to create a linked list from an array
ListNode* createLinkedList(int arr[], int size) {
    if (size == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// Function to print a linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

// Main function for testing
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int n = 2;  // Remove the 2nd node from the end

    // Create linked list
    ListNode* head = createLinkedList(arr, size);

    cout << "Original List: ";
    printLinkedList(head);

    // Call removeNthFromEnd function
    Solution solution;
    head = solution.removeNthFromEnd(head, n);

    cout << "Updated List: ";
    printLinkedList(head);

    return 0;
}