Squares Sum Minimization

Link

https://codefights.com/tournaments/gL4JNbYY5yuXpnNMF/C

Description

Given a sorted array of integers A, find such an integer x that ∑(A[i] – x)2 over all i has the minimum possible value. If there are several possible answers, output the smallest one.

Example

For A = [2, 4, 7], the output should be
squaresSumMinimization(A) = 4.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer AA non-empty array of integers, sorted in ascending order.

    Constraints:
    1 ≤ A.length ≤ 5,
    -25 ≤ A[i] ≤ 25.

  • [output] integer

Solution(C#)

int squaresSumMinimization(int[] A) {
var minimum = Int32.MaxValue;
  var element = 0;
  for (var i = -25; i < 26; i++) {
    var sum = 0;
    for (var j = 0; j < A.Length; j++) {
      sum += (int)Math.Pow(A[j] - i,2);
    }
    if (sum < minimum) {
      minimum = sum;
      element = i;
    }
  }
  return element;
}

Rectangle Rotation

Description:

A rectangle with sides equal to even integers a and b is drawn on the Cartesian plane. Its center (the intersection point of its diagonals) coincides with the point (0, 0), but the sides of the rectangle are not parallel to the axes; instead, they are forming 45 degree angles with the axes.

How many points with integer coordinates are located inside the given rectangle (including on its sides)?

Example

For a = 6 and b = 4, the output should be
rectangleRotation(a, b) = 23.

The following picture illustrates the example, and the 23 points are marked green.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer aA positive even integer.

    Constraints:
    2 ≤ a ≤ 50.

  • [input] integer bA positive even integer.

    Constraints:
    2 ≤ b ≤ 50.

  • [output] integerThe number of inner points with integer coordinates.

Tests:

Explain:

a17b87ea843a52e8ce44a35109bca772af4ba2631

therefore 4 blue edges make 45 degrees angles so the 4 edges are corresponding 4 expressions:

  • f1(x,y) = x + y + u = 0
  • f2(x,y) = x + y – u = 0
  • f3(x,y) = x – y + v = 0
  • f4(x,y) = x – y – v = 0

therefore point O(0,0) is in the rectangle, So

  • f1(0,0) = u > 0
  • f2(0,0) = -u < 0
  • f3(0,0) = v > 0
  • f4(0,0) = -v < 0

If 1 point P(x,y) is in the rectangle then demands 4 conditions:

  • f1(x,y) = x + y + u > 0
  • f2(x,y) = x + y – u < 0
  • f3(x,y) = x – y + v > 0
  • f4(x,y) = x – y – v < 0

Mean: |x + y| < u and |x – y| < v

Now finding u, v:

Draws more 2 red lines perpendicular with 2 edges of the rectangle, we have right angled triangles, So u = a/sqrt(2), v = b/sqrt(2).
Solution(C#):


int rectangleRotation(int a, int b) {
   int r = 0;
	for (int x = -a - b; x &amp;amp;amp;amp;amp;lt;= a + b; x++) {
		for (int y = -a - b; y &amp;amp;amp;amp;amp;lt;= a + b; y++) {
			if (2 * (x - y) * (x - y) &amp;amp;amp;amp;amp;lt;= a * a &amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp; 2 * (x + y) * (x + y) &amp;amp;amp;amp;amp;lt;= b * b)
                r++;
		}
	}
	return r;
}

Crossword Formation

Description:

You’re a crossword fanatic, and have finally decided to try and create your own. However, you also love symmetry and good design, so you come up with a set of rules they should follow:

  • the crossword must contain exactly four words;
  • these four words should form four pairwise intersections;
  • all words must be written either left-to-right or top-to-bottom;
  • the area of the rectangle formed by empty cells inside the intersections isn’t equal to zero.

Given 4 words, find the number of ways to make a crossword following the above-described rules. Note that two crosswords which differ by rotation are considered different.

Example

For words = ["crossword", "square", "formation", "something"], the output should be
crosswordFormation(words) = 6.

The six crosswords can be formed as shown below:

  f                         f                             f
  o                     c r o s s w o r d     c r o s s w o r d
c r o s s w o r d           r   o                   q     r
  m   q                     m   m                   u     m
  a   u            ;  s q u a r e          ;        a     a
  t   a                     t   t                   r     t
  i   r                     i   h             s o m e t h i n g
s o m e t h i n g           o   i                         o
  n                         n   n                         n
                                g                               
                                                              
    c         s               s                                      
f o r m a t i o n       c     q               c         s          
    o         m         r     u               r         o      
    s q u a r e       f o r m a t i o n       o         m            
    s         t    ;    s     r            ;  s q u a r e                  
    w         h         s o m e t i n g       s         t         
    o         i         w                     w         h     
    r         n         o                   f o r m a t i o n            
    d         g         r                     r         n         
                        d                     d         g             

Input/Output

  • [time limit] 20000ms (swift)
  • [input] array.string words

    An array of distinct strings, the words you need to use in your crossword.

    Constraints:
    words.length = 4,
    3 ≤ words[i].length < 15.

  • [output] integer

    The number of ways to make a correct crossword of the desired formation.

Tests:
Solution(Swift):

func crosswordFormation(words: [String]) -> Int {
    var count = 0
    for i in 0..<4 {
        let a = words[i].characters.map({String($0)})
        for a1 in 0..<(a.count - 1) {
            for j in 0..<4 {
                if j == i {
                    continue
                }
                let b = words[j].characters.map({String($0)})
                for b2 in 1..<b.count {
                    if b[b2] != a[a1] {
                        continue
                    }
                    for b1 in 0..<(b2 - 1) {
                        for k in 0..<4 {
                            if k == i || k == j {
                                continue
                            }
                            let c = words[k].characters.map({String($0)})
                            let d = words[6 - i - j - k].characters.map({String($0)})
                            if b2 - b1 >= d.count {
                                continue
                            }
                            for c1 in 0..<(c.count - 1) {
                                if c[c1] != b[b1] {
                                    continue
                                }
                                for c2 in (c1 + 2)..<c.count {
                                    let a2 = a1 + (c2 - c1)
                                    if a2 >= a.count {
                                        continue
                                    }
                                    for d1 in 0..<d.count {
                                        if d[d1] != c[c2] {
                                            continue
                                        }
                                        let d2 = d1 + (b2 - b1)
                                        if d2 >= d.count {
                                            break
                                        }
                                        if a[a2] != d[d2] {
                                            continue
                                        }
                                        count += 1
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return count
}

Construct Square

Description:

Given a string consisting of lowercase English letters, find the largest square which can be obtained by reordering its characters and replacing them with digits (leading zeros are not allowed) where same characters always map to the same digits and different characters always map to different digits.

If there is no solution, return -1.

Example

  • For s = "ab", the output should be
    constructSquare(s) = 81;
  • For s = "zzz", the output should be
    constructSquare(s) = -1.

    There are no 3-digit square numbers with identical digits.

  • For s = "aba", the output should be
    constructSquare(s) = 900.

    It can be obtained after reordering the initial string into "baa".

Input/Output

  • [time limit] 3000ms (cs)
  • [input] string s

    Constraints:
    2 ≤ s.length < 10.

  • [output] integer

Tests:
Solution(C#):

int constructSquare(string s) {
    List<int> letterCnt = new List<int>();
    for (int i = 0; i < 26; i++) {
        letterCnt.Add(0);
    }
    for (int i = 0; i < s.Length; i++) {
        letterCnt[s[i]-'a']++;
    }
  
    letterCnt.Sort();
    int best = -1;

    int minNumber = (int)Math.Pow(10, s.Length - 1);
    for (int k = (int)Math.Floor(Math.Sqrt(minNumber)); k * k < minNumber * 10; k++) {
        int n = k * k;
        List<int> digitCnt = new List<int>();
        for (int i = 0; i < 26; i++) {
            digitCnt.Add(0);
        }
        while (n > 0) {
            digitCnt[n % 10]++;
            n = n / 10;
        }
    
        digitCnt.Sort();
        if (Enumerable.SequenceEqual(letterCnt, digitCnt)) {
            best = k * k;
        }
    }
    return best;
}


Numbers Grouping

Description:

You are given an array of integers that you want distribute between several groups. The first group should contain numbers from 1 to 104, the second should contain those from 104 + 1 to 2 * 104, …, the 100th one should contain numbers from 99 * 104 + 1to 106 and so on.

All the numbers will then be written down in groups to the text file in such a way that:

  • the groups go one after another;
  • each non-empty group has a header which occupies one line;
  • each number in a group occupies one line.

Calculate how many lines the resulting text file will have.

Example

For a = [20000, 239, 10001, 999999, 10000, 20566, 29999], the output should be
numbersGrouping(a) = 11.

The numbers can be divided into 4 groups:

  • 239 and 10000 go to the 1st group (1 ... 104);
  • 10001 and 20000 go to the second 2nd (104 + 1 ... 2 * 104);
  • 20566 and 29999 go to the 3rd group (2 * 104 + 1 ... 3 * 104);
  • groups from 4 to 99 are empty;
  • 999999 goes to the 100th group (99 * 104 + 1 ... 106).

Thus, there will be 4 groups (i.e. four headers) and 7 numbers, so the file will occupy 4 + 7 = 11 lines.

Input/Output

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

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

  • [output] integer

    The number of lines needed to store the grouped numbers.

Tests:
Solution(C#):

int numbersGrouping(int[] a) {
    List<int> nGroupList = new List<int>();
    for(int i=0;i<100000;i++ {
        nGroupList.Add(0);
    }
    int len = a.Length;
    for(int i=0;i<len;i++) {
        int index = (a[i]-1)/10000;
        if(nGroupList[index]==0)
            nGroupList[index]+=2;
        else
            nGroupList[index]++;
    }
    
    return nGroupList.Sum();
}

Different Squares

Description:

Given a rectangular matrix containing only digits, calculate the number of different 2 × 2 squares in it.

Example

For

matrix = [[1, 2, 1],
          [2, 2, 2],
          [2, 2, 2],
          [1, 2, 3],
          [2, 2, 1]]

the output should be
differentSquares(matrix) = 6.

Here are all 6 different 2 × 2 squares:

  • 1 2
    2 2
  • 2 1
    2 2
  • 2 2
    2 2
  • 2 2
    1 2
  • 2 2
    2 3
  • 2 3
    2 1

Input/Output

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

    Constraints:
    1 ≤ matrix.length ≤ 100,
    1 ≤ matrix[i].length ≤ 100,
    0 ≤ matrix[i][j] ≤ 9.

  • [output] integer

    The number of different 2 × 2 squares in matrix.

Tests:
Solution(C#):

int differentSquares(int[][] matrix) {
    int lenM = matrix.Length;
    List<Rectangle> rects = new List<Rectangle>();
    if(lenM>=1 && lenM<=100) {
        for(int i=0;i<lenM-1;i++) {
            int lenI = matrix[i].Length;
            for(int j=0;j<lenI-1;j++) {
                Rectangle rect = GetRectangle(matrix, i, j);
                if(!rects.Contains(rect)) {
                    rects.Add(rect);
                }
            }
        }
        return rects.Count;
    }
    else
        throw new ArgumentOutOfRangeException();
}
Rectangle GetRectangle(int[][] matrix, int i, int j) {
    return new Rectangle(matrix[i][j],matrix[i][j+1],matrix[i+1][j],matrix[i+1][j+1]);
}
class Rectangle : IEquatable<Rectangle> {
    public Rectangle(int x11, int x21, int x12, int x22) {
        this.X11 = x11;
        this.X12 = x12;
        this.X21 = x21;
        this.X22 = x22;
    }
    public int X11 { get; set; }
    public int X12 { get; set; }
    public int X21 { get; set; }
    public int X22 { get; set; }

    public bool Equals(Rectangle other) {
        if (this.X11 == other.X11 && this.X12 == other.X12
            && this.X21 == other.X21 && this.X22 == other.X22) {
            return true;
        }
        else {
            return false;
        }
    }
}

 

Most Frequent Digit Sum

Description:

A step(x) operation works like this: it changes a number x into x - s(x), where s(x)is the sum of x‘s digits. You like applying functions to numbers, so given the number n, you decide to build a decreasing sequence of numbers: n, step(n), step(step(n)), etc., with 0 as the last element.

Building a single sequence isn’t enough for you, so you replace all elements of the sequence with the sums of their digits (s(x)). Now you’re curious as to which number appears in the new sequence most often. If there are several answers, return the maximal one.

Example

  • For n = 88, the output should be
    mostFrequentDigitSum(n) = 9.

    • Here is the first sequence you built: 88, 72, 63, 54, 45, 36, 27, 18, 9, 0;
    • And here is s(x) for each of its elements: 16, 9, 9, 9, 9, 9, 9, 9, 9, 0.

    As you can see, the most frequent number in the second sequence is 9.

  • For n = 8, the output should be
    mostFrequentDigitSum(n) = 8.

    • At first you built the following sequence: 8, 0
    • s(x) for each of its elements is: 8, 0

    As you can see, the answer is 8 (it appears as often as 0, but is greater than it).

Input/Output

  • [time limit] 20000ms (swift)
  • [input] integer n

    Constraints:
    1 ≤ n ≤ 105,

  • [output] integer

    The most frequent number in the sequence s(n), s(step(n)), s(step(step(n))), etc.

Tests:
Solution(Swift):

func mostFrequentDigitSum(n: Int) -> Int {
    var m = n, counter: [Int: Int] = [:]
    while m > 0 {
        let reduce = s(m)
        if counter[reduce] != nil {
            counter[reduce] = 1 + counter[reduce]!
        } else {
            counter[reduce] = 1
        }
        m = m - reduce
    }
    var max = 0, maxCount = 0
    for (key, value) in counter {
        if value > maxCount {
            max = key
            maxCount = value
        } else if value == maxCount {
            if key > max {
                max = key
            }
        }
    }
    return max
}

func s(x: Int) -> Int {
    var y = x, result = 0
    while y > 0 {
        result += y % 10
        y /= 10
    }
    return result
}