Problem 19: Counting Sundays

*Difficulty: Easy

Problem:

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)?

How to solve:

First , we need a class that represent a date

private static class Date implements Comparable<Date>{

public static final int[] dayInMonth = {0,31,28,31,30,31,30,31,31,30,31,30,31};

public static final String[] monthNames = {“”,“Jan”,“Feb”,“Mar”,“Apr”,“May”,

“jun”,“Jul”,“Aug”,“Sep”,“Oct”,“Nov”,“Dec”};

publicintday;

publicintmonth;

publicintyear;

publicDate(int day, int month, int year) {

this.year = (year >= 1900 ) ? year : 1900;

this.month = (month>=1&&month<=12) ? month : 1;

if(day == 29 && month == 2 && isLeapYear(this.year)) {

this.day = day;

} else {

this.day = day>=1 && day <= dayInMonth[month] ? day : 1;

}

}

publicDate() {

this.day = 1;

this.month = 1;

this.year = 1900;

}

privatestaticbooleanisLeapYear(int year) {

return (year%4==0&&year%100!=0) || (year%400==0);

}

private Date increaseOneDay() {

Date result = new Date(this.day, this.month, this.year);

if(result.day < dayInMonth[result.month]) {

result.day += 1;

} else {

if((result.day == 28 || result.day==29) && result.month == 2 && isLeapYear(result.year)) {

if(result.day < 29)

result.day += 1;

else {

result.day = 1;

result.month += 1;

}

} else {

result.day = 1;

if(result.month < 12) {

result.month += 1;

} else {

result.month = 1;

result.year += 1;

}

}

}

returnresult;

}

@Override

publicintcompareTo(Date d) {

int yearCompare = this.year d.year;

int monthCompare = this.month d.month;

int dayCompare = this.day d.day;

return yearCompare != 0 ? yearCompare : monthCompare != 0 ? monthCompare : dayCompare;

}

@Override

public String toString() {

returnthis.day + ” “ + monthNames[this.month] + ” “ + this.year;

}

}

This class with the increaseOneDay method that can be used to solve this problem. We loop from the start day, 1/1/1901 , which is Tuesday, until we reach 31/12/2000. And we check if date.day == 1 and that date is Sunday (or equal 6) .

You got the idea.

Solution took 26 ms.

Implementation:

import java.util.Hashtable;

import java.util.Scanner;

public class Prob19 {

privatestaticclassDate implements Comparable<Date>{

public static final int[] dayInMonth = {0,31,28,31,30,31,30,31,31,30,31,30,31};

public static final String[] monthNames = {“”,“Jan”,“Feb”,“Mar”,“Apr”,“May”,

“jun”,“Jul”,“Aug”,“Sep”,“Oct”,“Nov”,“Dec”};

publicintday;

publicintmonth;

publicintyear;

publicDate(int day, int month, int year) {

this.year = (year >= 1900 ) ? year : 1900;

this.month = (month>=1&&month<=12) ? month : 1;

if(day == 29 && month == 2 && isLeapYear(this.year)) {

this.day = day;

} else {

this.day = day>=1 && day <= dayInMonth[month] ? day : 1;

}

}

publicDate() {

this.day = 1;

this.month = 1;

this.year = 1900;

}

privatestaticbooleanisLeapYear(int year) {

return (year%4==0&&year%100!=0) || (year%400==0);

}

private Date increaseOneDay() {

Date result = new Date(this.day, this.month, this.year);

if(result.day < dayInMonth[result.month]) {

result.day += 1;

} else {

if((result.day == 28 || result.day==29) && result.month == 2 && isLeapYear(result.year)) {

if(result.day < 29)

result.day += 1;

else {

result.day = 1;

result.month += 1;

}

} else {

result.day = 1;

if(result.month < 12) {

result.month += 1;

} else {

result.month = 1;

result.year += 1;

}

}

}

returnresult;

}

@Override

publicintcompareTo(Date d) {

int yearCompare = this.year d.year;

int monthCompare = this.month d.month;

int dayCompare = this.day d.day;

return yearCompare != 0 ? yearCompare : monthCompare != 0 ? monthCompare : dayCompare;

}

@Override

public String toString() {

returnthis.day + ” “ + monthNames[this.month] + ” “ + this.year;

}

}

privatestaticHashtable<Date, String> dayInWeekOfDate = new Hashtable<>();

public static final String[] dayInWeek = {“Monday”,“Tuesday”,“Wednesday”,“Thursday”,

“Friday”,“Sartuday”,“Sunday”};

privatestaticfinalintNUMBER_OF_DAY_IN_WEEK = 7;

publicstaticvoidmain(String[] args) {

Scannerinput = new Scanner(System.in);

int startDay,startMonth,startYear;

int endDay, endMonth,endYear;

int dayOfWeek;

System.out.println(“Enter start date(d,m,yyyy): “);

startDay= input.nextInt();

startMonth= input.nextInt();

startYear= input.nextInt();

System.out.println(“The day of week of start day:(0-6): “);

dayOfWeek= input.nextInt();

System.out.println(“Enter end date(d,m,yyyy): “);

endDay= input.nextInt();

endMonth= input.nextInt();

endYear= input.nextInt();

Date date = new Date(startDay, startMonth, startYear);

int count = dayOfWeek;

dayInWeekOfDate.put(date, dayInWeek[count++]);

int countSundayOnFirstMonth = 0;

Date endDate = new Date(endDay,endMonth,endYear);

while(true) {

date = date.increaseOneDay();

dayInWeekOfDate.put(date, dayInWeek[count]);

if(date.day == 1 && (count+1) == 7) {

++countSundayOnFirstMonth;

}

count = (count+1)%NUMBER_OF_DAY_IN_WEEK;

if(date.compareTo(endDate) == 0) {

System.out.println(countSundayOnFirstMonth);

break;

}

}

}

}

Input/Output:

Enter start date(d,m,yyyy):

1 1 1901

The day of week of start day:(0-6):

1

Enter end date(d,m,yyyy):

31 12 2000

171

Advertisements