Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Count Almost Equal Pairs I You are given an array nums consisting of positive integers.…

  1. User

    Count Almost Equal Pairs I You are given an array nums consisting of positive integers.

    We call two integers x and y in this problem almost equal if both integers can become equal after performing the following operation at most once:

    Choose either x or y and swap any two digits within the chosen number. Return the number of indices i and j in nums where i < j such that nums[i] and nums[j] are almost equal.

    Note that it is allowed for an integer to have leading zeros after performing an operation.

    Example 1:

    Input: nums = [3,12,30,17,21]

    Output: 2

    Explanation:

    The almost equal pairs of elements are:

    3 and 30. By swapping 3 and 0 in 30, you get 3. 12 and 21. By swapping 1 and 2 in 12, you get 21. Example 2:

    Input: nums = [1,1,1,1,1]

    Output: 10

    Explanation:

    Every two elements in the array are almost equal.

    Example 3:

    Input: nums = [123,231]

    Output: 0

    Explanation:

    We cannot swap any two digits of 123 or 231 to reach the other.

    Constraints:

    2 <= nums.length <= 100 1 <= nums[i] <= 106 give answer in this form : class Solution { public: int countPairs(vector& nums) {

    } };

  2. Assistant

    To solve this problem, you can follow this step-by-step algorithm:

    1. Understand the Operation: You can swap any two digits within one of the numbers (either x or y) exactly once to attempt to make the numbers equal. Leading zeros are allowed after swapping.

    2. Process Each Pair: For every pair of indices (i, j) where i < j, check if the numbers at those indices in the nums array (nums[i] and nums[j]) are almost equal according to the definition.

    3. Check for Equality:

      • Exact Match: If the numbers are already equal (x == y), they are almost equal.
      • Different Lengths: If the numbers have different lengths, swapping digits won't make them equal (since swapping doesn't change the length of the number).
      • Difference Check:
        • Convert both numbers to strings to compare them digit by digit.
        • Find all positions where the digits differ.
        • If the number of differing positions is exactly 2, attempt to swap those two positions in either x or y:
          • Swap in x: Swap the differing digits in x. If x becomes equal to y, they are almost equal.
          • Swap in y: Swap the differing digits in y. If y becomes equal to x, they are almost equal.
    4. Count Valid Pairs: Increment the count every time you find a pair that meets the criteria.

    Here's the implementation of the algorithm:

    class Solution {
    public:
        int countPairs(vector<int>& nums) {
            int count = 0;
            int n = nums.size();
    
            for(int i=0; i < n; ++i){
                string s_x = to_string(nums[i]);
                for(int j=i+1; j < n; ++j){
                    string s_y = to_string(nums[j]);
                    if(s_x == s_y){
                        // Numbers are equal, they are almost equal
                        count++;
                    }
                    else if(s_x.length() != s_y.length()){
                        // Can't make them equal by swapping digits (length differs)
                        continue;
                    }
                    else{
                        // Find positions where digits differ
                        vector<int> diff_indices;
                        for(int k=0; k < s_x.length(); ++k){
                            if(s_x[k] != s_y[k]){
                                diff_indices.push_back(k);
                            }
                        }
                        if(diff_indices.size() == 2){
                            // Try swapping in x
                            swap(s_x[diff_indices[0]], s_x[diff_indices[1]]);
                            if(s_x == s_y){
                                count++;
                            }
                            else{
                                // Swap back and try swapping in y
                                swap(s_x[diff_indices[0]], s_x[diff_indices[1]]); // swap back
                                swap(s_y[diff_indices[0]], s_y[diff_indices[1]]);
                                if(s_x == s_y){
                                    count++;
                                }
                            }
                            // Swap back if needed (optional as variables will be discarded)
                        }
                    }
                }
            }
            return count;
        }
    };