Find any K distinct odd integers such that their sum is equal to N
Given two integers N and K, the task is to find any K distinct odd integers such that their sum is equal to N. If no such integers exists, print -1.
Examples:
Input: N = 10, K = 2
Output: 1, 9
Explanation:
There are two possible distinct odd integers, such that their sum is equal to N.
Possible K integers can be – {(1, 9), (3, 7)}
Input: N = 5, K = 4
Output: -1
Explanation:
There are no such 4 distinct odd integers such that their sum is 5.
Approach:
- The key observation in this problem is if N and K have different parity then it is not possible to find K such distinct integers such that their sum is equal to N,
- Otherwise such K – 1 integers will consist of first K-1 odd positive integers
- The Kth odd number will be equal to (N – the sum of first (K-1) odd integers)
Kth Odd number = N - sum of first K-1 integer
Below is the implementation of the above approach:
C++
// C++ implementation to find k // odd integers such that their sum is N #include <bits/stdc++.h> using namespace std; // Function to find K odd integers // such that their sum is N void oddIntegers( int n, int k) { // Condition to check if there // exist such K integers if (n % 2 != k % 2) { cout << "-1" << "\n" ; return ; } int sum = 0; int i = 1; int j = 1; // Loop to find first K-1 // distinct odd integers while (j < k) { sum = sum + i; cout << i << " " ; i = i + 2; j++; } // Final Kth odd number int finalOdd = n - sum; cout << finalOdd << "\n" ; } // Driver code int main() { int n = 10; int k = 2; oddIntegers(n, k); return 0; } |
Java
// Java implementation to find k // odd integers such that their sum is N class GFG { // Function to find K odd integers // such that their sum is N static void oddIntegers( int n, int k) { // Condition to check if there // exist such K integers if (n % 2 != k % 2 ) { System.out.println( "-1" ); return ; } int sum = 0 ; int i = 1 ; int j = 1 ; // Loop to find first K-1 // distinct odd integers while (j < k) { sum = sum + i; System.out.print(i+ " " ); i = i + 2 ; j++; } // Final Kth odd number int finalOdd = n - sum; System.out.println(finalOdd); } // Driver code public static void main (String[] args) { int n = 10 ; int k = 2 ; oddIntegers(n, k); } } // This code is contributed by shubhamsingh |
Python3
# Python3 implementation to find k # odd integers such that their sum is N # Function to find K odd integers # such that their sum is N def oddIntegers(n, k) : # Condition to check if there # exist such K integers if (n % 2 ! = k % 2 ) : print ( "-1" ); return ; sum = 0 ; i = 1 ; j = 1 ; # Loop to find first K-1 # distinct odd integers while (j < k) : sum + = i; print (i,end = " " ); i + = 2 ; j + = 1 ; # Final Kth odd number finalOdd = n - sum ; print (finalOdd); # Driver code if __name__ = = "__main__" : n = 10 ; k = 2 ; oddIntegers(n, k); # This code is contributed by AnkitRai01 |
C#
// C# implementation to find k // odd integers such that their sum is N using System; class GFG { // Function to find K odd integers // such that their sum is N static void oddints( int n, int k) { // Condition to check if there // exist such K integers if (n % 2 != k % 2) { Console.WriteLine( "-1" ); return ; } int sum = 0; int i = 1; int j = 1; // Loop to find first K-1 // distinct odd integers while (j < k) { sum = sum + i; Console.Write(i+ " " ); i = i + 2; j++; } // Final Kth odd number int finalOdd = n - sum; Console.WriteLine(finalOdd); } // Driver code public static void Main(String[] args) { int n = 10; int k = 2; oddints(n, k); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation to find k // odd integers such that their sum is N // Function to find K odd integers // such that their sum is N function oddIntegers(n , k) { // Condition to check if there // exist such K integers if (n % 2 != k % 2) { document.write( "-1" ); return ; } var sum = 0; var i = 1; var j = 1; // Loop to find first K-1 // distinct odd integers while (j < k) { sum = sum + i; document.write(i + " " ); i = i + 2; j++; } // Final Kth odd number var finalOdd = n - sum; document.write(finalOdd); } // Driver code var n = 10; var k = 2; oddIntegers(n, k); // This code contributed by Rajput-Ji </script> |
Output
1 9
Performance Analysis:
- Time Complexity: As in the above approach, There is a loop to find such K odd integers which takes O(K) time in worst case. Hence the Time Complexity will be O(K).
- Auxiliary Space Complexity: As in the above approach, There is no extra space used. Hence the auxiliary space complexity will be O(1).
Using Dynamic Programming:
Approach:
- Define a function distinct_odd_integers_sum(N, K, memo={}) that takes three arguments – N, K, and memo. N is the sum we want to achieve and K is the number of distinct odd integers we want to use to achieve this sum. The memo parameter is used for memoization and is an empty dictionary by default.
- If the (N, K) tuple is already present in the memo dictionary, return its value.
- If K is equal to 1, then we can only use one integer to achieve the sum. Check if N is odd, if yes, return a list containing N, otherwise return None.
- If K is greater than 1, iterate over all odd integers from 1 to N (exclusive) with a step of 2. For each odd integer i, recursively call the distinct_odd_integers_sum function with the parameters N-i and K-1, and store the result in the remaining variable.
- If remaining is not None and i is not in remaining, then we can add i to the remaining list and return the list [i] + remaining.
- If we have exhausted all possible odd integers without finding a valid combination, then add the (N, K) tuple to the memo dictionary with a value of None and return None.
- Finally, outside the function, set N and K to the input values and call the distinct_odd_integers_sum function with these arguments. If the function returns a list, print the list, otherwise print -1.
C++
#include <algorithm> // Include the algorithm header for std::find #include <iostream> #include <map> #include <vector> std::map<std::pair< int , int >, std::vector< int > > memo; // Function to find a list of K distinct odd integers that // sum to N std::vector< int > distinctOddIntegersSum( int N, int K) { if (memo.count(std::make_pair(N, K)) > 0) { return memo[std::make_pair(N, K)]; } if (K == 1) { if (N % 2 != 0) { return { N }; } else { return std::vector< int >(); } } else { for ( int i = 1; i < N; i += 2) { std::vector< int > remaining = distinctOddIntegersSum(N - i, K - 1); if (!remaining.empty() && std::find(remaining.begin(), remaining.end(), i) == remaining.end()) { memo[std::make_pair(N, K)] = { i }; memo[std::make_pair(N, K)].insert( memo[std::make_pair(N, K)].end(), remaining.begin(), remaining.end()); return memo[std::make_pair(N, K)]; } } } memo[std::make_pair(N, K)] = std::vector< int >(); return memo[std::make_pair(N, K)]; } int main() { int N = 10; int K = 2; std::vector< int > result = distinctOddIntegersSum(N, K); if (!result.empty()) { for ( int i : result) { std::cout << i << " " ; } } else { std::cout << -1; } std::cout << std::endl; return 0; } |
Java
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class DistinctOddIntegersSum { // Memoization map to store computed results private static Map<Map.Entry<Integer, Integer>, List<Integer> > memo = new HashMap<>(); // Function to find a list of K distinct odd integers // that sum to N private static List<Integer> distinctOddIntegersSum( int N, int K) { Map.Entry<Integer, Integer> key = new java.util.AbstractMap.SimpleEntry<>(N, K); // Check if the result is already computed and // stored in memo if (memo.containsKey(key)) { return memo.get(key); } // Base case: K is 1 if (K == 1 ) { if (N % 2 != 0 ) { List<Integer> result = new ArrayList<>(); result.add(N); memo.put(key, result); return result; } else { memo.put(key, new ArrayList<>()); return memo.get(key); } } else { // Iterate through odd integers up to N for ( int i = 1 ; i < N; i += 2 ) { List<Integer> remaining = distinctOddIntegersSum(N - i, K - 1 ); // Check if i is not present in the // remaining list if (!remaining.isEmpty() && !remaining.contains(i)) { List<Integer> result = new ArrayList<>(); result.add(i); result.addAll(remaining); memo.put(key, result); return memo.get(key); } } } // No valid result found memo.put(key, new ArrayList<>()); return memo.get(key); } public static void main(String[] args) { int N = 10 ; int K = 2 ; List<Integer> result = distinctOddIntegersSum(N, K); if (!result.isEmpty()) { for ( int i : result) { System.out.print(i + " " ); } } else { System.out.print(- 1 ); } System.out.println(); } } |
Python3
def distinct_odd_integers_sum(N, K, memo = {}): if (N, K) in memo: return memo[(N, K)] if K = = 1 : return [N] if N % 2 ! = 0 else None else : for i in range ( 1 , N, 2 ): remaining = distinct_odd_integers_sum(N - i, K - 1 , memo) if remaining and i not in remaining: memo[(N, K)] = [i] + remaining return memo[(N, K)] memo[(N, K)] = None return None N = 10 K = 2 result = distinct_odd_integers_sum(N, K) if result: print (result) else : print ( - 1 ) |
C#
using System; using System.Collections.Generic; class Program { static Dictionary<( int , int ), List< int >> memo = new Dictionary<( int , int ), List< int >>(); static List< int > DistinctOddIntegersSum( int N, int K) { // Check if the result is already memoized. if (memo.ContainsKey((N, K))) { return memo[(N, K)]; } // Base case: when K is 1, return a list with N if it's odd, or an empty list. if (K == 1) { if (N % 2 != 0) { memo[(N, K)] = new List< int > { N }; return memo[(N, K)]; } else { memo[(N, K)] = new List< int >(); return memo[(N, K)]; } } else { for ( int i = 1; i < N; i += 2) { // Recursively calculate the remaining values for K-1. List< int > remaining = DistinctOddIntegersSum(N - i, K - 1); if (remaining.Count > 0 && !remaining.Contains(i)) { // If 'i' is not already in the remaining list, add it and memoize the result. memo[(N, K)] = new List< int > { i }; memo[(N, K)].AddRange(remaining); return memo[(N, K)]; } } } // If no valid result is found, memoize and return an empty list. memo[(N, K)] = new List< int >(); return memo[(N, K)]; } static void Main() { int N = 10; int K = 2; List< int > result = DistinctOddIntegersSum(N, K); if (result.Count > 0) { Console.Write( string .Join( " , " , result)); } else { Console.Write(-1); } Console.WriteLine(); } } |
Javascript
function distinctOddIntegersSum(N, K, memo = {}) { // Check if the result is already memoized if (memo[N] && memo[N][K]) { return memo[N][K]; } // Base case: K is 1 if (K === 1) { // Return [N] if N is odd, else return null if (N % 2 !== 0) { memo[N] = memo[N] || {}; memo[N][K] = [N]; return [N]; } else { return null ; } } // Initialize an array to store the result let result = null ; // Iterate through odd numbers from 1 to N for (let i = 1; i < N; i += 2) { // Calculate the remaining sum const remaining = distinctOddIntegersSum(N - i, K - 1, memo); // If there is a valid remaining sum and i is not in it if (remaining && !remaining.includes(i)) { // Update the result array and memoize it result = [i, ...remaining]; memo[N] = memo[N] || {}; memo[N][K] = result; return result; } } // Memoize the result as null memo[N] = memo[N] || {}; memo[N][K] = null ; return null ; } const N = 10; const K = 2; const result = distinctOddIntegersSum(N, K); if (result) { console.log(result); } else { console.log(-1); } |
Output
[1, 9]
Time Complexity: O(NK)
Space Complexity: O(NK)