# Count of Arrays of size N with elements in range [0, (2^K)-1] having maximum sum & bitwise AND 0

Given two integers **N** and **K**, The task is to find the count of all possible arrays of size **N** with **maximum sum **& **bitwise AND **of all elements as 0. Also, elements should be within the range of **0 **to** 2 ^{K}-1**.

**Examples:**

Input:N = 3, K = 2Output:9Explanation:2^{2}– 1 = 3, so elements of arrays should be between 0 to 3. All possible arrays are- [3, 3, 0], [1, 2, 3], [3, 0, 3], [0, 3, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] Bitwise AND of all the arrays is 0 & also the sum = 6 is maximumInput: N = 2, K = 2Output: 4Explanation: All possible arrays are – [3, 0], [0, 3], [1, 2], [2, 1]

**Approach: **To better understand the approach, refer to the steps below:

- As the maximum possible element is
**(2**and the size of the array is^{K}– 1)**N**so if all elements of the array are equal to the maximum element then the sum will be**maximum**i.e.**N * (2**=^{K}– 1)**N * ( 2**. Keep in mind that there are K bits in ( 2^{0}+ 2^{1}+ …………….. + 2^{K – 1})^{K}– 1) and all bits are set. - So now to make bitwise AND of all elements equal to 0 we have to
**unset**each bit at least in one element. Also, we**can not unset the same bit in more than 1 element**because in that case**sum**will not be**maximum**. - After unsetting each bit in one element, the maximum possible Sum = N * ( 2
^{0}+ 2^{1}+ ……… + 2^{K – 1}) – ( 2^{0}+ 2^{1}+ ………. + 2^{K – 1}) = (N * (2^{K}-1 )) – (2^{K}-1)=**(N – 1) * (2**.^{K}– 1) - Now the goal is to find all the
**ways**through which we can**unset**all**K bits**in**at least**one element. You can see that for unsetting a single bit you have N options i.e. you can unset it in any one of N elements. So the**total way for unsetting K bits will be N**. This is our final answer.^{K}

**Illustration:**

Let N = 3, K = 3

- Make all elements of the array equal to 2
^{3}– 1 = 7. The array will be [7, 7, 7]. Take binary representation of all elements : [111, 111, 111].- Unset each bit in exactly one element. Suppose we unset the 3rd bit of the 1st element and the 1st two bits of the 2nd element. array becomes [110, 001, 111] = [6, 1, 7]. This is one of the valid arrays. You can generate all arrays in such a way.
- The total number of arrays will be 3
^{3}= 27.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Iterative Function to calculate` `// (x^y) in O(log y)` `int` `power(` `int` `x, ` `int` `y)` `{` ` ` `// Initialize answer` ` ` `int` `res = 1;` ` ` `// Check till the number becomes zero` ` ` `while` `(y) {` ` ` `// If y is odd, multiply x with result` ` ` `if` `(y % 2 == 1)` ` ` `res = (res * x);` ` ` `// y = y/2` ` ` `y = y >> 1;` ` ` `// Change x to x^2` ` ` `x = (x * x);` ` ` `}` ` ` `return` `res;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 3, K = 2;` ` ` `cout << power(N, K);` ` ` `return` `0;` `}` |

## Java

`// Java code for the above approach` `import` `java.util.*;` `public` `class` `GFG` `{` ` ` `// Iterative Function to calculate` ` ` `// (x^y) in O(log y)` ` ` `static` `int` `power(` `int` `x, ` `int` `y)` ` ` `{` ` ` `// Initialize answer` ` ` `int` `res = ` `1` `;` ` ` `// Check till the number becomes zero` ` ` `while` `(y > ` `0` `) {` ` ` `// If y is odd, multiply x with result` ` ` `if` `(y % ` `2` `== ` `1` `)` ` ` `res = (res * x);` ` ` `// y = y/2` ` ` `y = y >> ` `1` `;` ` ` `// Change x to x^2` ` ` `x = (x * x);` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String args[])` ` ` `{` ` ` `int` `N = ` `3` `, K = ` `2` `;` ` ` `System.out.print(power(N, K));` ` ` `}` `}` `// This code is contributed by Samim Hossain Mondal.` |

## Python3

`# python3 program for the above approach` `# Iterative Function to calculate` `# (x^y) in O(log y)` `def` `power(x, y):` ` ` `# Initialize answer` ` ` `res ` `=` `1` ` ` `# Check till the number becomes zero` ` ` `while` `(y):` ` ` `# If y is odd, multiply x with result` ` ` `if` `(y ` `%` `2` `=` `=` `1` `):` ` ` `res ` `=` `(res ` `*` `x)` ` ` `# y = y/2` ` ` `y ` `=` `y >> ` `1` ` ` `# Change x to x^2` ` ` `x ` `=` `(x ` `*` `x)` ` ` `return` `res` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `3` ` ` `K ` `=` `2` ` ` `print` `(power(N, K))` ` ` `# This code is contributed by rakeshsahni` |

## C#

`// C# code to implement above approach` `using` `System;` `class` `GFG` `{` ` ` ` ` `// Iterative Function to calculate` ` ` `// (x^y) in O(log y)` ` ` `static` `int` `power(` `int` `x, ` `int` `y)` ` ` `{` ` ` `// Initialize answer` ` ` `int` `res = 1;` ` ` `// Check till the number becomes zero` ` ` `while` `(y > 0) {` ` ` `// If y is odd, multiply x with result` ` ` `if` `(y % 2 == 1)` ` ` `res = (res * x);` ` ` `// y = y/2` ` ` `y = y >> 1;` ` ` `// Change x to x^2` ` ` `x = (x * x);` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `N = 3, K = 2;` ` ` `Console.Write(power(N, K));` ` ` `}` `}` `// This code is contributed by Samim Hossain Mondal.` |

## Javascript

` ` `<script>` ` ` `// JavaScript code for the above approach` ` ` `// Iterative Function to calculate` ` ` `// (x^y) in O(log y)` ` ` `function` `power(x, y) {` ` ` `// Initialize answer` ` ` `let res = 1;` ` ` `// Check till the number becomes zero` ` ` `while` `(y) {` ` ` `// If y is odd, multiply x with result` ` ` `if` `(y % 2 == 1)` ` ` `res = (res * x);` ` ` `// y = y/2` ` ` `y = y >> 1;` ` ` `// Change x to x^2` ` ` `x = (x * x);` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` `// Driver Code` ` ` `let N = 3, K = 2;` ` ` `document.write(power(N, K));` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

9

**Time Complexity**: O(logK)**Auxiliary Space**: O(1)