Given an integer N, the task is to find the ways to choose some balls out of the given N balls such that at least one ball is chosen. Since the value can be large so print the value modulo 1000000007.
Example:
Input: N = 2
Output: 3
The three ways are “*.”, “.*” and “**” where ‘*’ denotes
the chosen ball and ‘.’ denotes the ball which didn’t get chosen.
Input: N = 30000
Output: 165890098
Approach: There are N balls and each ball can either be chosen or not chosen. Total number of different configurations is 2 * 2 * 2 * … * N. We can write this as 2N. But the state where no ball is chosen has to be subtracted from the answer. So, the result will be (2N – 1) % 1000000007.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MOD = 1000000007;// Function to return the count of// ways to choose the ballsint countWays(int n){ // Calculate (2^n) % MOD int ans = 1; for (int i = 0; i < n; i++) { ans *= 2; ans %= MOD; } // Subtract the only where // no ball was chosen return ((ans - 1 + MOD) % MOD);}// Driver codeint main(){ int n = 3; cout << countWays(n); return 0;} |
Java
// Java implementation of the approachclass GFG {static int MOD = 1000000007;// Function to return the count of// ways to choose the ballsstatic int countWays(int n){ // Calculate (2^n) % MOD int ans = 1; for (int i = 0; i < n; i++) { ans *= 2; ans %= MOD; } // Subtract the only where // no ball was chosen return ((ans - 1 + MOD) % MOD);}// Driver codepublic static void main(String[] args) { int n = 3; System.out.println(countWays(n));}} // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approachMOD = 1000000007# Function to return the count of # ways to choose the ballsdef countWays(n): # Return ((2 ^ n)-1) % MOD return (((2**n) - 1) % MOD)# Driver coden = 3print(countWays(n)) |
C#
// C# implementation of the approachusing System; class GFG {static int MOD = 1000000007;// Function to return the count of// ways to choose the ballsstatic int countWays(int n){ // Calculate (2^n) % MOD int ans = 1; for (int i = 0; i < n; i++) { ans *= 2; ans %= MOD; } // Subtract the only where // no ball was chosen return ((ans - 1 + MOD) % MOD);}// Driver codepublic static void Main(String[] args) { int n = 3; Console.WriteLine(countWays(n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript implementation of the approach MOD = 1000000007; // Function to return the count of // ways to choose the balls function countWays(n) { // Calculate (2^n) % MOD var ans = 1; for (i = 0; i < n; i++) { ans *= 2; ans %= MOD; } // Subtract the only where // no ball was chosen return ((ans - 1 + MOD) % MOD); } // Driver code var n = 3; document.write(countWays(n));// This code contributed by gauravrajput1 </script> |
7
Time Complexity : O(n)
Auxiliary Space : O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
