Designing Competition

C++ code

// C++ program to count total number of designs possible
#include <bits/stdc++.h>
using namespace std;


#define mod 1000000007


// Function to find the total number of designs possible for a given dimension
int numberOfDesigns(int l,int b)
{
	int ans = 1;

	for(int i=0; i < (l + b); i++)
	{
		ans = (ans * 2) % mod;
	}
  	
	return ans;
}


int main()
{

	// Given length of the sheet
	int l = 3;
   	
	// Given breadth of the sheet
	int b = 2;
    	
	// Call the function to find the total number of designs possible for the given dimension
	int ans = numberOfDesigns(l,b);
    	
	// Print the answer
	cout <<"The total number of designs possible for given dimension is: "<< ans << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output
The total number of designs possible for given dimension is: 32

Algorithm Complexity

Time Complexity: O( l + b)

In the function “numberOfDesigns()” to find the number of designs possible for a given value of ‘l’ and ‘b’, we have run a ‘for loop’ to calculate 2^(l+b). So, the time complexity is O(l + b), where ‘l’ and ‘b’ are length and breadth of the given sheet respectively.

Space Complexity: O(1) 

In the function “numberOfDesigns()” to find the number of designs possible for a given value of ‘l’ and ‘b’, , constant space is used. So, the space complexity is O(1).

Efficient Approach  

This approach of counting the total number of designs is the same as the previous one. But, here we will use binary exponentiation for calculating 2^{(l + b)}, which will be in logarithmic time complexity.

Algorithm 

Step 1. First, the main function. Inside the main function, create variables ‘l’ and ‘b’ to store the given length and breadth of the sheet respectively, then call the function “numberOfDesignsBinaryExp()” to find the total number of designs possible.

Step 2. Next, create the function “numberOfDesignsBinaryExp()” to find the total number of designs possible for a given dimension of sheet. It takes the following input parameters:

1. l: Length of the given sheet in the designing competition
2. arr: Breadth of the given sheet in the designing competition

Step 3.  Inside the function “numberOfDesignsBinaryExp()”, first initialise a variable ‘ans’ and calculate 2^{(l + b)} using binary exponentiation. Create a ‘while loop’ that will run while ‘y’ is greater than zero. In each iteration, if y is odd, multiply it with ‘ans’ and take modulo. If y is even, then update the value of x. Finally after the completion of the while loop, return the answer.

Step 4. Finally, print the calculated total number of designs possible for the given dimension of sheet.
 

C++ code

// C++ program to count total number of designs possible
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007


// Function to find the total number of designs possible for a given dimension
int numberOfDesignsBinaryExp(int l,int b)
{
	int ans = 1;

	int x = 2;
	int y = l + b;

	x = x % mod;

	if (x == 0) return 0;
    	
	while (y > 0)
	{

		// If y is odd, multiply x with result
		if (y & 1) {
			ans = (ans * x) % mod;
		}
		
		// y must be even now
		y = y/2;
		x = (x*x) % mod;
	}
	return ans;
}

You can also try this code with Online C++ Compiler

Run Code

Output
The total number of designs possible for given dimension is: 32

Algorithm Complexity

Time Complexity: O(log(l + b))

In the function “numberOfDesignsBinaryExp()” to find the number of designs possible for a given value of ‘l’ and ‘b’, we have used binary exponentiation to calculate 2^(l+b)  in which ‘y’ is getting halved at  each iteration . So, the time complexity is O(log(l + b)), where ‘l’ and ‘b’ are length and breadth of the given sheet respectively.

Space Complexity: O(1) 

In the function “numberOfDesignsBinaryExp()” to find the number of designs possible for a given value of ‘l’ and ‘b’, , constant space is used. So, the space complexity is O(1).

FAQs

1. What is Binary Exponentiation?
   Ans: Binary exponentiation is a technique to calculate the value of ‘x^y’ in ‘log(y)’ number of  multiplications only instead of ‘y’ number of multiplications.
2. How is the efficient approach discussed here better as compared to the brute force approach?
   Ans: The problem discussed above is reduced to calculate 2^{(l + b)}. In the brute force approach, 2^{(l + b)} is calculated using a ‘for loop’ which takes O(l + b) time but in the efficient approach, 2^{(l + b)} is calculated using binary exponentiation technique which takes O(log(l + b)) time.
    

Key Takeaways

This article discussed the problem “Designing Competition'', a brute force approach to the problem and an efficient approach based on binary exponentiation, their C++ implementation, and its time and space complexity. If you want to solve more problems for practice, you can visit Coding Ninjas Studio.

We hope that this blog helped you enhance your knowledge regarding the use of binary exponentiation in problems and its C++ implementation. 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Do upvote our blog to help other ninjas grow. Happy Coding!

Until then, All the best for your future endeavours, and Keep Coding.