짬뽕얼큰하게의 맨땅에 헤딩 :: '분류 전체보기' 카테고리의 글 목록 (5 Page)

Bitwise XOR of All Pairings

알고리즘 2025. 3. 4. 09:07

Leetcode Problem:

Summary

  • Given two arrays, nums1 and nums2, return the bitwise XOR of all pairings of integers between nums1 and nums2.

Approach

  • The solution uses two nested loops to iterate over the elements of nums1 and nums2
  • For each element in nums1, it XORs the element with all elements in nums2
  • Similarly, for each element in nums2, it XORs the element with all elements in nums1
  • The XOR operation is used to combine the pairings, and the result is returned.

Complexity

  • O(n*m) where n is the size of nums1 and m is the size of nums2

Explanation

  • The solution iterates over the elements of nums1 and nums2 using two nested loops
  • For each element in nums1, it XORs the element with all elements in nums2 using a single loop
  • Similarly, for each element in nums2, it XORs the element with all elements in nums1 using another single loop
  • The XOR operation is associative and commutative, so the order of the loops does not matter
  • The result of the XOR operation is the bitwise XOR of all pairings of integers between nums1 and nums2.

Solution Code:


class Solution {
public:
    int xorAllNums(vector& nums1, vector& nums2) {
        int n1 = (nums1.size()-1) % 2;
        int n2 = (nums2.size()-1) % 2;
        int ans = 0;
        for(int i = 0 ; i < nums1.size(); i++){
            for(int j = 0 ; j <= n2; j++){
                ans ^= nums1[i];
            }
        }
        for(int i = 0 ; i < nums2.size(); i++){
            for(int j = 0; j <= n1; j++){
                ans ^= nums2[i];
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Neighboring Bitwise XOR  (0) 2025.03.05
Check if Number is a Sum of Powers of Three  (0) 2025.03.04
Minimize XOR  (0) 2025.03.04
Find the Prefix Common Array of Two Arrays  (0) 2025.03.04
Construct K Palindrome Strings  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Minimize XOR

알고리즘 2025. 3. 4. 09:04

Leetcode Problem:

Summary

  • Find the positive integer x such that x has the same number of set bits as num2 and the value x XOR num1 is minimal.

Approach

  • The solution uses a two-step approach
  • First, it counts the number of set bits in num1 and num2 using a helper function
  • Then, it adjusts num1 to have the same number of set bits as num2 by shifting bits to the right and/or left until the difference is zero
  • The final result is the adjusted num1.

Complexity

  • O(log max(num1, num2))

Explanation

  • The time complexity is O(log max(num1, num2)) because in the worst case, we need to shift bits up to 32 places to the right (for a 32-bit integer)
  • The space complexity is O(1) because we only use a constant amount of space to store the result and the temporary variables.

Solution Code:


class Solution {
public:
    int bitCount(int n){
        int cnt = 0;
        while(n){
            cnt++;
            n &= n-1;
        }
        return cnt;
    }
    int minimizeXor(int num1, int num2) {
        int bit1 = bitCount(num1);
        int bit2 = bitCount(num2);
        int x = num1;
        int diff = bit2 - bit1;
        if(diff == 0) return num1;
        else if(diff > 0){
            long long offset = 1;
            while(diff){
                if((offset & x) == 0){
                    diff--;
                }
                x |= offset;
                offset <<= 1;
            }
        } else{
            diff = -diff;
            while(diff--){
                x &= x - 1;
            }
        }
        return x;
    }
};

'알고리즘' 카테고리의 다른 글

Check if Number is a Sum of Powers of Three  (0) 2025.03.04
Bitwise XOR of All Pairings  (0) 2025.03.04
Find the Prefix Common Array of Two Arrays  (0) 2025.03.04
Construct K Palindrome Strings  (0) 2025.03.04
Word Subsets  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Find the Prefix Common Array of Two Arrays

알고리즘 2025. 3. 4. 09:01

Leetcode Problem:

Summary

  • Find the prefix common array of two integer permutations

Approach

  • The approach is to use bitwise operations to count the common elements in both permutations
  • The idea is to treat each permutation as a subset of numbers from 1 to n, where n is the length of the permutations
  • We use a binary number to represent each subset, where each bit corresponds to a number from 1 to n
  • We then use bitwise operations to count the common elements in both subsets.

Complexity

  • O(n log n) due to the bitCount function, where n is the length of the permutations

Explanation

  • The solution works by iterating over each element in both permutations and updating the subset numbers for each permutation
  • For each element, we use bitwise operations to count the common elements in both subsets
  • The bitCount function is used to count the number of bits set in a binary number, which represents the count of common elements
  • The result is a vector of integers representing the prefix common array.

Solution Code:


class Solution {
public:
    int bitCount(unsigned long long num){
        int cnt = 0;
        while(num){
            cnt++;
            num &= num-1;
        }
        return cnt;
    }
    vector findThePrefixCommonArray(vector& A, vector& B) {
        unsigned long long subsetA = 0;
        unsigned long long subsetB = 0;
        vector ans;
        for(int i = 0 ; i < A.size(); i++){
            subsetA |= 1ULL << A[i];
            subsetB |= 1ULL << B[i];
            ans.push_back(bitCount(subsetA & subsetB));
        }
        return  ans;
    }
};

'알고리즘' 카테고리의 다른 글

Bitwise XOR of All Pairings  (0) 2025.03.04
Minimize XOR  (0) 2025.03.04
Construct K Palindrome Strings  (0) 2025.03.04
Word Subsets  (0) 2025.03.04
Counting Words With a Given Prefix  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Construct K Palindrome Strings

알고리즘 2025. 3. 4. 08:57

Leetcode Problem:

Summary

  • Given a string s and an integer k, return true if all characters in s can be used to construct non-empty k palindrome strings or false otherwise.

Approach

  • This solution uses a frequency count array to store the frequency of each character in the string
  • It then checks the number of characters with odd frequencies, which are the characters that can only appear in one palindrome
  • If the number of such characters is less than or equal to k, it means that all characters can be used to construct k palindrome strings.

Complexity

  • O(n) where n is the length of the string, because we are iterating over the string twice (to count frequencies and to check odd frequencies).

Explanation

  • We start by checking if the length of the string is less than k
  • If it is, we return false because we cannot construct k palindrome strings
  • We then create a frequency count array cnt of size 128 to store the frequency of each character in the string
  • We iterate over the string and increment the count of each character in the array
  • We then iterate over the characters 'a' to 'z' and count the number of characters with odd frequencies
  • If this number is less than or equal to k, we return true because we can construct k palindrome strings
  • Otherwise, we return false.

Solution Code:


class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.size() < k) return false;
        int cnt[128];
        for(char c: s){
            cnt[c]++;
        }
        int odd = 0;
        for(int i = 'a'; i <= 'z'; i++){
            odd += cnt[i] & 1;
        }
        return odd <= k;
    }
};

'알고리즘' 카테고리의 다른 글

Minimize XOR  (0) 2025.03.04
Find the Prefix Common Array of Two Arrays  (0) 2025.03.04
Word Subsets  (0) 2025.03.04
Counting Words With a Given Prefix  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Word Subsets

알고리즘 2025. 3. 4. 08:54

Leetcode Problem:

Summary

