9

Count N-length arrays of made up of elements not exceeding 2^K - 1 having maximu...

 2 years ago
source link: https://www.geeksforgeeks.org/count-n-length-arrays-of-made-up-of-elements-not-exceeding-2k-1-having-maximum-sum-and-bitwise-and-equal-to-0/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Count N-length arrays of made up of elements not exceeding 2^K – 1 having maximum sum and Bitwise AND equal to 0

  • Last Updated : 05 Aug, 2021

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: 

  • Python3
  • Javascript
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the power of n^k % p
int 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 conditions
int countArrays(int n, int k)
{
int mod = 1000000007;
// Calculating N^K
int ans = power(n, k, mod);
return ans;
}
// Driver Code
int main()
{
int n = 3, k = 5;
int ans = countArrays(n, k);
cout << ans << endl;
return 0;
}
Output: 
243

Time Complexity: O(log(K))
Auxiliary Space: O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK