Given a function f(n) = (13 + 23 + 33 + … + n3), the task is to find the value of f(n) mod 4 for a given positive integer ‘n’.
Examples
Input: n=6
Output: 1
Explanation: f(6) = 1+8+27+64+125+216=441
f(n) mod 4=441 mod 4 = 1Input: n=4
Output: 0
Explanation: f(4)=1+8+27+64 = 100
f(n) mod 4 =100 mod 4 = 0
While solving this problem, you might directly compute (13 + 23 + 33 + … + n3) mod 4. But this requires O(n) time. We can use direct formula for sum of cubes, but for large ‘n’ we may get f(n) out of range of long long int.
Here’s an efficient O(1) solution:
From division algorithm we know that every integer can be expressed as either 4k, 4k+1, 4k+2 or 4k+3.
Now,
(4k)3 = 64k3 mod 4 = 0.
(4k+1)3 = (64k3 + 48k2 + 12k+1) mod 4 = 1
(4k+2)3 = (64k3+64k2+48k+8) mod 4 = 0
(4k+3)3 = (64k3+184k2 + 108k+27) mod 4 = 3
and ((4k)3+(4k+1)3+(4k+2)3+(4k+1)4) mod 4 = (0 + 1+ 0 + 3) mod 4 = 0 mod 4
Now let x be the greatest integer not greater than n divisible by 4. So we can easily see that,
(13+23+33…..+x3) mod 4=0.
Now,
- if n is a divisor of 4 then x=n and f(n) mod 4 =0.
- Else if n is of the form 4k + 1, then x= n-1. So, f(n)= 13 + 23 + 33…..+ x3+n3) mod 4 = n^3 mod 4 = 1
- Similarly if n is of the form 4k+2 (i.e x=n-2), we can easily show that f(n) = ((n-1)3+n3) mod 4=(1 + 0) mod 4 = 1
- And if n is of the form 4k+3 (x=n-3). Similarly, we get f(n) mod 4 = ((n-2)3+(n-1)3+n3) mod 4 = (1+0+3) mod 4 = 0
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// function for obtaining the value of f(n) mod 4int fnMod(int n){ // Find the remainder of n when divided by 4 int rem = n % 4; // If n is of the form 4k or 4k+3 if (rem == 0 || rem == 3) return 0; // If n is of the form 4k+1 or 4k+2 else if (rem == 1 || rem == 2) return 1;}// Driver codeint main(){ int n = 6; cout << fnMod(n); return 0;} |
Java
// Java implementation of the approachimport java .io.*;class GFG { // function for obtaining the value of f(n) mod 4static int fnMod(int n){ // Find the remainder of n when divided by 4 int rem = n % 4; // If n is of the form 4k or 4k+3 if (rem == 0 || rem == 3) return 0; // If n is of the form 4k+1 or 4k+2 else if (rem == 1 || rem == 2) return 1; return 0;}// Driver code public static void main (String[] args) { int n = 6; System.out.print( fnMod(n)); }}//This code is contributed // by shs |
Python 3
# Python3 implementation of# above approach# function for obtaining the # value of f(n) mod 4 def fnMod(n) : # Find the remainder of n # when divided by 4 rem = n % 4 # If n is of the form 4k or 4k+3 if (rem == 0 or rem == 3) : return 0 # If n is of the form # 4k+1 or 4k+2 elif (rem == 1 or rem == 2) : return 1# Driver code if __name__ == "__main__" : n = 6 print(fnMod(n))# This code is contributed # by ANKITRAI1 |
C#
// C# implementation of the approach using System; class GFG { // function for obtaining the value of f(n) mod 4static int fnMod(int n){ // Find the remainder of n when divided by 4 int rem = n % 4; // If n is of the form 4k or 4k+3 if (rem == 0 || rem == 3) return 0; // If n is of the form 4k+1 or 4k+2 else if (rem == 1 || rem == 2) return 1; return 0;} // Driver code public static void Main () { int n = 6; Console.Write( fnMod(n)); }} |
PHP
<?php// PHP implementation of the approach// function for obtaining the// value of f(n) mod 4function fnMod($n){ // Find the remainder of n // when divided by 4 $rem = $n % 4; // If n is of the form 4k or 4k+3 if ($rem == 0 or $rem == 3) return 0; // If n is of the form 4k+1 or 4k+2 else if ($rem == 1 or $rem == 2) return 1;}// Driver code$n = 6;echo fnMod($n);// This code is contributed // by anuj_67..?> |
Javascript
<script>// Javascript implementation of the approach// Function for obtaining the value// of f(n) mod 4function fnMod(n){ // Find the remainder of n // when divided by 4 var rem = n % 4; // If n is of the form 4k or 4k+3 if (rem == 0 || rem == 3) return 0; // If n is of the form 4k+1 or 4k+2 else if (rem == 1 || rem == 2) return 1; return 0;}// Driver Codevar n = 6;document.write(fnMod(n));// This code is contributed by Kirti</script> |
1
Time Complexity: O(1) because constant operations are used.
Auxiliary Space: O(1) because no extra space is used.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
