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

Advertisements

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

Add Border

Description:

Given a rectangular matrix of characters, add a border of asterisks(*) to it.

Example

For

picture = ["abc",
           "ded"]

the output should be

addBorder(picture) = ["*****",
                      "*abc*",
                      "*ded*",
                      "*****"]

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.string picture

    A non-empty array of non-empty equal-length strings.

    Constraints:
    1 ≤ picture.length ≤ 5,
    1 ≤ picture[i].length ≤ 5.

  • [output] array.string

    The same matrix of characters, framed with a border of asterisks of width 1.

Tests:
Solutions:

string[] addBorder(string[] picture) {
    List<string> answer = new List<string>();
    string decoratedRow =string.Empty;
    for (var i = 0; i < picture[0].Length + 2; i++) {
        decoratedRow += "*";
    }
    answer.Add(decoratedRow);
    for (var i = 0; i < picture.Length; i++) {
        string row = "*";
        for (var j = 0; j < picture[0].Length; j++) {
          row += picture[i][j];
        }
        row += "*";
        answer.Add(row);
      }
      answer.Add(decoratedRow);
      return answer.ToArray();
}

Minimal Number of Coins

Description:

You find yourself in Bananaland trying to buy a banana. You are super rich so you have an unlimited supply of banana-coins, but you are trying to use as few coins as possible.

The coin values available in Bananaland are stored in a sorted array coins. coins[0] = 1, and for each i (0 < i < coins.length) coins[i] is divisible by coins[i - 1]. Find the minimal number of banana-coins you’ll have to spend to buy a banana given the banana’s price.

Example

For coins = [1, 2, 10] and price = 28, the output should be
minimalNumberOfCoins(coins, price) = 6.

You have to use 10 twice, and 2 four times.

Input/Output

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

    The coin values available in Bananaland.

    Constraints:
    1 ≤ coins.length ≤ 5,
    1 ≤ coins[i] ≤ 120.

  • [input] integer price

    A positive integer representing the price of the banana.

    Constraints:
    8 ≤ price ≤ 250.

  • [output] integer

    The minimal number of coins you can use to buy the banana.

Tests:
Solutions:

int minimalNumberOfCoins(int[] coins, int price) {
    int r = 0;
    int l=coins.Length-1;
    while(price>0) {
        while(price<coins[l]) {
            l-=1;
            if(l<0)
                break;
        }
        price -= coins[l];
        r+=1;
    }
    return r;
}