Given a number N, the task is to represent N as sum of maximum number of unique positive integers.
Examples:
Input: N = 12
Output: 1+ 2 + 3 + 6
Explanation:
Possible splits are:
2 + 10
4 + 8
2 + 4 + 6
1 + 2 + 3 + 6
Among them, (1 + 2 + 3 + 6) contains the maximum number of unique integers.Input: N = 6
Output: 1 + 2 + 3
Approach: Consider the below observations to solve the problem:
- We know that any number N can be represented as the sum of N 1s.
- But it is required in this problem that no duplicate values are taken.
- Hence we will try to group N 1s into unique combinations, which will surely give as sum N.
Illustration:
Consider, N = 12 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Since the numbers have to be unique, lets try to group 1s in a continuous manner.
- Cannot group 1’s in this manner since second grouping and last grouping result in same number.
12 = (1) + (1 + 1) + (1 + 1 + 1) + (1 + 1 + 1 + 1) + (1 + 1)
= 1 + 2 + 3 + 4 + 2- To avoid this, combine the last two groupings.
12 = (1) + (1 + 1) + (1 + 1 + 1) + (1 + 1 + 1 + 1 + 1 + 1)
= 1 + 2 + 3 + 6Therefore, To make groupings unique, the number of 1’s in any two groups should not be the same.
Below is the implementation of the above approach:
C++
// C++ program to find maximum number of// splits into unique positive integers.#include <iostream>#include <vector>using namespace std;vector<int> maximumSplit(int N){ vector<int> answer; int groupSize = 1; while (N >= groupSize) { answer.push_back(groupSize); N -= groupSize; groupSize++; } // In case N != 0, then it is not // possible to group remaining 1's if (N != 0) { // Get the last unique integer int last = answer.back(); answer.pop_back(); // Add the remaining 1's to it last += N; // Add the new number to list answer.push_back(last); } return answer;}// Driver Codeint main(){ int N = 12; vector<int> answer = maximumSplit(N); for (int n : answer) cout << n << " ";} |
Java
// Java program to find maximum number of// splits into unique positive integers.import java.util.*;class GFG { public static List<Integer> maximumSplit(int N) { List<Integer> answer = new ArrayList<>(); int groupSize = 1; while (N >= groupSize) { answer.add(groupSize); N -= groupSize; groupSize++; } // In case N != 0, // then we were not able // to group remaining 1's if (N != 0) { // get the last unique integer int last = answer.remove( answer.size() - 1); // add the remaining 1's to it last += N; // add the new number to list answer.add(last); } return answer; } // Driver code public static void main(String[] args) { int N = 12; List<Integer> answer = maximumSplit(N); for (int n : answer) System.out.print(n + " "); }} |
Python3
# Python code for the above approachdef maximumSplit(N): answer = []; groupSize = 1; while (N >= groupSize): answer.append(groupSize); N -= groupSize; groupSize= groupSize + 1; # In case N != 0, then it is not # possible to group remaining 1's if (N != 0): # Get the last unique integer last = answer[len(answer) - 1]; answer.pop(); # Add the remaining 1's to it last += N; # Add the new number to list answer.append(last); return answer; # Driver CodeN = 12;answer = maximumSplit(N);for i in range(len(answer)): print(answer[i], end = " ");# This code is contributed by Potta Lokesh |
C#
// C# program to find maximum number of// splits into unique positive integers.using System;using System.Collections;class GFG{ static ArrayList maximumSplit(int N) { ArrayList answer = new ArrayList(); int groupSize = 1; while (N >= groupSize) { answer.Add(groupSize); N -= groupSize; groupSize++; } // In case N != 0, then it is not // possible to group remaining 1's if (N != 0) { // Get the last unique integer int last = (int)answer[answer.Count - 1]; answer.RemoveAt(answer.Count - 1); // Add the remaining 1's to it last += N; // Add the new number to list answer.Add(last); } return answer; } // Driver Code public static void Main() { int N = 12; ArrayList answer = maximumSplit(N); foreach (int n in answer) Console.Write(n + " "); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to find maximum number of // splits into unique positive integers. const maximumSplit = (N) => { let answer = []; let groupSize = 1; while (N >= groupSize) { answer.push(groupSize); N -= groupSize; groupSize++; } // In case N != 0, then it is not // possible to group remaining 1's if (N != 0) { // Get the last unique integer let last = answer[answer.length - 1]; answer.pop(); // Add the remaining 1's to it last += N; // Add the new number to list answer.push(last); } return answer; } // Driver Code let N = 12; let answer = maximumSplit(N); for (let n in answer) document.write(`${answer[n]} `);// This code is contributed by rakeshsahni</script> |
Output
1 2 3 6
Time complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
