짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/02/12 글 목록

Max Sum of a Pair With Equal Sum of Digits

알고리즘 2025. 2. 12. 21:13

Leetcode Problem:

Summary

  • Find the maximum sum of two numbers in an array where the sum of digits of each number is equal.

Approach

  • The approach used is to calculate the sum of digits of each number and store them in a map
  • Then, for each sum of digits, find the two numbers in the map that can be added together to get the maximum sum
  • If there are multiple pairs, choose the one with the maximum sum.

Complexity

  • O(n log n) due to the sorting of the numbers in the map

Explain

  • The code first calculates the sum of digits of each number using the digit_sum function
  • Then, it stores these sums and their corresponding numbers in a map
  • For each sum of digits, it checks if there are already two numbers in the map that can be added together to get a larger sum
  • If not, it adds the current number to the map and updates the map if the current number is larger than the one already in the map
  • Finally, it iterates over the map to find the maximum sum of two numbers that can be obtained.

Solution Code:


class Solution {
public:
    unordered_map> map;
    int digit_sum(int num){
        int s = 0;
        while(num){
            s += num % 10;
            num /= 10;
        }
        return s;
    }
    int maximumSum(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            int digit = digit_sum(nums[i]);
            if(map[digit].size() < 2){
                map[digit].push_back(nums[i]);
                if(map[digit].size() == 2 && map[digit][0] < map[digit][1]){
                    int t = map[digit][0];
                    map[digit][0] = map[digit][1];
                    map[digit][1] = t;
                }
            } else{
                if(map[digit][0] <= nums[i]){
                    map[digit][1] = map[digit][0];
                    map[digit][0] = nums[i];
                } else{
                    map[digit][1] = max(map[digit][1], nums[i]);
                }
            }
        }
        int ans = -1;
        for(auto iter: map){
            if((iter.second).size() == 2){
                if(ans < (iter.second[0] + iter.second[1])){
                    ans = iter.second[0] + iter.second[1];
                }
            }
        }
        return ans;
    }
};

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

My Calendar I  (0) 2025.02.13
Sum of Prefix Scores of Strings  (0) 2025.02.13
Find the Length of the Longest Common Prefix  (0) 2025.02.12
Extra Characters in a String  (0) 2025.02.12
K-th Smallest in Lexicographical Order  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

Find the Length of the Longest Common Prefix

알고리즘 2025. 2. 12. 09:08

Leetcode Problem:

Summary

  • Find the length of the longest common prefix among all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.

Approach

  • Use a set to store the digits of the numbers in arr1 and then for each number in arr2, check if the digits are present in the set
  • If they are, update the answer with the maximum count of digits found so far.

Complexity

  • O(n*m*log(max(arr1[i], arr2[i]))) where n is the size of arr1 and m is the size of arr2

Explain

  • The time complexity of this solution is O(n*m*log(max(arr1[i], arr2[i]))) because for each number in arr1, we are inserting its digits into the set, and for each number in arr2, we are checking if its digits are present in the set
  • The space complexity is O(n*m) because we are storing all the digits in the set.

Solution Code:


class Solution {
public:
    set s;
    int getCount(int a){
        int cnt = 0;
        while(a){
            cnt++;
            a /= 10;
        }
        return cnt;
    }
    int longestCommonPrefix(vector& arr1, vector& arr2) {
        int ans = 0;
        for(int i = 0 ; i < arr1.size(); i++){
            while(arr1[i]){
                s.insert(arr1[i]);
                arr1[i] /= 10;
            }
        }
        for(int i = 0 ; i < arr2.size(); i++){
            while(arr2[i]){
                if (s.find(arr2[i]) != s.end()){
                    ans = max(ans, getCount(arr2[i]));
                    break;
                }
                arr2[i] /= 10;
            }
        }
        return ans;
    }
};

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

Sum of Prefix Scores of Strings  (0) 2025.02.13
Max Sum of a Pair With Equal Sum of Digits  (0) 2025.02.12
Extra Characters in a String  (0) 2025.02.12
K-th Smallest in Lexicographical Order  (0) 2025.02.12
Largest Number  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

Extra Characters in a String

알고리즘 2025. 2. 12. 09:04

Leetcode Problem:

Summary

  • Given a string s and a dictionary of words, find the minimum number of extra characters left over if the string is broken into non-overlapping substrings present in the dictionary.

Approach

  • Dynamic programming approach, where a 1D array dp is used to store the minimum number of extra characters for each prefix of the string
  • The function go recursively tries to match the current prefix with each word in the dictionary, and updates the dp array accordingly.

