Sponsored
Sponsored
The key observation is that to maximize the result of the division, we should minimize the denominator. We achieve this by grouping as many elements as possible in the denominator so that the result becomes maximum. Hence, we should divide the first number by all the numbers after the first number treated as one single division.
Time Complexity: O(n), where n is the number of elements in nums. We iterate through the nums once to construct the string.
Space Complexity: O(n), for storing the joined string.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5char* optimalDivision(int* nums, int numsSize) {
6 if (numsSize == 1) {
7 char* result = (char*)malloc(24 * sizeof(char));
8 sprintf(result, "%d", nums[0]);
9 return result;
10 }
11 if (numsSize == 2) {
12 char* result = (char*)malloc(48 * sizeof(char));
13 sprintf(result, "%d/%d", nums[0], nums[1]);
14 return result;
15 }
16 char* result = (char*)malloc(256 * sizeof(char));
17 char temp[16];
18 sprintf(result, "%d/(", nums[0]);
19 for (int i = 1; i < numsSize; ++i) {
20 sprintf(temp, "%d", nums[i]);
21 strcat(result, temp);
22 if (i < numsSize - 1) strcat(result, "/");
23 }
24 strcat(result, ")");
25 return result;
26}The C solution implements the logic using memory allocation for string operations. It handles base cases directly and constructs the expression for more than two numbers by iterating through the nums array and concatenating the numbers with necessary division symbols and enclosing parentheses for optimizing division results.