Labels

Project Euler #19: Counting Sundays

Question
You are given the following information, but you may prefer to do some research for yourself.
  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Answer : 171

Hacker Rank Problem

Solution

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
import java.util.*;

public class Solution {

    private static int SUNDAY = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            // input
            long[][] dateArray = new long[2][3];
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 3; j++) {
                    dateArray[i][j] = in.nextLong();
                }
            }
            // begin
            adjust(dateArray);
            //
            long ak = 0;
            while (true) {
                if (dateArray[0][2] == 1) {
                    if (verify(dateArray[0][0], dateArray[0][1], dateArray[0][2])) {
                        ak++;
                    }
                }
                // set date
                dateArray[0][2] = 1;
                // month plus 1
                dateArray[0][1]++;
                if (dateArray[0][1] > 12) {
                    dateArray[0][1] = 1;
                    dateArray[0][0]++;
                }
                if (overDate(dateArray)) {
                    break;
                }
            }
            System.out.println(ak);
        }
        in.close();
    }

    /**
     * check if dateArray[0] is later than dateArray[1]
     * @param dateArray
     * @return
     */
    private static boolean overDate(long[][] dateArray) {
        if (dateArray[0][0] > dateArray[1][0]) {
            return true;
        } else if (dateArray[0][0] == dateArray[1][0]) {
            if (dateArray[0][1] > dateArray[1][1]) {
                return true;
            } else if (dateArray[0][1] == dateArray[1][1]) {
                if (dateArray[0][2] > dateArray[1][2])
                    return true;
            }
        }
        return false;
    }

    /**
     * let a[0] be earlier than a[1]
     * @param dateArray
     */
    private static void adjust(long[][] dateArray) {
        if (overDate(dateArray)) {
            exchange(dateArray);
        }
    }

    /**
     * exchange two input date
     * @param dateArray
     */
    private static void exchange(long[][] dateArray) {
        long[] tmp = new long[3];
        tmp = dateArray[1];
        dateArray[1] = dateArray[0];
        dateArray[0] = tmp;
    }

    private static boolean verify(long year, long month, long day) {
        // w=(y + (y / 4) + (c / 4) - (2 * c) + ((26 * (month + 1)) / 10) + day - 1) % 7
//        long sourceY = year;
//        long sourceM = month;
        if (month < 3) {
            month += 12;
            year -= 1;
        }
        long c = year / 100;
        long y = year % 100;
        int w = (int) ((y + (y / 4) + (c / 4) - (2 * c) + ((26 * (month + 1)) / 10) + day - 1) % 7);
        boolean t = w == SUNDAY;
//        if (t) {
//            System.out.println(sourceY  + "-" + sourceM + "-" + day);
//        }
        return t;
    }
}
Labels:

Comments

Post a Comment

Popular Posts