Given two integers N and K, the task is to find the number of N-length arrays that satisfies the following conditions:
- The sum of the array elements is maximum possible.
- For every possible value of i ( 1 ? i ? N ), the ith element should lie between 0 and 2K – 1.
- Also, Bitwise AND of all the array elements should be 0.
Note: Since, the answer can be large, so print the answer modulo 10^9?+?7.
Examples :
Input : N=2 K =2
Output : 4
Explanation : The required arrays are ( {1, 2}, {2, 1}, {0, 3}, {3, 0} )Input : N=1 K =1
Output : 1
Approach: The idea is to observe that if all the bits of all the elements in the array are 1, then the bitwise AND of all elements wont be 0 although the sum would be maximized. So for each bit, flip the 1 to 0 at each bit in at least one of the elements to make the bitwise AND equal to 0 and at the same time keeping the sum maximum. So for every bit, choose exactly one element and flip the bit there. Since there are K bits and N elements, the answer is just N^K. Follow the steps below to solve the problem:
- Define a function power(long long x, long long y, int p) and perform the following tasks:
- Initialize the variable res as 1 to store the result.
- Update the value of x as x%p.
- If x is equal to 0, then return 0.
- Iterate in a while loop till y is greater than 0 and perform the following tasks.
- If y is odd, then set the value of res as (res*x)%p.
- Divide y by 2.
- Set the value of x as (x*x)%p.
- Initialize the variable mod as 1e9+7.
- Initialize the variable ans as the value returned by the function power(N, K, mod).
- After performing the above steps, print the value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the power of n^k % pint power(long long x, unsigned int y, int p){ int res = 1; // Update x if it is more // than or equal to p x = x % p; // In case x is divisible by p; if (x == 0) return 0; 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;}// Function to count the number of// arrays satisfying required conditionsint countArrays(int n, int k){ int mod = 1000000007; // Calculating N^K int ans = power(n, k, mod); return ans;}// Driver Codeint main(){ int n = 3, k = 5; int ans = countArrays(n, k); cout << ans << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to calculate the power of n^k % pstatic int power(int x, int y, int p){ int res = 1; // Update x if it is more // than or equal to p x = x % p; // In case x is divisible by p; if (x == 0) return 0; while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) == 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Function to count the number of// arrays satisfying required conditionsstatic int countArrays(int n, int k){ int mod = 1000000007; // Calculating N^K int ans = power(n, k, mod); return ans;}// Driver Codepublic static void main (String[] args){ int n = 3, k = 5; int ans = countArrays(n, k); System.out.println(ans);}}// This code is contributed by shubhamsingh10 |
Python3
# Python3 program for the above approach# Function to calculate the power of n^k % pdef power(x, y, p): res = 1 # Update x if it is more # than or equal to p x = x % p # In case x is divisible by p; if (x == 0): return 0 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# Function to count the number of# arrays satisfying required conditionsdef countArrays(n, k): mod = 1000000007 # Calculating N^K ans = power(n, k, mod) return ans# Driver Coden = 3k = 5ans = countArrays(n, k)print(ans)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to calculate the power of n^k % pstatic int power(int x, int y, int p){ int res = 1; // Update x if it is more // than or equal to p x = x % p; // In case x is divisible by p; if (x == 0) return 0; while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) !=0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Function to count the number of// arrays satisfying required conditionsstatic int countArrays(int n, int k){ int mod = 1000000007; // Calculating N^K int ans = power(n, k, mod); return ans;}// Driver Codepublic static void Main(){ int n = 3, k = 5; int ans = countArrays(n, k); Console.Write(ans);}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approach // Function to calculate the power of n^k % p function power(x, y, p) { let res = 1; // Update x if it is more // than or equal to p x = x % p; // In case x is divisible by p; if (x == 0) return 0; 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; } // Function to count the number of // arrays satisfying required conditions function countArrays(n, k) { let mod = 1000000007; // Calculating N^K let ans = power(n, k, mod); return ans; } // Driver Code let n = 3, k = 5; let ans = countArrays(n, k); document.write(ans);// This code is contributed by Potta Lokesh </script> |
Output:
243
Time Complexity: O(log(K))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
