Three Split

Description:

You have a long strip of paper with integers written on it in a single line from left to right. You wish to cut the paper into exactly three pieces such that each piece contains at least one integer and the sum of the integers in each piece is the same. You cannot cut through a number, i.e. each initial number will unambiguously belong to one of the pieces after cutting. How many ways can you do it?

It is guaranteed that the sum of all elements in the array is divisible by 3.

Example

For a = [0, -1, 0, -1, 0, -1], the output should be
threeSplit(a) = 4.

Input/Output

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

    Constraints:
    5 ≤ a.length ≤ 104,
    -108 ≤ a[i] ≤ 108.

  • [output] integer

    It’s guaranteed that for the given test cases the answer always fits signed 32-bit integer type.

Tests:
Solution(Swift):

func threeSplit(a: [Int]) -> Int {
    var sum = 0
    for num in a {
        sum += num
    }
    var temp = sum%3
    if !(temp==0) {
        return 0
    }
    sum /= 3
    var cut1 = 0, cut2 = 0, count = 0
    var sum1 = 0, sum2 = 0
    for cut1 in 0..<a.count-2 {
        sum1 += a[cut1]
        if sum1 == sum {
            sum2 = 0
            for cut2 in (cut1 + 1)..<a.count-1 {
                sum2 += a[cut2]
                if sum2 == sum {
                    count += 1
                }
            }
        }
    }
    return count
}

Ada Number

Description:

Consider two following representations of a non-negative integer:

  1. A simple decimal integer, constructed of a non-empty sequence of digits from 0 to 9;
  2. An integer with at least one digit in a base from 2 to 16 (inclusive), enclosed between # characters, and preceded by the base, which can only be a number between 2 and 16 in the first representation. For digits from 10 to 15 characters a, b, …, f and A, B, …, F are used.

Additionally, both representations may contain underscore (_) characters; they are used only as separators for improving legibility of numbers and can be ignored while processing a number.

Your task is to determine whether the given string is a valid integer representation.

Note: this is how integer numbers are represented in the programming language Ada.

Example

  • For line = "123_456_789", the output should be
    adaNumber(line) = true;
  • For line = "16#123abc#", the output should be
    adaNumber(line) = true;
  • For line = "10#123abc#", the output should be
    adaNumber(line) = false;
  • For line = "10#10#123ABC#", the output should be
    adaNumber(line) = false;
  • For line = "10#0#", the output should be
    adaNumber(line) = true;
  • For line = "10##", the output should be
    adaNumber(line) = false.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] string lineA non-empty string.

    Constraints:
    2 ≤ line.length ≤ 30.

  • [output] booleantrue if line is a valid integer representation, false otherwise.

