A pair of string s and r are called magical if for every index i the character of s is less than r i.e. s[i] < r[i]. The task is to count number of pairs of strings possible of length L. Since this value can be large, give answer modulo 109.
Note: The string contains only lowercase English alphabets.
Examples:
Input: L = 1
Output: 325
Since the length of the strings required is 1.
If s = “a” then r can be any one of “b”, “c”, “d”, … “z” (25 Possibilities)
If s = “b” then r can be any one of “c”, “d”, “e”, … “z” (24 Possibilities)
….
If s = “y” then r can only be “z” (1 Possibilities)
s cannot be “z” as it is the maximum lowercase character.
Hence total possibilities are 1 + 2 + 3 + … + 25 = 325Input: L = 2
Output: 105625
Approach: For L = 1, total possibilities are 325.
For L = 2, total possibilities are 3252.
Total possibilities for any value of L will be 325L.
Since this value can be large, print the answer modulo 109.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Iterative Function to calculate (x^y)%p in O(log y)int power(int x, unsigned int y, int p){ // Initialize result int res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // Y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Driver Codeint main(){ int L = 2, P = pow(10, 9); int ans = power(325, L, P); cout << ans << "\n"; return 0;} |
Java
// Java implementation of the approachclass GFG{ // Iterative Function to calculate (x^y)%p in O(log y) static int power(int x, int y, int p) { // Initialize result int res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) { res = (res * x) % p; } // Y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Driver Code public static void main(String[] args) { int L = 2; int P = (int) Math.pow(10, 9); int ans = power(325, L, P); System.out.println(ans); }}// This code has been contributed by 29AjayKumar |
Python3
# Python implementation of the approach # Iterative Function to calculate (x^y)%p in O(log y)def power(x, y, p): # Initialize result res = 1; # Update x if it is >= p x = x % p; while (y > 0): # If y is odd, multiply x with result if (y %2== 1): res = (res * x) % p; # Y must be even now y = y >> 1; # y = y/2 x = (x * x) % p; return res; # Driver CodeL = 2; P = pow(10, 9);ans = power(325, L, P);print(ans);# This code contributed by Rajput-Ji |
C#
// C# implementation of the approach using System;class GFG { // Iterative Function to calculate (x^y)%p in O(log y) static int power(int x, int y, int p) { // Initialize result int res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) { res = (res * x) % p; } // Y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Driver Code public static void Main() { int L = 2; int P = (int) Math.Pow(10, 9); int ans = power(325, L, P); Console.WriteLine(ans); } } // This code is contributed by AnkitRai01 |
PHP
<?php// PHP implementation of the approach// Iterative Function to calculate (x^y)%p in O(log y)function power($x, $y, $p){ // Initialize result $res = 1; // Update x if it is >= p $x = $x % $p; while ($y > 0) { // If y is odd, multiply x with result if ($y & 1) $res = ($res * $x) % $p; // Y must be even now $y = $y >> 1; // y = y/2 $x = ($x * $x) % $p; } return $res;}// Driver Code$L = 2;$P = pow(10, 9);$ans = power(325, $L, $P);echo $ans , "\n";// This code is contributed by ajit.?> |
Javascript
<script> // Javascript implementation of the approach // Iterative Function to calculate (x^y)%p in O(log y) function power(x, y, p) { // Initialize result let res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) { res = (res * x) % p; } // Y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } let L = 2; let P = Math.pow(10, 9); let ans = power(325, L, P); document.write(ans); </script> |
105625
Time Complexity: O(log (L))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