Complexity

  • O(n*m*len(word)) where n is the length of the string, m is the number of words in the dictionary, and len(word) is the length of each word in the dictionary.

Explain

  • The function go takes a string s, a dictionary of words dict, and an integer i as input
  • It first checks if the current prefix of the string has been processed before (i.e., dp[i] is not -1)
  • If not, it sets dp[i] to 1 (for the extra character) and recursively calls itself for the next character
  • Then it tries to match the current prefix with each word in the dictionary, and updates dp[i] with the minimum of its current value and the result of the recursive call for the next character plus the length of the current word
  • The function minExtraChar initializes the dp array and calls the function go with the initial prefix as an empty string.

Solution Code:


class Solution {
public:
    int dp[51];
    int go(string & s, vector& dict, int i){
        if(i == s.size()) return 0;

        if (dp[i] == -1){
            dp[i] = 1 + go(s, dict, i+1);
            for(auto &w: dict){
                if(s.compare(i, w.size(), w) == 0){
                    dp[i] = min(dp[i], go(s, dict, i+w.size()));
                }
            }
        }
        return dp[i];

    }
    int minExtraChar(string s, vector& dictionary) {
        memset(dp, -1, sizeof(dp));
        return go(s, dictionary, 0);
    }
};

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

Max Sum of a Pair With Equal Sum of Digits  (0) 2025.02.12
Find the Length of the Longest Common Prefix  (0) 2025.02.12
K-th Smallest in Lexicographical Order  (0) 2025.02.12
Largest Number  (0) 2025.02.12
XOR Queries of a Subarray  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

K-th Smallest in Lexicographical Order

알고리즘 2025. 2. 12. 09:01

Leetcode Problem:

Summary

  • Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Approach

  • The solution uses a binary search approach to find the kth lexicographically smallest number
  • It first calculates the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number
  • Then it recursively finds the kth lexicographically smallest number by finding the kth number that can be formed by appending a digit from 1 to 9 to the current number.

Complexity

  • O(log(n))

Explain

  • The solution consists of two main functions: findKthNumber and findKthNumber
  • The findKthNumber function takes an integer n and an integer k as input and returns the kth lexicographically smallest number
  • The findKthNumber function uses a binary search approach to find the kth lexicographically smallest number
  • It first calculates the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number
  • Then it recursively finds the kth lexicographically smallest number by finding the kth number that can be formed by appending a digit from 1 to 9 to the current number
  • The second findKthNumber function is used to calculate the number of numbers less than or equal to n that can be formed by appending a digit from 1 to 9 to the current number.

Solution Code:


class Solution {
public:
    int findKthNumber(int n, int k) {
        int result = 1;
        while (k > 1) {
            int count = findKthNumber(result, result + 1, n);
            if (count < k) {
                result++;
                k -= count;
            } else {
                result *= 10;
                k--;
            }
        }
        return result;
    }
    int findKthNumber(long p, long q, long n) {
        int result = 0;
        while (p <= n) {
            result += min(q, n + 1) - p;
            p *= 10;
            q *= 10;
        }
        return result;
    }
};

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

Find the Length of the Longest Common Prefix  (0) 2025.02.12
Extra Characters in a String  (0) 2025.02.12
Largest Number  (0) 2025.02.12
XOR Queries of a Subarray  (0) 2025.02.12
Count the Number of Consistent Strings  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

Largest Number

알고리즘 2025. 2. 12. 08:57

Leetcode Problem:

Summary

  • Given a list of non-negative integers, arrange them to form the largest number and return it as a string.

Approach

  • The approach used is to first convert all the numbers into strings, then sort them in descending order based on a custom comparison function
  • The comparison function concatenates each pair of strings in both orders (ab and ba) and returns the one that results in the larger number
  • After sorting, the strings are concatenated in reverse order to form the largest possible number.

Complexity

  • O(n log n) due to the sorting operation, where n is the number of elements in the input list.

Explain

  • The solution code first converts all the numbers in the input list into strings
  • It then defines a custom comparison function `cmp` that takes two strings `a` and `b` as input
  • This function concatenates each pair of strings in both orders (ab and ba) and returns the one that results in the larger number
  • The `largestNumber` function then sorts the list of strings using this comparison function and concatenates them in reverse order to form the largest possible number
  • Finally, it checks if the resulting number starts with '0' and returns '0' if it does, to handle the case where all the numbers are zeros.

Solution Code:


