Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Maximum Element-Sum of a Complete Subset of Indices #21

Open
saichanda opened this issue Sep 23, 2023 · 3 comments · May be fixed by #22
Open

Maximum Element-Sum of a Complete Subset of Indices #21

saichanda opened this issue Sep 23, 2023 · 3 comments · May be fixed by #22
Assignees
@saichanda
Labels
LeetCode

Comments

@saichanda
Copy link
Owner

You are given a 1-indexed array nums of n integers.

A set of numbers is complete if the product of every pair of its elements is a perfect square.

For a subset of the indices set {1, 2, ..., n} represented as {i1, i2, ..., ik}, we define its element-sum as: nums[i1] + nums[i2] + ... + nums[ik].

Return the maximum element-sum of a complete subset of the indices set {1, 2, ..., n}.

A perfect square is a number that can be expressed as the product of an integer by itself.
@saichanda saichanda self-assigned this Sep 23, 2023
@saichanda
Copy link
Owner Author

Input: nums = [8,7,3,5,7,2,4,9]
Output: 16
Explanation: Apart from the subsets consisting of a single index, there are two other complete subsets of indices: {1,4} and {2,8}.
The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 8 + 5 = 13.
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 7 + 9 = 16.
Hence, the maximum element-sum of a complete subset of indices is 16.

@saichanda
Copy link
Owner Author

Input: nums = [5,10,3,10,1,13,7,9,4]
Output: 19
Explanation: Apart from the subsets consisting of a single index, there are four other complete subsets of indices: {1,4}, {1,9}, {2,8}, {4,9}, and {1,4,9}.
The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 5 + 10 = 15.
The sum of the elements corresponding to indices 1 and 9 is equal to nums[1] + nums[9] = 5 + 4 = 9.
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 10 + 9 = 19.
The sum of the elements corresponding to indices 4 and 9 is equal to nums[4] + nums[9] = 10 + 4 = 14.
The sum of the elements corresponding to indices 1, 4, and 9 is equal to nums[1] + nums[4] + nums[9] = 5 + 10 + 4 = 19.
Hence, the maximum element-sum of a complete subset of indices is 19.

@saichanda saichanda linked a pull request Sep 23, 2023 that will close this issue
Create max_ele_sum #22
Open
@saichanda
Copy link
Owner Author

idx 1_2 3 4 5 6 7 8 9
1 [[ X 2 3 4 5 6 7 8 9]
2 [ X X 6 8 10 12 14 16 18]
3 [ X X X 12 15 18 21 24 27]
4 [ X X X X 20 24 28 32 36]
5 [ X X X X X 30 35 40 45]
6 [ X X X X X X 42 48 54]
7 [ X X X X X X X 56 63]
8 [ X X X X X X X X 72]
9 [ X X X X X X X X X]]

To find the subsets of perfect squares from the above table.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@saichanda saichanda

Labels
LeetCode
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Create max_ele_sum saichanda/code_mastery
1 participant
@saichanda