Given an array arr[] consisting of N positive integers, the task is to check if each array element can be represented in terms of numbers 4 and 5. If it is possible, then print the total count of 4 and 5 needed for each array element. Otherwise, print -1.
Examples:
Input: arr[] = {12, 11, 9}
Output: 3 -1 2
Explanation:
- arr[0]( =12): Print 3 as it can be represented by using 3 fours i.e. 4 + 4 + 4 = 12.
- arr[1](= 11): Print -1 as it cannot be represented by any combination of 4 and 5.
- arr[2](= 9): Print 2 as it can be represented by using one 4 and one 5 i.e. 4 + 5 = 9.
Input: arr[] = {7, 15, 17, 22}
Output: -1 3 4 5
Approach: The problem can be solved using greedy approach and a bit of mathematics. Follow the steps below to solve the problem:
- Initialize a vector say ans, as {-1} where the ans[i] stores the answer to a possible answer for the value arr[i] of the array arr[].
- Iterate over a range [0, N-1] using the variable i and perform the following steps:
- If arr[i] is less than 4, then, continue.
- Initialize two variables, say sum as INT_MAX to store the count of numbers of 4 and 5 needed to form arr[i] and cnt as 0 to keep the count of the current factor of 4.
- Iterate over a range [0, arr[i]] using the variable j and perform the following steps:
- If (arr[i] – j) is divisible by 5, then, set the value of the sum to the minimum of sum and (cnt + (arr[i] – j)/5).
- Increase the value of cnt by 1 and j by 4.
- If the sum is not equal to INT_MAX, then, set the value of ans[i] in the vector ans as sum.
- Finally, after completing the above steps, print the values in the vector ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the count of the // combination of 4 or 5 required to // make the arr[i] for each 0 < i < N void sumOfCombinationOf4OR5(vector< int > arr, int N) { // Vector to store the answer vector< int > ans(N, -1); // Iterate in the range[0, N-1] for ( int i = 0; i < N; i++) { if (arr[i] < 4) { continue ; } // Initialize sum to store the count // of numbers and cnt for the current // factor of 4 int sum = INT_MAX, cnt = 0; // Iterate in the range[0, arr[i]] with // increment of 4 for ( int j = 0; j <= arr[i]; j += 4) { // Check if arr[i] - j(the current factor // of 4) is divisible by 5 or not if ((arr[i] - j) % 5 == 0) { sum = min(sum, cnt + (arr[i] - j) / 5); } cnt++; } // If sum is not maximum // then answer is found if (sum != INT_MAX) ans[i] = sum; } // Finally, print the required answer for ( auto num : ans) cout << num << " " ; } // Driver Code int main() { // Given Input vector< int > arr = { 7, 15, 17, 22 }; int N = arr.size(); // Function Call sumOfCombinationOf4OR5(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.Arrays; class GFG { // Function to print the count of the // combination of 4 or 5 required to // make the arr[i] for each 0 < i < N static void sumOfCombinationOf4OR5( int [] arr, int N) { // Vector to store the answer int [] ans = new int [N]; Arrays.fill(ans, - 1 ); // Iterate in the range[0, N-1] for ( int i = 0 ; i < N; i++) { if (arr[i] < 4 ) { continue ; } // Initialize sum to store the count // of numbers and cnt for the current // factor of 4 int sum = Integer.MAX_VALUE; int cnt = 0 ; // Iterate in the range[0, arr[i]] with // increment of 4 for ( int j = 0 ; j <= arr[i]; j += 4 ) { // Check if arr[i] - j(the current factor // of 4) is divisible by 5 or not if ((arr[i] - j) % 5 == 0 ) { sum = Math.min(sum, cnt + (arr[i] - j) / 5 ); } cnt++; } // If sum is not maximum // then answer is found if (sum != Integer.MAX_VALUE) ans[i] = sum; } // Finally, print the required answer for ( int num : ans) System.out.printf(num + " " ); } // Driver Code public static void main(String[] args) { // Given Input int [] arr = { 7 , 15 , 17 , 22 }; int N = arr.length; // Function Call sumOfCombinationOf4OR5(arr, N); } } // This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach # Function to print the count of the # combination of 4 or 5 required to # make the arr[i] for each 0 < i < N def sumOfCombinationOf4OR5(arr, N): # Vector to store the answer ans = [ - 1 for i in range (N)] # Iterate in the range[0, N-1] for i in range (N): if (arr[i] < 4 ): continue # Initialize sum to store the count # of numbers and cnt for the current # factor of 4 sum = 10 * * 9 cnt = 0 # Iterate in the range[0, arr[i]] with # increment of 4 for j in range ( 0 , arr[i] + 1 , 4 ): # Check if arr[i] - j(the current factor # of 4) is divisible by 5 or not if ((arr[i] - j) % 5 = = 0 ): sum = min ( sum , cnt + (arr[i] - j) / / 5 ) cnt + = 1 # If sum is not maximum # then answer is found if ( sum ! = 10 * * 9 ): ans[i] = sum # Finally, print the required answer for num in ans: print (num, end = " " ) # Driver Code # Given Input arr = [ 7 , 15 , 17 , 22 ] N = len (arr) # Function Call sumOfCombinationOf4OR5(arr, N) # This code is contributed by gfgking |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to print the count of the // combination of 4 or 5 required to // make the arr[i] for each 0 < i < N static void sumOfCombinationOf4OR5( int []arr, int N) { // Vector to store the answer int []ans = new int [N]; for ( int i = 0; i < N; i++) ans[i] = -1; // Iterate in the range[0, N-1] for ( int i = 0; i < N; i++) { if (arr[i] < 4) { continue ; } // Initialize sum to store the count // of numbers and cnt for the current // factor of 4 int sum = Int32.MaxValue, cnt = 0; // Iterate in the range[0, arr[i]] with // increment of 4 for ( int j = 0; j <= arr[i]; j += 4) { // Check if arr[i] - j(the current factor // of 4) is divisible by 5 or not if ((arr[i] - j) % 5 == 0) { sum = Math.Min(sum, cnt + ( int )(arr[i] - j) / 5); } cnt++; } // If sum is not maximum // then answer is found if (sum != Int32.MaxValue) ans[i] = sum; } // Finally, print the required answer foreach ( int num in ans) Console.Write(num + " " ); } // Driver Code public static void Main() { // Given Input int []arr = {7, 15, 17, 22 }; int N = arr.Length; // Function Call sumOfCombinationOf4OR5(arr, N); } } // This code is contributed by ipg2016107. |
Javascript
<script> // Javascript program for the above approach // Function to print the count of the // combination of 4 or 5 required to // make the arr[i] for each 0 < i < N function sumOfCombinationOf4OR5(arr, N) { // Vector to store the answer let ans = new Array(N).fill(-1); // Iterate in the range[0, N-1] for (let i = 0; i < N; i++) { if (arr[i] < 4) { continue ; } // Initialize sum to store the count // of numbers and cnt for the current // factor of 4 let sum = Number.MAX_SAFE_INTEGER, cnt = 0; // Iterate in the range[0, arr[i]] with // increment of 4 for (let j = 0; j <= arr[i]; j += 4) { // Check if arr[i] - j(the current factor // of 4) is divisible by 5 or not if ((arr[i] - j) % 5 == 0) { sum = Math.min(sum, cnt + Math.floor((arr[i] - j) / 5)); } cnt++; } // If sum is not maximum // then answer is found if (sum != Number.MAX_SAFE_INTEGER) ans[i] = sum; } // Finally, print the required answer for (let num of ans) document.write(num + " " ); } // Driver Code // Given Input let arr = [7, 15, 17, 22]; let N = arr.length; // Function Call sumOfCombinationOf4OR5(arr, N); </script> // This code is contributed by _saurabh_jaiswal. |
-1 3 4 5
Time Complexity: O(N*M) where M is the maximum element of the array arr[].
Auxiliary Space: O(N)
Note: The above approach can be further optimized in terms of space complexity as storing the result before printing is optional in the above approach. Thereafter, the space complexity will be optimized to O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!