Find whether a day fall under the GEEK year
The Beginner living in the Geekland follow a particular type of calendar. The calendar is such that on a normal year it contains N days. Every Mth year on Geekland is known as the “GEEK” year. For example, if M = 5, then years 5, 10, 15, … are “GEEK” years. A “GEEK” year contains K additional days than a normal year i.e., it contains N + K days. Given X, The task is to determine whether the day falls in a “GEEK” year.
Examples:
Input: N = 3, M = 4, K = 1, X = 25
Output: YES
Explanation: year 1 has N = 3 days
year 2 has N = 3 days
year 3 has N = 3 days
year 4 is a “GEEK” year and has N + K = 4 days
year 5 has N = 3 days
year 6 has N = 3 days
year 7 has N = 3 days
year 8 is a “GEEK” year and has N + K = 4 days
X = 25th day falls on the third day of year 8, which is a “GEEK” year.
So, output YES.Input: N = 3, M = 5, K = 7, X = 52
Output: NO
Explanation: year 1 has N = 3 days
year 2 has N = 3 days
year 3 has N = 3 days
year 4 has N = 3 days
year 5 is a “GEEK” year and has N + K = 10 days
year 6 has N = 3 days
year 7 has N = 3 days
year 8 has N = 3 days
year 9 has N = 3 days
year 10 is a “GEEK” year and has N + K = 10 days
year 11 has N = 3 days
year 12 has N = 3 days
year 13 has N = 3 days
X = 52nd day falls on the second day of year 13, which is not a “GEEK” year.
So, output NO.
Approach: To solve the problem follow the below steps:
- Move year by year, counting the number of days.
- Check if the current year is a “GEEK” year. If X falls within this year, output YES and return.
- If X falls in a non-“GEEK” year, output NO and return.
- Utilize the pattern that every Mth year is a “GEEK” year.
- Compute the total number of days in the first M-1 years as N*(M-1).
- If X falls within this computed value, it’s not a “GEEK” year.
- The total number of days from the beginning till the first “GEEK” year is N*M+k.
- Repeat this pattern of normal years followed by a “GEEK” year.
Implementation of the above approach.
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; bool is_Geek_Year( int N, int M, int K, int X) { int dayCount = 0; // Total no. of days before // GEEK year while (dayCount <= X) { dayCount += N * (M - 1); // If X falls under any day which // is before GEEK year if (X <= dayCount) // Then return false return false ; // Total no. of days including GEEK year dayCount += N + K; // If X falls under under this value // then it will be present in the GEEK // year because we have already // checked for normal years if (X <= dayCount) return true ; // The loop will run again and again for // next set of normal years followed by // GEEK year X can fall either in // normal year or GEEK year } return false ; } // Driver code int main() { // Testcase1 int N = 3, M = 4, K = 1, X = 25; // Function call if (is_Geek_Year(N, M, K, X)) cout << "YES\n"; else cout << "NO\n"; // Testcase2 N = 3, M = 5, K = 7, X = 52; // Function call if (is_Geek_Year(N, M, K, X)) cout << "YES\n"; else cout << "NO\n"; return 0; } |
Java
import java.io.*; class GFG { static boolean is_Geek_Year( int N, int M, int K, int X) { int dayCount = 0 ; while (dayCount <= X) { dayCount += N * (M - 1 ); // total no. of days // before GEEK year if (X <= dayCount) // if X falls under any day // which is before GEEK year return false ; // then return false dayCount += N + K; // total no. of days // including GEEK year // if X falls under under this value // then it will be present in the GEEK year // because we have already checked for normal // years if (X <= dayCount) return true ; // The loop will run again and again for next // set of normal years followed by GEEK year X // can fall either in normal year or GEEK year } return false ; } public static void main(String[] args) { int N = 3 , M = 4 , K = 1 , X = 25 ; if (is_Geek_Year(N, M, K, X)) System.out.println("YES"); else System.out.println("NO"); N = 3 ; M = 5 ; K = 7 ; X = 52 ; if (is_Geek_Year(N, M, K, X)) System.out.println("YES"); else System.out.println("NO"); } } |
Python3
def is_Geek_Year(N, M, K, X): dayCount = 0 while (dayCount < = X): dayCount + = N * (M - 1 ) # total no. of days before GEEK year if (X < = dayCount): # if X falls under any day which is before GEEK year return False # then return false dayCount + = N + K # total no. of days including GEEK year # if X falls under under this value # then it will be present in the GEEK year # because we have already checked for normal years if (X < = dayCount): return True return False if __name__ = = "__main__": N = 3 M = 4 K = 1 X = 25 if (is_Geek_Year(N, M, K, X)): print ("YES") else : print ("NO") N = 3 M = 5 K = 7 X = 52 if (is_Geek_Year(N, M, K, X)): print ("YES") else : print ("NO") |
C#
// C# Implementation using System; class GFG { static bool IsGeekYear( int N, int M, int K, int X) { int dayCount = 0; while (dayCount <= X) { dayCount += N * (M - 1); // total no. of days before GEEK year if (X <= dayCount) // if X falls under any day which is before GEEK year return false ; // then return false dayCount += N + K; // total no. of days including GEEK year // if X falls under under this value then it will be present in the GEEK year // because we have already checked for normal years if (X <= dayCount) return true ; // The loop will run again and again for next set of normal years followed by GEEK year // X can fall either in normal year or GEEK year } return false ; } static void Main( string [] args) { int N = 3, M = 4, K = 1, X = 25; if (IsGeekYear(N, M, K, X)) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); N = 3; M = 5; K = 7; X = 52; if (IsGeekYear(N, M, K, X)) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code is contributed by Sakshi |
Javascript
function isGeekYear(N, M, K, X) { let dayCount = 0; // Total number of days before GEEK year while (dayCount <= X) { dayCount += N * (M - 1); // If X falls under any day which is before GEEK year if (X <= dayCount) { // Then return false return false ; } // Total number of days including GEEK year dayCount += N + K; // If X falls under this value then it will be present in the GEEK year because we have already checked for normal years if (X <= dayCount) { return true ; } // The loop will run again and again for the next set of normal years followed by GEEK year. X can fall either in normal year or GEEK year. } return false ; } // Driver code function main() { // Testcase 1 let N = 3, M = 4, K = 1, X = 25; // Function call if (isGeekYear(N, M, K, X)) { console.log( "YES" ); } else { console.log( "NO" ); } // Testcase 2 N = 3; M = 5; K = 7; X = 52; // Function call if (isGeekYear(N, M, K, X)) { console.log( "YES" ); } else { console.log( "NO" ); } } main(); // This code is contributed by rambabuguphka |
YES NO
Time Complexity: In the worst case, it may take O(X) time which may be very high for larger inputs.
Auxillary space: O(1)
Efficient Approach: To solve the problem follow the below idea:
The above approach repeatedly checks whether X falls under normal years or a GEEK year. But we need not check for every set of normal years and GEEK years to arrive at the conclusion. Instead, we can use some maths to solve our problem and reduce the complexity.
Steps to solve the problem:
- Let a = N * M + K be the total number of days till the first GEEK year.
- Let b = N * (M -1) be the total number of days in the normal years.
- Now, on dividing X with a, if the reminder turns out to be greater than b then that means X does not fall in a normal year because it is greater than the total no. of days in normal year. Which means X belongs to the GEEK year.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; bool is_Geek_Year( int N, int M, int K, int X) { // Total no. of days including the GEEK year int a = N * M + K; // Total no. of days only in normal years int b = N * (M - 1); // Calculate X%a int c = X % a; // If the reminder does not fall in normal // years then it must fall in a GEEK year if (c > b) return true ; else return false ; } // Driver code int main() { // Testcase1 int N = 3, M = 4, K = 1, X = 25; // function call if (is_Geek_Year(N, M, K, X)) cout << "YES\n"; else cout << "NO\n"; // Testcase 2 N = 3, M = 5, K = 7, X = 52; // Function Call if (is_Geek_Year(N, M, K, X)) cout << "YES\n"; else cout << "NO\n"; return 0; } |
Java
import java.io.*; class GFG { static boolean is_Geek_Year( int N, int M, int K, int X) { int a = N * M + K; // total no. of days including // the GEEK year int b = N * (M - 1 ); // total no. of days only in // normal years int c = X % a; // calculate X%a if (c > b) // if the reminder does not fall in normal // years then it must fall in a GEEK year return true ; else return false ; } public static void main(String[] args) { int N = 3 , M = 4 , K = 1 , X = 25 ; if (is_Geek_Year(N, M, K, X)) System.out.println("YES"); else System.out.println("NO"); N = 3 ; M = 5 ; K = 7 ; X = 52 ; if (is_Geek_Year(N, M, K, X)) System.out.println("YES"); else System.out.println("NO"); } } |
Python3
def is_Geek_Year(N, M, K, X): a = N * M + K # total no. of days including the GEEK year b = N * (M - 1 ) # total no. of days only in normal years c = X % a # calculate X%a if (c > b): # if the reminder does not fall in normal # years then it must fall in a GEEK year return True else : return False if __name__ = = "__main__": N = 3 M = 4 K = 1 X = 25 if (is_Geek_Year(N, M, K, X)): print ("YES") else : print ("NO") N = 3 M = 5 K = 7 X = 52 if (is_Geek_Year(N, M, K, X)): print ("YES") else : print ("NO") |
C#
using System; public class GeekYear { public static bool IsGeekYear( int N, int M, int K, int X) { // Total no. of days including the GEEK year int a = N * M + K; // Total no. of days only in normal years int b = N * (M - 1); // Calculate X % a int c = X % a; // If the reminder does not fall in normal years then it must fall in a GEEK year if (c > b) { return true ; } else { return false ; } } public static void Main( string [] args) { // Testcase 1 int N1 = 3, M1 = 4, K1 = 1, X1 = 25; if (IsGeekYear(N1, M1, K1, X1)) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } // Testcase 2 int N2 = 3, M2 = 5, K2 = 7, X2 = 52; if (IsGeekYear(N2, M2, K2, X2)) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } |
Javascript
function isGeekYear(N, M, K, X) { // Total no. of days including the GEEK year let a = N * M + K; // Total no. of days only in normal years let b = N * (M - 1); // Calculate X % a let c = X % a; // If the reminder does not fall in normal years then it must fall in a GEEK year if (c > b) { return true ; } else { return false ; } } // Testcase 1 let N1 = 3, M1 = 4, K1 = 1, X1 = 25; if (isGeekYear(N1, M1, K1, X1)) { console.log( "YES" ); } else { console.log( "NO" ); } // Testcase 2 let N2 = 3, M2 = 5, K2 = 7, X2 = 52; if (isGeekYear(N2, M2, K2, X2)) { console.log( "YES" ); } else { console.log( "NO" ); } |
YES NO
Time Complexity: O(1)
Auxillary Space: O(1)
Contact Us