Sum of each element raised to (prime-1) % prime
Given an array arr[] and a positive integer P where P is prime and none of the elements of array are divisible by P. Find sum of all the elements of the array raised to the power P – 1 i.e. arr[0]P – 1 + arr[1]P – 1 + … + arr[n – 1]P – 1 and print the result modulo P.
Examples:
Input: arr[] = {2, 5}, P = 3
Output: 2
22 + 52 = 29 and 29 % 3 = 2
Input: arr[] = {5, 6, 8}, P = 7
Output: 3
Approach: This problem is a direct application of Fermats’s Little Theorem, a(P-1) = 1 (mod p) where a is not divisible by P. Since, none of the elements of array arr[] are divisible by P, each element arr[i] will give the value 1 with the given operation.
Therefore, our answer will be 1 + 1 + … (upto n(size of array)) = n.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> #include <vector> using namespace std; // Function to return the required sum int getSum(vector< int > arr, int p) { return arr.size(); } // Driver code int main() { vector< int > arr = { 5, 6, 8 }; int p = 7; cout << getSum(arr, p) << endl; return 0; } // This code is contributed by Rituraj Jain |
Java
// Java implementation of the approach public class GFG { // Function to return the required sum public static int getSum( int arr[], int p) { return arr.length; } // Driver code public static void main(String[] args) { int arr[] = { 5 , 6 , 8 }; int p = 7 ; System.out.print(getSum(arr, p)); } } |
Python3
# Python3 implementation of the approach # Function to return the required sum def getSum(arr, p) : return len (arr) # Driver code if __name__ = = "__main__" : arr = [ 5 , 6 , 8 ] p = 7 print (getSum(arr, p)) # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; public class GFG{ // Function to return the required sum public static int getSum( int []arr, int p) { return arr.Length; } // Driver code static public void Main (){ int []arr = { 5, 6, 8 }; int p = 7; Console.WriteLine(getSum(arr, p)); } //This Code is contributed by akt_mit } |
PHP
<?php // PHP implementation of the approach // Function to return the required sum function getSum( $arr , $p ) { return count ( $arr ); } // Driver code $arr = array ( 5, 6, 8 ); $p = 7; echo (getSum( $arr , $p )); // This code is contributed // by Sach_Code ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the required sum function getSum(arr, p) { return arr.length; } let arr = [ 5, 6, 8 ]; let p = 7; document.write(getSum(arr, p)); </script> |
3
Time Complexity: O(1)
Auxiliary Space: O(1)