Unique Digit Products

Description:

Let’s call product(x) the product of x‘s digits. Given an array of integers a, calculate product(x) for each x in a, and return the number of distinct results you get.

Example

For a = [2, 8, 121, 42, 222, 23], the output should be
uniqueDigitProducts(a) = 3.

Here are the products of the array’s elements:

  • 2: product(2) = 2;
  • 8: product(8) = 8;
  • 121: product(121) = 1 * 2 * 1 = 2;
  • 42: product(42) = 4 * 2 = 8;
  • 222: product(222) = 2 * 2 * 2 = 8;
  • 23: product(23) = 2 * 3 = 6.

As you can see, there are only 3 different products: 2, 6 and 8.

Input/Output

  • [time limit] 20000ms (swift)
  • [input] array.integer a

    Constraints:
    1 ≤ a.length ≤ 105,
    1 ≤ a[i] ≤ 109.

  • [output] integer

    The number of different digit products in a.

Tests:
Solution(Swift):

func uniqueDigitProducts(a: [Int]) -> Int { 
    var product: Int 
    var products = [Int]()

    for i in a {
        var temp = i
        product = 1
        while (temp>0) {
            product *= temp%10
            temp /= 10
        }
        if (!products.contains(product)) {
            products.append(product)
        }
    }

    return products.count
}

 

Digit Difference Sort

Description:

Given an array of integers, sort its elements by the difference of their largest and smallest digits. In the case of a tie, that with the larger index in the array should come first.

Example

For a = [152, 23, 7, 887, 243], the output should be
digitDifferenceSort(a) = [7, 887, 23, 243, 152].

Here are the differences of all the numbers:

  • 152: difference = 5 - 1 = 4;
  • 23: difference = 3 - 2 = 1;
  • 7: difference = 7 - 7 = 0;
  • 887: difference = 8 - 7 = 1;
  • 243: difference = 4 - 2 = 2.

23 and 887 have the same difference, but 887 goes after 23 in a, so in the sorted array it comes first.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer a

    An array of integers.

    Constraints:
    0 ≤ sequence.length ≤ 104,
    1 ≤ sequence[i] ≤ 105.

  • [output] array.integer

    Array a sorted as described above.