class Solution {
public:
    static bool cmp(string a, string b){
        string aa = a + b;
        string bb = b + a;
        return aa < bb;
    }
    string largestNumber(vector& nums) {
        vector str_nums;
        for(int i = 0 ; i < nums.size(); i++){
            str_nums.push_back(to_string(nums[i]));
        }
        sort(str_nums.begin(), str_nums.end(), cmp);
        string ans = "";
        for(int i = str_nums.size() - 1; i >= 0 ; i--){
            ans += str_nums[i];
        }
        if (ans.find("0") == 0) return "0";
        return ans;
    }
};

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

Extra Characters in a String  (0) 2025.02.12
K-th Smallest in Lexicographical Order  (0) 2025.02.12
XOR Queries of a Subarray  (0) 2025.02.12
Count the Number of Consistent Strings  (0) 2025.02.12
Minimum Bit Flips to Convert Number  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

XOR Queries of a Subarray

알고리즘 2025. 2. 12. 08:54

Leetcode Problem:

Summary

  • Given an array of positive integers and queries where each query is a range, compute the XOR of elements in the range for each query.

Approach

  • The approach is to first compute the XOR of all elements in the array and then for each query, compute the XOR of the elements in the range by XORing the element at the end of the range with the XOR of the elements up to the second last element in the range.

Complexity

  • O(n + q) where n is the size of the array and q is the number of queries

Explain

  • The solution first computes the XOR of all elements in the array by iterating over the array and XORing each element with the previous one
  • Then for each query, it computes the XOR of the elements in the range by XORing the element at the end of the range with the XOR of the elements up to the second last element in the range
  • This is done by accessing the element at the end of the range and the element at the position before the end of the range, and XORing them
  • The result is then added to the answer vector.

Solution Code:


class Solution {
public:
    vector xorQueries(vector& arr, vector>& queries) {
        vector ans;
        for(int i = 1 ; i < arr.size(); i++){
            arr[i] = arr[i] ^ arr[i-1];
        }
        for(int i = 0 ; i < queries.size(); i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            ans.push_back(arr[b] ^ (a-1 < 0 ? 0 : arr[a-1]));
        }
        return ans;
    }
};

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

K-th Smallest in Lexicographical Order  (0) 2025.02.12
Largest Number  (0) 2025.02.12
Count the Number of Consistent Strings  (0) 2025.02.12
Minimum Bit Flips to Convert Number  (0) 2025.02.12
Insert Greatest Common Divisors in Linked List  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

Count the Number of Consistent Strings

알고리즘 2025. 2. 12. 08:51

Leetcode Problem:

Summary

  • Count the number of consistent strings in a given array of words, where a string is consistent if all characters appear in the allowed string.

Approach

  • The solution uses a boolean array to track the presence of each character in the allowed string
  • It then iterates over each word in the array, checking if each character in the word is present in the allowed string
  • If a character is not present, the word is not consistent and is not counted.

Complexity

  • O(n*m), where n is the length of the allowed string and m is the maximum length of a word in the array.

Explain

  • The solution works by first initializing a boolean array `allow` of size 256, where each index corresponds to a lowercase English letter
  • It then iterates over each character in the allowed string, setting the corresponding index in the `allow` array to `true`
  • The solution then iterates over each word in the array, checking if each character in the word is present in the `allow` array
  • If a character is not present, the word is not consistent and is not counted
  • The number of consistent words is then returned.

Solution Code:


class Solution {
public:
    bool allow[256];
    int countConsistentStrings(string allowed, vector& words) {
        for(int i = 0 ; i < allowed.size(); i++){
            allow[allowed[i]] = true;
        }
        int ans = 0;
        for(int i = 0 ; i < words.size(); i++){
            bool success = true;
            for(int j = 0; j < words[i].size(); j++){
                if (!allow[words[i][j]]){
                    success = false;
                    break;
                }
            }
            if (success){
                ans++;
            }
        }
        return ans;
    }
};

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

Largest Number  (0) 2025.02.12
XOR Queries of a Subarray  (0) 2025.02.12
Minimum Bit Flips to Convert Number  (0) 2025.02.12
Insert Greatest Common Divisors in Linked List  (0) 2025.02.12
Spiral Matrix IV  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

Minimum Bit Flips to Convert Number

알고리즘 2025. 2. 12. 08:48

Leetcode Problem:

Summary

  • Find the minimum number of bit flips to convert start to goal.

Approach

  • This solution works by continuously dividing both start and goal by 2 (using bitwise right shift) until they are both 0
  • In each iteration, it checks if the least significant bit of start and goal are different
  • If they are, it increments the answer by 1
  • This is because flipping the least significant bit of either start or goal (or both) requires one bit flip.

