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

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
}

Curious Clock

Description:

Benjamin recently bought a digital clock at a magic trick shop. The seller never told Ben what was so special about it, but mentioned that one day Benjamin would be faced with a surprise.

Indeed, the clock did surprise Benjamin: without warning, at someTime the clock suddenly started going in the opposite direction! Unfortunately, Benjamin has an important meeting very soon, and knows that at leavingTime he should leave the house so as to not be late. Ben spent all his money on the clock, so has to figure out what time his clock will show when it’s time to leave.

Given the someTime at which the clock started to go backwards, find out what time will be shown on the curious clock at leavingTime.

For your convenience, here is the list of months lengths (from January to December, respectively):

  • Months lengths: 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31.

Please, note that in leap years February has 29 days.

Example

For someTime = "2016-08-26 22:40" and leavingTime = "2016-08-29 10:00", the output should be
curiousClock(someTime, leavingTime) = "2016-08-24 11:20".

There are 2 days, 11 hours and 20 minutes till the meeting. Thus, the clock will show 2016-08-24 11:20 at the leavingTime.

Input/Output

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

    The time at which the clock started going backwards. It is guaranteed that the time is correct and is not earlier than the midnight of January the 1st, 1970.

    The time is given in the format "YYYY-MM-DD HH:MM".

  • [input] string leavingTime

    The time at which Ben will have to leave for the meeting in the same format as someTime and with the same constraints.
    It is guaranteed that leavingTime is later than someTime, but not later than the year of 2035.

  • [output] string

    The time Ben’s curious clock will show when it’s time to leave in the same format as leavingTime and someTime. It is guaranteed that it will be not earlier than the midnight of January the 1st, 1970.

Tests:
Solution(C#):

string curiousClock(string someTime, string leavingTime) {
    DateTime lt = DateTime.Parse(leavingTime);
    DateTime st = DateTime.Parse(someTime);
    TimeSpan ts = lt.Subtract(st);
    DateTime rt = st.Subtract(ts);
    return rt.ToString("yyyy-MM-dd HH:mm");
}

 

Day Of Week

Description:
Tests:
Solution(C#):

int dayOfWeek(string birthdayDate) {
    DateTime date=DateTime.Parse(birthdayDate);
    bool isLeap = date.Day==29 && date.Month==2;
    DayOfWeek dow = date.DayOfWeek;
    int count=1,day=date.Day;
    for(int i=1;i<100;i++){
        date = date.AddYears(1);
        if(isLeap &&DateTime.IsLeapYear(date.Year))
            date = date.AddDays(1);
        if(dow==date.DayOfWeek && day==date.Day){
            break;
        }
        count++;
    }
    return count;
}

 

Video Part

Description:

You have been watching a video for some time. Knowing the total video duration find out what portion of the video you have already watched.

Example

For part = "02:20:00" and total = "07:00:00", the output should be
videoPart(part, total) = [1, 3].

You have watched 1 / 3 of the whole video.

Input/Output

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

    A string of the following format "hh:mm:ss" representing the time you have been watching the video.

  • [input] string total

    A string of the following format "hh:mm:ss" representing the total video duration.

  • [output] array.integer

    An array of the following format [a, b] (where a / b is a reduced fraction).

Tests:
Solution(Java):

int[] videoPart(String part, String total) {
    class Helper {
            int getSeconds(String time) {
                int h = Integer.parseInt(time.substring(0, 2)),
                        m = Integer.parseInt(time.substring(3, 5)),
                        s = Integer.parseInt(time.substring(6, 8));
                return h * 60 * 60 + m * 60 + s;
            }

            int gcd(int a, int b) {
                while (a > 0) {
                    int tmp = a;
                    a = b % a;
                    b = tmp;
                }
                return b;
            }
    }
    
    Helper h = new Helper();

    int partTime = h.getSeconds(part);
    int totalTime = h.getSeconds(total);
    int divisor = h.gcd(partTime, totalTime);
    return new int[]{partTime / divisor, totalTime / divisor};
}

 

Valid Time

Description:

Check if the given string is a correct time representation of the 24-hour clock.

Example

  • For time = "13:58", the output should be
    validTime(time) = true;
  • For time = "25:51", the output should be
    validTime(time) = false;
  • For time = "02:76", the output should be
    validTime(time) = false.

Input/Output

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

    A string representing time in HH:MM format. It is guaranteed that the first two characters, as well as the last two characters, are digits.

  • [output] boolean

    true if the given representation is correct, false otherwise.

Tests:
Solution(Java):

boolean validTime(String time) {
    class Helper {
        int charToInt(char symbol) {
        return symbol - '0';
        }
    }
    Helper h = new Helper();

    int hours = h.charToInt(time.charAt(0)) * 10 + h.charToInt(time.charAt(1)),
        minutes = h.charToInt(time.charAt(3)) * 10 + h.charToInt(time.charAt(4));

    if (hours < 24 && minutes < 60) {
        return true;
    }
    return false;
}

 

Chess Knight Moves

Description:

Given a position of a knight on the standard chessboard, find the number of different moves the knight can perform.

The knight can move to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally away from it. The complete move therefore looks like the letter L. Check out the image below to see all valid moves for a knight piece that is placed on one of the central squares.

Example

  • For cell = "a1", the output should be
    chessKnightMoves(cell) = 2.

  • For cell = "c2", the output should be
    chessKnightMoves(cell) = 6.

Input/Output

  • [time limit] 3000ms (java)
  • [input] string cell

    String consisting of 2 letters – coordinates of the knight on an 8 × 8 chessboard in chess notation.

  • [output] integer

Tests:
Solution(Java):

int chessKnightMoves(String cell) {
    int x = cell.charAt(0) % 97,
    y = +cell.charAt(1) - '0' - 1;
    int c = 0;
    for (int dx = -2; dx <= 2; dx++)
        for (int dy = -2; dy <= 2; dy++) {
            if (Math.abs(dx * dy) == 2)
                if (isValid(x + dx, y + dy))
                    c++;
        }
    return c;
}
private static boolean isValid(int x, int y) {
    return x >= 0 && x <= 7 && y >= 0 && y <= 7;
}