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;
}


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
}

Number Of Clans

Description:

Let’s call two integers A and B friends if each integer from the array divisors is a divisor of both A and B or neither A nor B. If two integers are friends, they are said to be in the same clan. How many clans are the integers from 1 to k, inclusive, broken into?

Example

For divisors = [2, 3] and k = 6, the output should be
numberOfClans(divisors, k) = 4.

The numbers 1 and 5 are friends and form a clan, 2 and 4 are friends and form a clan, and 3 and 6 do not have friends and each is a clan by itself. So the numbers 1 through 6 are broken into 4 clans.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer divisorsA non-empty array of positive integers.Constraints:
    2 ≤ divisors.length < 10,
    1 ≤ divisors[i] ≤ 10.
  • [input] integer kA positive integer.Constraints:
    5 ≤ k ≤ 10.
  • [output] integer

Tests:
Solution(C#):

int numberOfClans(int[] divisors, int k) {
    List<int> clans = new List<int>(){1};
    for (int i = 2; i <= k; i++)
    {
        bool shouldAdd = true;
        foreach(int clan in clans) {
            if (isFriend(divisors, clan, i)) {
                shouldAdd = false;
                break;
            }
        }
        if (shouldAdd) {
            clans.Add(i);
        }
    }
    return clans.Count;
}
bool isFriend(int[] divisors, int a, int b) {
    for (int i = 0; i < divisors.Length; i++)
        if (!(a % divisors[i] == 0 && b % divisors[i] == 0)
                && !(a % divisors[i] != 0 && b % divisors[i] != 0))
            return false;
    return true;
}

Is Substitution Cipher?

Description:

A ciphertext alphabet is obtained from the plaintext alphabet by means of rearranging some characters. For example "bacdef...xyz" will be a simple ciphertext alphabet where a and b are rearranged.

A substitution cipher is a method of encoding where each letter of the plaintext alphabet is replaced with the corresponding (i.e. having the same index) letter of some ciphertext alphabet.

Given two strings, check whether it is possible to obtain them from each other using some (possibly, different) substitution ciphers.

Example

  • For string1 = "aacb" and string2 = "aabc", the output should be
    isSubstitutionCipher(string1, string2) = true.

    Any ciphertext alphabet that starts with acb... would make this transformation possible.

  • For string1 = "aa" and string2 = "bc", the output should be
    isSubstitutionCipher(string1, string2) = false.

Input/Output

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

    A string consisting of lowercase characters.

    Constraints:
    1 ≤ string1.length ≤ 10.

  • [input] string string2

    A string consisting of lowercase characters of the same length as string1.

    Constraints:
    string2.length = strin1.length.

  • [output] boolean

Tests:
Solution:

bool isSubstitutionCipher(string string1, string string2) {
    Dictionary<char,char>codes1=new Dictionary<char,char>();
    Dictionary<char,char>codes2=new Dictionary<char,char>();
    for(int i=0;i<string1.Length;i++) {
        char c1 = string1[i];
        char c2 = string2[i];
        if(codes1.ContainsKey(c1)) {
            if(c2!=codes1[c1])
                return false;
        }
        else {
            codes1.Add(c1,c2);
        }
        if(codes2.ContainsKey(c2)) {
            if(c1!=codes2[c2])
                return false;
        }
        else {
            codes2.Add(c2,c1);
        }
    }
    return true;
}

Strings Construction

Description:

How many strings equal to A can be constructed using letters from the stringB? Each letter can be used only once and in one string only.

Example

For A = "abc" and B = "abccba", the output should be
stringsConstruction(A, B) = 2.

We can construct 2 strings A with letters from B.

Input/Output

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

    String to construct, A contains only lowercase English letters.

    Constraints:
    3 ≤ A.length ≤ 10.

  • [input] string B

    String containing needed letters, B contains only lowercase English letters.

    Constraints:
    3 ≤ B.length ≤ 50.

  • [output] integer

Tests:
Solution:

int stringsConstruction(string A, string B) {
    int count=0;
    int index=0;
    bool found = true;
    while(B.Length>0) {
        for(int i=0;i<A.Length;i++) {
            var regex = new Regex(Regex.Escape(""+A[i]));
            if(B.Contains(""+A[i]))
                B = regex.Replace(B, "", 1);
            else {
                found = false;
                break;
            }
        }
        if(found)
            count++;
        else
            break;
    }
    return count;
}