Stick Division

Easy

0/40

Average time to solve is 15m

Contributed by

2 upvotes

Asked in companies

Problem statement

You have 'N' sticks of different lengths. You want sticks to be of equal length. You can cut any stick any number of times. Your task is to find the maximum length of the stick you can get.

Note:

The cuts in all the sticks will be of the same length.

For Example:

You have 4 sticks of sizes 4, 12, 20, 48. Now you want to cut sticks of equal length from each stick. Then you have the following options:

Make all the sticks of unit length.

Make all sticks of 2 unit length, 4(2*2), 12(2*6), 20(2*10), 48(2*24)

Make all the sticks of 4 unit length, 4(4*1), 12(4*3), 20(4*5), 48(4*12)

Hence, the maximum possible length of the stick is 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows. 

The first line of each test case contains an integer ‘N’ representing the number of sticks you have.

The next line contains 'N' space-separated integers, which denotes the size of the 'N' sticks.

Output Format:

For each test case, return the maximum possible length of the stick possible.

Note:

You don’t need to print anything or take input. This already has been taken care of.

Constraints:

1 <= T <= 100
2 <= N <= 5000
1 <= length[i] <= 10^6

Time Limit: 1 second

Sample Input 1:

Sample Output 1:

2
1

Explanation For Sample Output 1:

Test Case 1:
Here we have sticks of lengths 2, 4, 6, and 8. So we can cut these in sticks of 1 unit length or sticks of length 2 unit.
1 < 2 so, we will return 2.

Test Case 2:
In this case, there is only one possibility, i.e., sticks of length 1. So we will return 1.

Sample Input 2

Sample output 2

1
5

Hint 1

Think of the greatest common divisor.

Approaches (1)

Approach 1

Brute Force

The greatest length possible is the gcd of all lengths given. So for finding the maximum length we need to find the gcd of the array.

Algorithm:

Make a function for gcd of 2 number, let say int gcd(int a, int b)
- if(a == 0) then return b
- Else return gcd(b%a, a)
Now make another function for finding the gcd of the array.
- Initialise a variable ans = length[0]
- Now iterate i from 1 to the size of the array:
  - Update ans as, ans = gcd(ans, length[i]).
  - If ans == 1 at any point then return 1.
- Return ans. That will be the maximum possible length.

Time Complexity

O(N * log(M)), Where ‘N’ is the size of the array, and ‘M’ is the smallest element in the array.

For finding the gcd of two numbers ‘a’ and ‘b’, we need log(min(a,b)) operations. In this case, we are finding gcd of an array so we have to traverse through its length. So complexity is O(N * log(M)).

Space Complexity

O(1)

Since no extra space is used.

(100% EXP penalty)

Stick Division

Console