Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Approach
5.
Program
5.1.
Example
6.
Complexity Analysis
7.
Key Takeaways
Last Updated: Mar 27, 2024

Arrange Elements of Given Array in a Mathematical Expression using Operators [+, -, *, /] and Parentheses to Get Value 28

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

We all prepare hard for the interview of our favorite company, solve a lot of DSA questions, study Computer Science Fundamentals, and enhance our problem-solving skills. So in this journey, this blog will help you solve one more interesting question.

‘Arrange elements of the given array in a mathematical expression using operators [+, -, *, /] and parentheses to get value 28’ is a kind of mathematical problem where one is required to have a grip on basic arithmetic rules to get an edge over it. Principles like BODMAS, etc, also play an essential role in reaching the solution. 

BODMAS rule dictates the correct order of operations when you complete a mathematical number sentence question with different operations. The BODMAS acronym stands for brackets, orders, division, multiplication, addition, subtraction. So after arranging them in a mathematical expression and solving it with the BODMAS rule, should give 28 as a result is a requirement.

Recommended topic, kth largest element in an array, and Euclid GCD Algorithm

Problem Statement

An array containing four integers between the range of [1, 9] is given. The task is to find out if it is possible to obtain 28 as the output by placing [+, -, *, /] operators between the array elements or grouping them using parenthesis. If it is possible, then print “28 can be generated”; otherwise, print “NO”.

Example

Input: NUMS[] = {1, 7, 4, 1}

Output: “28 can be generated”

Explanation: A possible way to construct 28 from above elements is:

1 X 7 x 4 X 1 = 28


Input: NUMS[] = {1, 8, 7, 2}

Output: “28 can be generated”

Explanation: A possible way to construct 28 from the above elements i:

(1 X 8 X 7) / 2 = 28

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Intuition

We always need to analyze the problem carefully and obtain the key points mentioned in the statement. From given conditions, we can observe that bracket sequences and operators can be inserted anywhere, which will result in many outcomes, out of which, one could be 28. This observation leads us to use a backtracking algorithm.

Approach

In order to solve this problem with a backtracking algorithm, we need to implement three functions to resolve four elements of the given array NUMS[] and reach an outcome. 

  • First function checkResolve_4(int num1, int num2, int num3, int num4), will take the complete array NUMS[] as an argument and will try applying all four operations between every consecutive element and call the following function recursively, checkResolve_3().  
  • The second function, checkResolve_3(double num1, double num2, double num3), will take three double values as arguments because the division operator can generate double values. Then it will check if we can generate 28 by applying given operations on all consecutive elements and call the further function checkResolve_2().
  • The final function checkResolve_2(double num1, double num2) will take the final two elements as arguments and return whether any of the four operations between these two values can generate 28.  
  • While comparing the final result with 28 in the function checkResolve_2(), we need to introduce a tolerance value to manage issues related to precision. 

Program

// Program to find if 28 can be generated.
#include <iostream>
#include <vector>
 
using namespace std;
 
// Function to resolve the final two elements to generate one outcome.
bool checkResolve_2(double num1, double num2)
{
      // Variable to store tolerance in precision.
      double tolerance = 0.001;
 
      // Addition operation on final elements.
      if (abs(num1 + num2 - 28.0) <= tolerance)
            return true;
 
      // Subtraction operation on final elements.
      if (abs(num1 - num2 - 28.0) <= tolerance)
            return true;
 
      // Multiplication operation on final elements.
      if (abs(num1 * num2 - 28.0) <= tolerance)
            return true;
 
      // Division operation on final elements.
      if (num2 != 0 && abs(num1 / num2 - 28.0) <= tolerance)
            return true;
 
      // Return false if 28 is not generated with all four operations.
      return false;
}
 