Complexity

  • O(log min(start, goal))

Explain

  • The time complexity of this solution is O(log min(start, goal)) because in each iteration, the size of start and goal is halved
  • The space complexity is O(1) because only a constant amount of space is used.

Solution Code:


class Solution {
public:
    int minBitFlips(int start, int goal) {
        int ans = 0;
        while(!(start == 0 && goal == 0)){
            if((start & 1) != (goal & 1)) ans++;
            start >>= 1;
            goal >>= 1;
        }
        return ans;
    }
};

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

XOR Queries of a Subarray  (0) 2025.02.12
Count the Number of Consistent Strings  (0) 2025.02.12
Insert Greatest Common Divisors in Linked List  (0) 2025.02.12
Spiral Matrix IV  (0) 2025.02.12
Linked List in Binary Tree  (0) 2025.02.12
블로그 이미지

짬뽕얼큰하게

,

Insert Greatest Common Divisors in Linked List

알고리즘 2025. 2. 12. 08:45

Leetcode Problem:

Summary

  • Inserting greatest common divisors between adjacent nodes in a linked list

Approach

  • The approach used is to traverse the linked list and for each pair of adjacent nodes, calculate the greatest common divisor (GCD) using the Euclidean algorithm
  • A new node is then inserted between the two nodes with the calculated GCD
  • The process is repeated until all nodes have been processed.

Complexity

  • O(n), where n is the number of nodes in the linked list

Explain

  • The provided C++ code defines a solution to the problem
  • The `_gcd` function calculates the GCD of two numbers using the Euclidean algorithm
  • The `insertGreatestCommonDivisors` function traverses the linked list, calculates the GCD of each pair of adjacent nodes, and inserts a new node with the calculated GCD between the two nodes
  • The process is repeated until all nodes have been processed, resulting in a linked list with the GCDs inserted between adjacent nodes.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int _gcd(int a, int b){
        if(a % b == 0) return b;
        return _gcd(b, a%b);
    }
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* ptr = head;
        while(ptr->next != nullptr){
            int a = ptr->val;
            int b = ptr->next->val;
            ListNode* newNode = new ListNode(_gcd(a, b), ptr->next);
            ptr->next = newNode;
            ptr = newNode->next;
        }
        return head;
    }
};

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

Count the Number of Consistent Strings  (0) 2025.02.12
Minimum Bit Flips to Convert Number  (0) 2025.02.12
Spiral Matrix IV  (0) 2025.02.12
Linked List in Binary Tree  (0) 2025.02.12
Remove All Occurrences of a Substring  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Spiral Matrix IV

알고리즘 2025. 2. 12. 08:41

Leetcode Problem:

Summary

  • Generate a spiral matrix from a linked list of integers

Approach

  • Use a spiral traversal algorithm to fill the matrix in a clockwise direction

Complexity

  • O(R*C + N)

Explain

  • The solution uses a spiral traversal algorithm to fill the matrix in a clockwise direction
  • The algorithm starts from the top-left corner of the matrix and moves in a spiral pattern until all elements have been visited
  • The matrix is represented as a 2D vector, and the algorithm uses two arrays `dy` and `dx` to keep track of the direction of movement
  • The `R` and `C` variables represent the number of rows and columns in the matrix, respectively
  • The algorithm also uses a `while` loop to iterate through the linked list and fill the matrix with the corresponding values
  • The remaining empty spaces in the matrix are filled with -1.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector> ans;
    
    int R, C;
    vector> spiralMatrix(int m, int n, ListNode* head) {
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        R = m;
        C = n;

        vector> ans(m, vector(n, -1));
        int r = 0;
        int c = 0;
        int dir = 0;
        while(head){
            ans[r][c] = head->val;
            int nr = r + dy[dir];
            int nc = c + dx[dir];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C || ans[nr][nc] != -1){
                dir = (dir + 1) %4;
                nr = r + dy[dir];
                nc = c + dx[dir];
            }
            r = nr;
            c = nc;
            head = head->next;
        }
        return ans;
    }
};

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

Minimum Bit Flips to Convert Number  (0) 2025.02.12
Insert Greatest Common Divisors in Linked List  (0) 2025.02.12
Linked List in Binary Tree  (0) 2025.02.12
Remove All Occurrences of a Substring  (0) 2025.02.11
Delete Nodes From Linked List Present in Array  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

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

티스토리툴바