CodeFights - Comfortable Numbers - Solution

Problem

Let's say that number a feels comfortable with number b if a ≠ b and b lies in the segment [a - s(a), a + s(a)], where s(x) is the sum of x's digits.
How many pairs (a, b) are there, such that a < b, both a and b lie on the segment [L, R], and each number feels comfortable with the other?
Example
For L = 10 and R = 12, the output should be
comfortableNumbers(L, R) = 2.
Here are all values of s(x) to consider:
  • s(10) = 1, so 10 is comfortable with 9 and 11;
  • s(11) = 2, so 11 is comfortable with 9, 10, 12 and 13;
  • s(12) = 3, so 12 is comfortable with 9, 10, 11, 13, 14 and 15.
Thus, there are 2 pairs of numbers comfortable with each other within the segment [10; 12]: (10, 11) and (11, 12).
Input/Output
  • [time limit] 500ms (cpp)
  • [input] integer L
    Guaranteed constraints:
    1 ≤ L ≤ R ≤ 1000.
  • [input] integer R
    Guaranteed constraints:
    1 ≤ L ≤ R ≤ 1000.
  • [output] integer
    The number of pairs satisfying all the above conditions.

Solution

The problem is pretty straightforward due to constraints of the problem. We need to look at 1000C2 pairs in the worst case. We look at all the pairs in the range [L, R] and check if the pair of integers in a given pair are comfortable to each other.

Code

int digitSum(int n){
    int _sum = 0;
    
    while (n){
        _sum += (n%10);
        n = n/10;
    }
    
    return _sum;
}

int comfortableNumbers(int L, int R) {
    int total_pairs = 0;
    
    for(int i=L; i<=R; i++){
        for(int j=i+1; j<=R; j++){
            int s_a = digitSum(i);
            int s_b = digitSum(j);
            if (j>= (i-s_a) and j<= (i+s_a) and 
                  i>= (j-s_b) and i<= (j+s_b)
               ) {
                total_pairs++;
            }
        }
    }
    return total_pairs;
}
17 comments:

CodeFights - Count Black Cells - Solution

Problem

Imagine a white rectangular grid of n rows and m columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let's paint the grid in two colors according to the following rules:
  • A cell is painted black if it has at least one point in common with the diagonal;
  • Otherwise, a cell is painted white.
Count the number of cells painted black.

Solution

Here is the code that solves the problem:
 
int gcd(int n, int m){
    while (m) {
        int temp = n;
        n = m;
        m = temp%m;
    }
    
    return n;
}
int countBlackCells(int n, int m) {
    if (n == m) return (n + 2*(n-1));
    if (n == 1 or m==1 ) return n*m;
    return n + m -gcd(n, m) + (gcd(n, m)-1)*2;
}

1 comment:

Merge overlapping intervals in Python - Leetcode 56. Merge Intervals

Problem:
Given a set of intervals in arbitrary order, merge overlapping intervals to produce a list of intervals which are mutually exclusive.

Eg:
 [ [1,4], [1,5] ] --> [ [1,5] ]
[[6,8], [1,9], [2,4], [4,7]] -> [ [1, 9] ]

Approach:

This approach to solving the problem borrows the idea of how balanced parentheses are checked. We first flatten the given list of intervals into individual bounds and associate each of them with an integer which signifies whether that bound is lower or an upper bound. We then sort this list according to the starting/ending integer and then the bound i.e for the same starting/ending integer, lower bound should come before the upper bound. We use a stack and keep pushing items onto it as long as the integer represents a lower bound and pop items if it is an upper bound. If at any point of time, the stack gets empty, then we have found one merged interval.

Eg:

[ (6, 8), (1, 9), (2, 4), (4, 7) ]

Step 1: Flatten the list

[ (6, 8), (1, 9), (2, 4), (4, 7) ] -> [(6, 0), (8, 1), (1, 0), (9, 1), (2, 0), (4, 1), (4, 0), (7, 1)]

0/1 of a tuple in the resulting list tells whether it is a lower/upper bound respectively.

Step 2: Sort the flattened list

[(1, 0), (2, 0), (4, 0), (4, 1), (6, 0), (7, 1), (8, 1), (9, 1)]

Step 3: Go through the list item by item and merge as explained above.

Code:


66 comments:
Subscribe to: Posts (Atom)