// Function to resolve three elements to generate one outcome.
bool checkResolve_3(double num1, double num2, double num3)
{
      // Variable to store the result.
      bool possible = false;
 
      // Applying all four operations on the first two consecutive elements.
      if(!possible)
            possible = possible | checkResolve_2(num1 + num2, num3);
      if(!possible)
            possible = possible | checkResolve_2(num1 - num2, num3);
      if(!possible)
            possible = possible | checkResolve_2(num1 * num2, num3);
      if(!possible && num2 != 0)
            possible = possible | checkResolve_2(num1 / num2, num3);
 
      // Checking if 28 is possible with operations on the first two consecutive elements.
      if (possible)
            return true;
 
      // Applying all four operations on the second two consecutive elements.
      if(!possible)
            possible = possible | checkResolve_2(num1, num2 + num3);
      if(!possible)
            possible = possible | checkResolve_2(num1, num2 - num3);
      if(!possible)
            possible = possible | checkResolve_2(num1, num2 * num3);
      if(!possible && num3 != 0)
            possible = possible | checkResolve_2(num1, num2 / num3);
 
      // Returning the final verdict.
      return possible;
}
 
// Function to resolve four elements to generate one outcome.
bool checkResolve_4(int num1, int num2, int num3, int num4)
{
      // Variable to store the result.
      bool possible = false;
 
      // Applying all four operations on the first two consecutive elements.
      if(!possible)
            possible = possible | checkResolve_3(num1 + num2, num3, num4);
      if(!possible)
            possible = possible | checkResolve_3(num1 - num2, num3, num4);
      if(!possible)
            possible = possible | checkResolve_3(num1 * num2, num3, num4);
      if(!possible && num2 != 0)
            possible = possible | checkResolve_3(num1 / num2, num3, num4);
 
      // Checking if 28 is possible with operations on the first two consecutive elements.
      if (possible)
            return true;
 
      // Applying all four operations on the  second two consecutive elements.
      if(!possible)
            possible = possible | checkResolve_3(num1, num2 + num3, num4);
      if(!possible)
            possible = possible | checkResolve_3(num1, num2 - num3, num4);
      if(!possible)
            possible = possible | checkResolve_3(num1, num2 * num3, num4);
      if(!possible && num3 != 0)
            possible = possible | checkResolve_3(num1, num2 / num3, num4);
 
      // Checking if 28 is possible with operations on the  second two consecutive elements.
      if (possible)
            return true;
 
      // Applying all four operations on the last two consecutive elements.
      if(!possible)
            possible = possible | checkResolve_3(num1, num2, num3 + num4);
      if(!possible)
            possible = possible | checkResolve_3(num1, num2, num3 - num4);
      if(!possible)
            possible = possible | checkResolve_3(num1, num2, num3 * num4);
      if(!possible && num4 != 0)
            possible = possible | checkResolve_3(num1, num2, num3 / num4);
 
      // Returning the final verdict.
      return possible;
}
 
// Main Function.
int main()
{
      // Vector to store the four elements.
      vector<int> NUMS(4);
 
      // Input of vector.
      for (int i = 0; i < 4; i++)
            cin >> NUMS[i];
 
      // Printing the output.
      if (checkResolve_4(NUMS[0], NUMS[1], NUMS[2], NUMS[3]))
            cout << "28 can be generated";
      else
            cout << "NO";
 
      return 0;
}

Example

Input:

1 14 4 2

Output:

28 can be generated

Complexity Analysis

Time Complexity: O(4x 3!)

Explanation: Complexity generated by all three functions: 

(4 x 3) x (4 x 2) x (4 x 1) = 43 x 3!

Space Complexity: O(1)

Explanation: No extra space has been used

Key Takeaways

In this article, we’ve discussed the “Arrange elements of the given array in a mathematical expression using operators [+, -, *, /] and parentheses to get value 28” problem. Here an effective method has been used, which is called backtracking. It also involves arithmetic concepts like BODMAS which enhances one’s mathematical skills. More such problems can be found on Backtracking Problems.  These questions are asked during various coding contests as well as placements tests.

Check out this article - Balanced Parentheses

If you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!

Previous article
Maximum length of a string having even frequency of each character formed by concatenation
Next article
Solve Sudoku on the Basis of the Given Irregular Regions
Live masterclass