  • Given two string arrays, find all the universal strings in the first array that can form a subset of every string in the second array.

Approach

  • The approach used is to first count the frequency of each character in all strings of the second array
  • Then, for each string in the first array, check if it can form a subset of every string in the second array by comparing the frequency of each character in the string with the minimum count from the second array
  • If a string can form a subset of every string in the second array, it is added to the result.

Complexity

  • O(n * m * 26) where n is the number of strings in the first array, m is the number of strings in the second array, and 26 is the number of lowercase English letters.

Explanation

  • The solution uses a character count array `charCnt` to store the minimum frequency of each character in the second array
  • It then iterates over each string in the first array and checks if it can form a subset of every string in the second array by comparing the frequency of each character in the string with the minimum count from the second array
  • If a string can form a subset of every string in the second array, it is added to the result.

Solution Code:


class Solution {
public:
    int charCnt[128];
    vector wordSubsets(vector& words1, vector& words2) {
        for(string word : words2){
            int tmpCnt[128] = {0};
            for(char c : word){
                tmpCnt[c]++;
            }
            for(int i = 'a' ; i <= 'z'; i++){
                charCnt[i] = max(charCnt[i], tmpCnt[i]);
            }
        }
        vector ans;
        for(string word : words1){
            int tmpCnt[128] = {0};
            for(char c : word){
                tmpCnt[c]++;
            }
            bool isSubset = true;
            for(int i = 'a' ; i <= 'z'; i++){
                if(charCnt[i] == 0) continue;
                if(tmpCnt[i] < charCnt[i]){
                    isSubset = false;
                    break;
                }
            }
            if(isSubset){
                ans.push_back(word);
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Find the Prefix Common Array of Two Arrays  (0) 2025.03.04
Construct K Palindrome Strings  (0) 2025.03.04
Counting Words With a Given Prefix  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Counting Words With a Given Prefix

알고리즘 2025. 3. 4. 08:50

Leetcode Problem:

Summary

  • Find the number of strings in the array that contain a given prefix.

Approach

  • The solution uses a simple loop to iterate over each word in the array
  • For each word, it checks if the prefix is present by comparing characters one by one
  • If the prefix is found, it increments the answer counter.

Complexity

  • O(n*m) where n is the number of words and m is the length of the prefix.

Explanation

  • The solution works by iterating over each word in the array and comparing it with the prefix
  • It uses two nested loops to compare characters one by one
  • The outer loop iterates over each word, and the inner loop compares characters up to the length of the prefix
  • If the prefix is found, it increments the answer counter.

Solution Code:


class Solution {
public:
    int prefixCount(vector& words, string pref) {
        int ans = 0;
        for(string word : words){
            int i = 0;
            for( ; i < pref.size(); i++){
                if(pref[i] != word[i]){
                    break;
                }
            }
            if(i == pref.size()){
                ans++;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Construct K Palindrome Strings  (0) 2025.03.04
Word Subsets  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

Count Prefix and Suffix Pairs I

알고리즘 2025. 3. 4. 08:48

Leetcode Problem:

Summary

  • This solution is designed to count the number of index pairs (i, j) where i < j and isPrefixAndSuffix(words[i], words[j]) is true.

Approach

  • The solution uses a nested loop approach to iterate over each pair of words in the input array
  • It checks if each word is a prefix and suffix of every other word in the array
  • The isPrefixAndSuffix function is used to check this condition
  • The time complexity of this approach is O(n^2 * m) where n is the number of words and m is the maximum length of a word.

Complexity

  • O(n^2 * m)

Explanation

  • The solution starts by initializing a variable ans to 0, which will be used to store the count of index pairs
  • It then iterates over each word in the input array using a for loop
  • For each word, it iterates over the rest of the words in the array using another for loop
  • For each pair of words, it checks if the word is a prefix and suffix of the other word using the isPrefixAndSuffix function
  • If it is, it increments the ans variable
  • Finally, it returns the ans variable at the end of the function.

Solution Code:


class Solution {
public:
    bool isPrefixAndSuffix(string str1, string str2){
        if(str1.size() > str2.size()) return false;
        for(int i = 0 ; i < str1.size(); i++){
            if(str1[i] != str2[i])return false;
            if(str1[i] != str2[str2.size() - str1.size() + i]) return false;
        }
        return true;
    }
    int countPrefixSuffixPairs(vector& words) {
        int ans = 0;
        for(int i = 0 ; i < words.size(); i++){
            for(int j = i + 1 ; j < words.size(); j++){
                if(isPrefixAndSuffix(words[i], words[j])){
                    ans++;
                }
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Word Subsets  (0) 2025.03.04
Counting Words With a Given Prefix  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
블로그 이미지

짬뽕얼큰하게

,

String Matching in an Array

알고리즘 2025. 3. 4. 08:44

Leetcode Problem:

Summary

  • Given an array of strings, return all strings that are a substring of another word.

Approach

  • The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
  • It uses nested loops to compare characters between words.

Complexity

  • O(n^3) where n is the number of words in the input array

Explanation

  • The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
  • It uses nested loops to compare characters between words
  • The outer loop iterates over each word, the middle loop checks if the current word is a substring of any other word, and the inner loop compares characters between words
  • If a word is found to be a substring of another word, it is added to the result array and the middle loop is terminated to avoid unnecessary comparisons.

Solution Code:


class Solution {
public:
    vector stringMatching(vector& words) {
        vector ans;
        for(int i = 0 ; i < words.size(); i++){
            bool success = false;
            for(int j = 0; j < words.size(); j++){
                if(i == j) continue;
                for(int k = 0; k < words[j].size(); k++){
                    int l = 0;
                    for(; l < words[i].size(); l++){
                        if(words[j][k+l] != words[i][l]) break;
                    }
                    if(l == words[i].size()){
                        ans.push_back(words[i]);
                        success = true;
                        break;
                    }
                }
                if(success) break;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Counting Words With a Given Prefix  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Operations to Move All Balls to Each Box

알고리즘 2025. 3. 4. 08:41

Leetcode Problem:

Summary

  • Given a binary string representing boxes with balls, find the minimum number of operations needed to move all the balls to each box.

Approach

  • The approach is to first count the number of balls in each box and store it in the `ltor` and `rtol` arrays
  • Then, calculate the minimum number of operations needed to move all the balls to each box by adding the `ltor` and `rtol` values at each index.

Complexity

  • O(n), where n is the length of the binary string.

Explanation

  • The provided C++ solution uses two arrays, `ltor` and `rtol`, to store the cumulative count of balls from the left and right sides of each box
  • The minimum number of operations needed to move all the balls to each box is calculated by adding the `ltor` and `rtol` values at each index
  • This approach ensures that the minimum number of operations is calculated considering the initial state of the boxes.

Solution Code:


class Solution {
public:
    int ltor[2000];
    int rtol[2000];
    vector minOperations(string boxes) {
        vector ans;
        int oneCnt = 0;
        for(int i = 0 ; i < boxes.size() - 1; i++){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            ltor[i+1] = ltor[i] + oneCnt;
        }
        oneCnt = 0;
        for(int i = boxes.size() - 1; i > 0 ; i--){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            rtol[i-1] = rtol[i] + oneCnt;
        }
        for(int i = 0 ; i < boxes.size(); i++){
            ans.push_back(ltor[i] + rtol[i]);
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Count Prefix and Suffix Pairs I  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Shifting Letters II

알고리즘 2025. 3. 4. 08:38

Leetcode Problem:

Summary

  • Given a string s and a 2D integer array shifts, shift the characters in s from the start index to the end index forward if direction is 1, or backward if direction is 0.

Approach

  • This solution uses a prefix sum array to efficiently calculate the cumulative sum of shifts for each character
  • It then iterates over the string, adding the prefix sum to the current character's ASCII value and taking the modulus 26 to wrap around the alphabet.

Complexity

  • O(n + m) where n is the length of the string s and m is the number of shifts, as it needs to iterate over the string and the shifts array once.

Explanation

  • The prefix sum array pSum is used to store the cumulative sum of shifts for each character
  • For each shift, the sum of the character at the start index and the sum of the character at the end index plus the shift direction are added to pSum[start] and pSum[end+1] respectively
  • Then, the string is iterated over, and the prefix sum is added to the current character's ASCII value to get the shifted character
  • The modulus 26 is taken to wrap around the alphabet.

Solution Code:


class Solution {
public:
    int pSum[500001];
    int fb[2] = {25, 1};
    string shiftingLetters(string s, vector>& shifts) {
        for(int i = 0 ; i < shifts.size(); i++){
            int start = shifts[i][0];
            int end = shifts[i][1];
            int dir = shifts[i][2];
            pSum[start] += fb[dir];
            pSum[start] %= 26;
            pSum[end+1] += fb[dir ^ 1];
            pSum[end+1] %= 26;
            
        }

        string ans = "";
        for(int i = 0 ; i < s.size(); i++){
            pSum[i+1] += pSum[i];
            pSum[i] %= 26;
            unsigned char c = s[i] + pSum[i];
            if(c > 'z') c = 'a' + (c - 'z') - 1;
            if(c < 'a') c = 'z' - ('a' - c - 1);
            ans += c;
        }
        
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

String Matching in an Array  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
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

티스토리툴바