Tests:
Solution(C#):

int[] digitDifferenceSort(int[] a) {
    var diff = a.Select((s,i) => new {s, d = different(s), i = i}).ToList();
    diff = diff.OrderBy(s => s.d).ThenByDescending(s => s.i).ToList();
    return diff.Select(item=>item.s).ToArray();
}
int different(int s){
    List<int> digits = new List<int>();
    while(s>0) {
        int m= s%10;
        digits.Add(m);
        s=s/10;
    }
    int[]temp=digits.ToArray();
    Array.Sort(temp);
    int min=temp[0];
    int max=temp[digits.Count-1];
    return max-min;
}

 

Rows Rearranging

Description:

Given a rectangular matrix of integers, check if it is possible to rearrange its rows in such a way that all its columns become strictly increasing sequences (read from top to bottom).

Example

  • For
    matrix = [[2, 7, 1], 
              [0, 2, 0], 
              [1, 3, 1]]
    

    the output should be
    rowsRearranging(matrix) = false;

  • For
    matrix = [[6, 4], 
              [2, 2], 
              [4, 3]]
    

    the output should be
    rowsRearranging(matrix) = true.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer matrix

    A 2-dimensional array of integers.

    Constraints:
    1 ≤ matrix.length ≤ 10,
    1 ≤ matrix[0].length ≤ 10,
    -300 ≤ matrix[i][j] ≤ 300.

  • [output] boolean

Tests:
Solution(Java):

boolean rowsRearranging(int[][] matrix) {
    class Helper {
        void swapRows(int row1, int row2, int[][] matrix) {
            for (int i = 0; i < matrix[0].length; i++) {
                int tmp = matrix[row1][i];
                matrix[row1][i] = matrix[row2][i];
                matrix[row2][i] = tmp;
            }
        }
    }

    Helper h = new Helper();

    for (int i = 0; i < matrix.length; i++) {
        int minIndex = i;
        for (int j = i; j < matrix.length; j++) {
            if (matrix[j][0] < matrix[minIndex][0]) {
                minIndex = j;
            }
        }
        h.swapRows(i, minIndex, matrix);
    }

    boolean answer = true;
    for (int i = 0; i < matrix[0].length; i++) {
        for (int j = 1; j < matrix.length; j++) {
            if (matrix[j][i] <= matrix[j - 1][i]) {
                answer = false;
            }
        }
    }

    return answer;
}

 

Maximum Sum

Description:

You are given an array of integers A. Range sum query is defined by a pair of non-negative integers L and R (L <= R). An output to a range sum query on the given array is the sum of all elements of A with indices from L to R inclusive.

Find an algorithm that given a list of range sum queries can rearrange the array A in such a way that the total sum of all of the query outputs is maximized.

Example

For A = [2, 1, 2] and Q = [[0, 1]], the output should be
maximumSum(A, Q) = 4.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer A

    An initial array.

    Constraints:
    2 ≤ A.length ≤ 10,
    1 ≤ A[i] ≤ 10.

  • [input] array.array.integer Q

    Array of range sum queries, each query is an array of two non-negative integers.

    Constraints:
    1 ≤ Q.length ≤ 10,
    0 ≤ Q[i][j] ≤ 10.

  • [output] integer

    Maximum possible total sum of the given range sum query outputs.

Tests:
Solution(Java):

int maximumSum(int[] A, int[][] Q) {
    int[] sumCount = new int[A.length];
    for (int i = 0; i < Q.length; i++) {
        for (int j = Q[i][0]; j <= Q[i][1]; j++) {
            sumCount[j]++;
        }
    }
    Arrays.sort(A);
    Arrays.sort(sumCount);
    int answer = 0;
    for (int i = 0; i < A.length; i++) {
        answer += A[i] * sumCount[i];
    }

    return answer;
}

 

Boxes Packing

Description:

You are given n rectangular boxes, the ith box has the length lengthi, the width widthi and the height heighti. Your task is to check if it is possible to pack all boxes into one so that inside each box there is no more than one another box (which, in turn, can contain at most one another box, and so on). More formally, your task is to check whether there is such sequence of n different numbers pi (1 ≤ pi ≤ n) that for each 1 ≤ i < n the box number pi can be put into the box number pi+1.
A box can be put into another box if all sides of the first one are less than the respective ones of the second one. You can rotate each box as you wish, i.e. you can swap its length, width and height if necessary.

Example

  • For length = [1, 3, 2], width = [1, 3, 2] and height = [1, 3, 2], the output should be
    boxesPacking(length, width, height) = true;
  • For length = [1, 1], width = [1, 1] and height = [1, 1], the output should be
    boxesPacking(length, width, height) = false;
  • For length = [3, 1, 2], width = [3, 1, 2] and height = [3, 2, 1], the output should be
    boxesPacking(length, width, height) = false.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer length

    Array of positive integers.

    Constraints:
    1 ≤ length.length ≤ 104,
    1 ≤ length[i] ≤ 2 · 104.

  • [input] array.integer width

    Array of positive integers.

    Constraints:
    width.length = length.length,
    1 ≤ width[i] ≤ 2 · 104.

  • [input] array.integer height

    Array of positive integers.

    Constraints:
    height.length = length.length,
    1 ≤ height[i] ≤ 2 · 104.

  • [output] boolean

    true if it is possible to put all boxes into one, false otherwise.

Tests:
Solution(Java):

boolean boxesPacking(int[] length, int[] width, int[] height) {
    int n = length.length;
    int[] p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    for (int it = 0; it < n; it++) {
        for (int i = 0; i < n - 1; i++) {
            int volumeF = length[p[i]] * width[p[i]] * height[p[i]];
            int volumeS = length[p[i + 1]] * width[p[i + 1]] * height[p[i + 1]];
            if (volumeF > volumeS) {
                int tmp = p[i];
                p[i] = p[i + 1];
                p[i + 1] = tmp;
            }
        }
    }
    boolean isCorrectSequence = true;
    for (int i = 0; i < n - 1; i++) {
        int pi = p[i];
        int pj = p[i + 1];
        boolean canSwap = false;
        canSwap |= (length[pi] < length[pj] &&
                width[pi] < width[pj] &&
                height[pi] < height[pj]);
        canSwap |= (length[pi] < length[pj] &&
                width[pi] < height[pj] &&
                height[pi] < width[pj]);
        canSwap |= (length[pi] < width[pj] &&
                width[pi] < length[pj] &&
                height[pi] < height[pj]);
        canSwap |= (length[pi] < width[pj] &&
                width[pi] < height[pj] &&
                height[pi] < length[pj]);
        canSwap |= (length[pi] < height[pj] &&
                width[pi] < length[pj] &&
                height[pi] < width[pj]);
        canSwap |= (length[pi] < height[pj] &&
                width[pi] < width[pj] &&
                height[pi] < length[pj]);
        isCorrectSequence &= canSwap;
    }
    return isCorrectSequence;
}

 

Sort By Length

Description:

Given an array of strings, sort them in the order of increasing lengths. If two strings have the same length, their relative order must be the same as in the initial array.

Example

For

inputArray = ["abc",
              "",
              "aaa",
              "a",
              "zz"]

the output should be

sortByLength(inputArray) = ["",
                            "a",
                            "zz",
                            "abc",
                            "aaa"]

Input/Output

  • [time limit] 3000ms (java)
  • [input] array.string inputArray

    A non-empty array of strings.

    Constraints:
    3 ≤ inputArray.length ≤ 10,
    0 ≤ inputArray[i].length ≤ 10.

  • [output] array.string

Tests:
Solution(Java):

String[] sortByLength(String[] inputArray) {
    HashMap<Integer, List<String>> inputMap = new HashMap<>();
    for (String str : inputArray) {
        if (inputMap.containsKey(str.length())) {
            List<String> vals = inputMap.get(str.length());
            vals.add(str);
        } else {
            List<String> vals = new ArrayList<>();
            vals.add(str);
            inputMap.put(str.length(), vals);
        }
    }


    String[] result = new String[inputArray.length];
    SortedSet<Integer> keys = new TreeSet<>(inputMap.keySet());
    int idx = 0;
    for (Integer key : keys) {
        for (String str : inputMap.get(key)) {
            result[idx] = str;
            idx++;
        }
    }
    return result;
}

 

Sort By Height

Description:

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees.

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be
sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer a

    If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

    Constraints:
    5 ≤ a.length ≤ 15,
    -1 ≤ a[i] ≤ 200.

  • [output] array.integer

    Sorted array a with all the trees untouched.

Tests:
Solution(C#):

int[] sortByHeight(int[] a) {
    int[] result = new int[a.Length];
    Array.Copy(a,0,result,0,a.Length);
    Array.Sort(a);
    int count=a.Where(i => i==-1).Count();
    for(int i=0;i<a.Length;i++){
        if(result[i]!=-1){
            result[i]=a[count];
            count++;
        }
    }
    return result;
}