# Count of N-size maximum sum Arrays with elements in range [0, 2^K – 1] and Bitwise AND equal to 0

Given two positive integers **N** and **K**, the task is to find the number of arrays of size **N **such that each array element lies over the range **[0, 2 ^{K} – 1]** with the maximum sum of array element having Bitwise AND of all array elements

**0**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 2 K = 2Output:4Explanation:

The possible arrays with maximum sum having the Bitwise AND of all array element as 0 {0, 3}, {3, 0}, {1, 2}, {2, 1}. The count of such array is 4.

Input:N = 5 K = 6Output:15625

**Approach:** The given problem can be solved by observing the fact that as the Bitwise AND of the generated array should be **0**, then for each **i **in the range **[0, K – 1]** there should be at least 1 element with an **i ^{th}** bit equal to

**0**in its binary representation. Therefore, to maximize the sum of the array, it is optimal to have exactly 1 element with the

**i**bit unset.

^{th}Hence, for each of the **K** bits, there are ** ^{N}C_{1}** ways to make it unset in 1 array element. Therefore, the resultant count of an array having the maximum sum is given by

**N**.

^{K}Below is the implementation of the approach :

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the value of X to` `// the power Y` `int` `power(` `int` `x, unsigned ` `int` `y)` `{` ` ` `// Stores the value of X^Y` ` ` `int` `res = 1;` ` ` `while` `(y > 0) {` ` ` `// If y is odd, multiply x` ` ` `// with result` ` ` `if` `(y & 1)` ` ` `res = res * x;` ` ` `// Update the value of y and x` ` ` `y = y >> 1;` ` ` `x = x * x;` ` ` `}` ` ` `// Return the result` ` ` `return` `res;` `}` `// Function to count number of arrays` `// having element over the range` `// [0, 2^K - 1] with Bitwise AND value` `// 0 having maximum possible sum` `void` `countArrays(` `int` `N, ` `int` `K)` `{` ` ` `// Print the value of N^K` ` ` `cout << ` `int` `(power(N, K));` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 5, K = 6;` ` ` `countArrays(N, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `public` `class` `GFG` `{` `// Function to find the value of X to` `// the power Y` `static` `int` `power(` `int` `x, ` `int` `y)` `{` ` ` ` ` `// Stores the value of X^Y` ` ` `int` `res = ` `1` `;` ` ` `while` `(y > ` `0` `) {` ` ` `// If y is odd, multiply x` ` ` `// with result` ` ` `if` `(y%` `2` `!=` `0` `)` ` ` `res = res * x;` ` ` `// Update the value of y and x` ` ` `y = y >> ` `1` `;` ` ` `x = x * x;` ` ` `}` ` ` `// Return the result` ` ` `return` `res;` `}` `// Function to count number of arrays` `// having element over the range` `// [0, 2^K - 1] with Bitwise AND value` `// 0 having maximum possible sum` `static` `void` `countArrays(` `int` `N, ` `int` `K)` `{` ` ` ` ` `// Print the value of N^K` ` ` `System.out.println((` `int` `)(power(N, K)));` `}` `// Driver Code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `N = ` `5` `, K = ` `6` `;` ` ` `countArrays(N, K);` `}` `}` `// This code is contributed by SoumikMondal` |

## Python3

`# Python Program for the above approach` `# Function to find the value of X to` `# the power Y` `def` `power(x, y):` ` ` `# Stores the value of X^Y` ` ` `res ` `=` `1` ` ` `while` `(y > ` `0` `):` ` ` `# If y is odd, multiply x` ` ` `# with result` ` ` `if` `(y & ` `1` `):` ` ` `res ` `=` `res ` `*` `x` ` ` `# Update the value of y and x` ` ` `y ` `=` `y >> ` `1` ` ` `x ` `=` `x ` `*` `x` ` ` `# Return the result` ` ` `return` `res` `# Function to count number of arrays` `# having element over the range` `# [0, 2^K - 1] with Bitwise AND value` `# 0 having maximum possible sum` `def` `countArrays(N, K):` ` ` `# Print the value of N^K` ` ` `print` `(power(N, K))` `# Driver Code` `N ` `=` `5` `;` `K ` `=` `6` `;` `countArrays(N, K)` `# This code is contributed by gfgking` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `// Function to find the value of X to` `// the power Y` `static` `int` `power(` `int` `x, ` `int` `y)` `{` ` ` ` ` `// Stores the value of X^Y` ` ` `int` `res = 1;` ` ` `while` `(y > 0)` ` ` `{` ` ` ` ` `// If y is odd, multiply x` ` ` `// with result` ` ` `if` `(y % 2 != 0)` ` ` `res = res * x;` ` ` `// Update the value of y and x` ` ` `y = y >> 1;` ` ` `x = x * x;` ` ` `}` ` ` `// Return the result` ` ` `return` `res;` `}` `// Function to count number of arrays` `// having element over the range` `// [0, 2^K - 1] with Bitwise AND value` `// 0 having maximum possible sum` `static` `void` `countArrays(` `int` `N, ` `int` `K)` `{` ` ` ` ` `// Print the value of N^K` ` ` `Console.WriteLine((` `int` `)(power(N, K)));` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 5, K = 6;` ` ` ` ` `countArrays(N, K);` `}` `}` `// This code is contributed by subhammahato348` |

## Javascript

`<script>` ` ` `// JavaScript Program for the above approach` ` ` `// Function to find the value of X to` ` ` `// the power Y` ` ` `function` `power(x, y) {` ` ` `// Stores the value of X^Y` ` ` `let res = 1;` ` ` `while` `(y > 0) {` ` ` `// If y is odd, multiply x` ` ` `// with result` ` ` `if` `(y & 1)` ` ` `res = res * x;` ` ` `// Update the value of y and x` ` ` `y = y >> 1;` ` ` `x = x * x;` ` ` `}` ` ` `// Return the result` ` ` `return` `res;` ` ` `}` ` ` `// Function to count number of arrays` ` ` `// having element over the range` ` ` `// [0, 2^K - 1] with Bitwise AND value` ` ` `// 0 having maximum possible sum` ` ` `function` `countArrays(N, K) {` ` ` `// Print the value of N^K` ` ` `document.write(power(N, K));` ` ` `}` ` ` `// Driver Code` ` ` `let N = 5, K = 6;` ` ` `countArrays(N, K);` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output:**

15625

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