Tests:
Solution(C#):

bool adaNumber(string line) {
  bool atLeastOneDigit = false;
  if (line[line.Length - 1] == '#') {
    int i = 0;
    int baseChar = 0;
    while (line[i] != '#' && baseChar <= 16) {
      if (line[i] != '_') {
        if ('0' <= line[i] && line[i] <= '9') {
          baseChar = baseChar * 10 + (line[i] - '0');
        } else {
          return false;
        }
      }
      i++;
    }
    if (baseChar < 2 || baseChar > 16) {
      return false;
    }
    i++;
    while (i < line.Length - 1) {
      if (line[i] != '_') {
        var digit = -1;
        if ('a' <= line[i] && line[i] <= 'f') {
          digit = line[i] - 'a' + 10;
        }
        if ('A' <= line[i] && line[i] <= 'F') {
          digit = line[i] - 'A' + 10;
        }
        if ('0' <= line[i] && line[i] <= '9') {
          digit = line[i] - '0';
        }
        if (0 <= digit && digit < baseChar) {
          atLeastOneDigit = true;
        } else {
          return false;
        }
      }
      i++;
    }
  } else {
    foreach (char i in line) {
      if (i != '_') {
        if ('0' <= i && i <= '9') {
          atLeastOneDigit = true;
        } else
          return false;
      }
    }
  }
  return atLeastOneDigit;
}

Are Similar?

Description:

Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements.

Given two arrays, check whether they are similar.

Example

  • For A = [1, 2, 3] and B = [1, 2, 3], the output should be
    areSimilar(A, B) = true;
  • For A = [1, 2, 3] and B = [2, 1, 3], the output should be
    areSimilar(A, B) = true;
  • For A = [1, 2, 2] and B = [2, 1, 1], the output should be
    areSimilar(A, B) = false.

Input/Output

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

    Array of integers.

    Constraints:
    3 ≤ A.length ≤ 105,
    1 ≤ A[i] ≤ 1000.

  • [input] array.integer B

    Array of integers of the same length as A.

    Constraints:
    B.length = A.length,
    1 ≤ B[i] ≤ 1000.

  • [output] boolean

    true if A and B are similar, false otherwise.

Tests:
Solutions:

bool areSimilar(int[] A, int[] B) {
    List<int>b=new List<int>(B);
    List<int>a=new List<int>(A);
    bool isSwapped=false;
    if(A.Length>=3 && A.Length<=100000 &&
      A.Length==B.Length) {        
        for(int i=0;i<A.Length;i++) {
            int aI =A[i];
            int bI =B[i];
            
            if(1<=aI && aI<=1000 &&
              1<=bI && bI<=1000) {
                int f = b.IndexOf(aI,i);
                if(f==i)
                    continue;
                else if(f>i) {
                    if(!isSwapped) {
                        int e = i;
                        while(e<a.Count) {
                            e=a.IndexOf(bI,e);
                            System.Console.WriteLine(e);
                            if(e<=i)
                                break;
                            if(b[e]==a[i])
                                break;
                            else
                                e++;
                        } 
                        
                        if(e>i && e<b.Count) {
                            b[e]=b[i];
                            isSwapped=true;
                        }
                        else
                            return false;    
                    }
                    else
                        return false;    
                }
                else
                    return false;
            }
            else
                throw new ArgumentOutOfRangeException();
        }
        return true;
    }
    else
        throw new ArgumentOutOfRangeException();
}

Integer to String of Fixed Width

Description:

Given a positive integer number and a certain length, we need to modify the given number to have a specified length. We are allowed to do that either by cutting out leading digits (if the number needs to be shortened) or by adding 0s in front of the original number.

Example

  • For number = 1234 and width = 2, the output should be
    integerToStringOfFixedWidth(number, width) = "34";
  • For number = 1234 and width = 4, the output should be
    integerToStringOfFixedWidth(number, width) = "1234";
  • For number = 1234 and width = 5, the output should be
    integerToStringOfFixedWidth(number, width) = "01234".

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer number

    A non-negative integer.

    Constraints:
    0 ≤ number ≤ 105.

  • [input] integer width

    A positive integer representing the desired length.

    Constraints:
    1 ≤ width ≤ 5.

  • [output] string

    The modified version of number as described above.

Tests:
Solutions:

string integerToStringOfFixedWidth(int number, int width) {
    StringBuilder result = new StringBuilder();

    for (int i = 0; i < width; i++) {
        result.Append("0");
    }

    int position = width - 1;
    while (number != 0 && position >= 0) {
        System.Console.WriteLine(number);
        result[position] = (number % 10).ToString()[0];
        number /= 10;
        position--;
    }

    return result.ToString();
}

 

Elections Winners

Description:

Elections are in progress!

Given an array of the numbers of votes given to each of the candidates so far, and an integer k equal to the number of voters who haven’t cast their vote yet, find the number of candidates who still have a chance to win the election.

The winner of the election must secure strictly more votes than any other candidate. If two or more candidates receive the same(maximum) number of votes, assume there is no winner at all.

Example

For votes = [2, 3, 5, 2] and k = 3, the output should be
electionsWinners(votes, k) = 2.

Input/Output

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

    A non-empty array of non-negative integers. Its ith element denotes the number of votes cast for the ith candidate.

    Constraints:
    4 ≤ votes.length ≤ 105,
    0 ≤ votes[i] ≤ 104.

  • [input] integer k

    The number of voters who haven’t cast their vote yet.

    Constraints:
    0 ≤ k ≤ 105.

  • [output] integer

Tests:
Solutions:

int electionsWinners(int[] votes, int k) {
    int ma = 0;
    for (int i = 0; i < votes.Length; i++)
        ma = Math.Max(ma, votes[i]);
    int cnt = 0;
    for (int i = 0; i < votes.Length; i++)
        if (votes[i] + k > ma)
            cnt++;
    if (cnt == 0) {
        for (int i = 0; i < votes.Length; i++)
            if (votes[i] == ma)
                cnt++;
        if (cnt > 1)
            cnt = 0;
    }
    return cnt;
}

Timed Reading

Description:

Timed Reading is an educational tool used in many schools to improve and advance reading skills. A young elementary student has just finished his very first timed reading exercise. Unfortunately he’s not a very good reader yet, so whenever he encountered a word longer than maxLength, he simply skipped it and read on.

Help the teacher figure out how many words the boy has read by calculating the number of words in the text he has read, no longer than maxLength.
Formally, a word is a substring consisting of English letters, such that characters to the left of the leftmost letter and to the right of the rightmost letter are not letters.

Example

For maxLength = 4 and
text = "The Fox asked the stork, 'How is the soup?'",
the output should be
timedReading(maxLength, text) = 7.

The boy has read the following words: "The", "Fox", "the", "How", "is", "the", "soup".

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer maxLength

    A positive integer, the maximum length of the word the boy can read.

    Constraints:
    1 ≤ maxLength ≤ 10.

  • [input] string text

    A non-empty string of English letters and punctuation marks.

    Constraints:
    3 ≤ text.length ≤ 110.

  • [output] integer

    The number of words the boy has read.

Tests:
Solutions:

int timedReading(int maxLength, string text) {
    string[] words = text.Split(' ');
    int count=0;
    if(words.Length==0)
        words[0]=text;
    foreach(string word in words) {
        Regex r = new Regex("(?:[^a-zA-Z ]|(?<=[.'\"])s)", 
            RegexOptions.IgnoreCase | 
            RegexOptions.CultureInvariant |
            RegexOptions.Compiled);
        string trimmedWord =r.Replace(word, String.Empty);
        
        if(trimmedWord.Length<=maxLength && trimmedWord.Length>0)
            count++;
    }
    return count;
}

Switch Lights

Description:

N candles are placed in a row, some of them are initially lit. For each candle from the1st to the Nth the following algorithm is applied: if the observed candle is lit then states of this candle and all candles before it are changed to the opposite. Which candles will remain lit after applying the algorithm to all candles in the order they are placed in the line?

Example

For a = [1, 1, 1, 1, 1], the output should be
switchLights(a) = [0, 1, 0, 1, 0].

Check out the image below for better understanding:

Input/Output

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

    Initial situation – array of zeros and ones of length N, 1 means that the corresponding candle is lit.

    Constraints:
    5 ≤ a.length ≤ 5000.

  • [output] array.integer

    Situation after applying the algorithm – array in the same format as input with the same length.

Tests:
Solutions:

int[] switchLights(int[] a) {
    for (int i = 0; i < a.Length; i++) {
        if (a[i] == 1) {
            for (int j = 0; j <= i; j++) {
                a[j] = 1 - a[j];
            }
        }
    }
    return a;
}