Given a positive integer N. The task is to print the array in decreasing order in which the numbers are odd powers of 2 and the sum of all the numbers in the array is N and the size of the array should be minimum if it is not possible to form the array then print -1.
Examples:
Input: 18
Output: 8 8 2
Explanation: Array with sum 18 and which consists
minimum numbers with odd powers of 2 are [8 8 2] .
Since 8+8+2=19 and 21=2, 23=8 where 1, 3 are odd numbers.Input: 7
Output: -1
Explanation: Since there is no array with sum equal to 7.
Approach: To solve the problem follow the below idea:
The idea is to create a binary array of size (32) and check the set bit position.If the bit position is odd, store the power of position else store power of (position-1).
Follow the below steps to solve the problem:
- Create a binary array of max size 32 which will store the number’s binary.
- If the number is odd then print -1.
- If the number is even traverse the binary array from the reverse side and check if the bit is 1 and the position of the bit is odd then take its power of 2 and store it in the answer array.
- If the bit is 1 and the position of the bit is even then take the 2 instances of 2^(position-1).
- If the bit is 0 then continue traversing the binary array.
- Print the answer array
Below is the Implementation of the above approach.
C++
// Code for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate power of 2 .int power(int x, int y){ if (y == 0) return 1; else if (y % 2 == 0) return power(x, y / 2) * power(x, y / 2); else return x * power(x, y / 2) * power(x, y / 2);}// Function performing Calculationvector<int> solve(int N){ vector<int> binary(32); vector<int> answer; // Storing the binary of the number // N in the binary array. for (int i = 31; i >= 0; i--) { // Checking if the bit is set // or not if ((N & (1 << i)) != 0) binary[i] = 1; } // Storing power of 2 in the answer // array for (int i = 31; i >= 0; i--) { // If the bit is set and is at odd // position the store the power of // 2 of i. if (binary[i] == 1 && i & 1) { answer.push_back(power(2, i)); } // If the bit is set and is at // even position // then store 2 numbers with // the power of 2 of i-1. else if (binary[i] == 1 && !(i & 1)) { answer.push_back(power(2, i - 1)); answer.push_back(power(2, i - 1)); } else continue; } return answer;}// Driver Functionint main(){ int N = 18; // Checking if the number is odd if (N & 1) { cout << -1 << endl; return 0; } // Function call vector<int> ans = solve(N); for (int x : ans) cout << x << " "; return 0;} |
Java
// Java Code for the above approachimport java.io.*;import java.util.*;class GFG { // Function to calculate power of 2 . public static int power(int x, int y) { if (y == 0) return 1; else if (y % 2 == 0) return power(x, y / 2) * power(x, y / 2); else return x * power(x, y / 2) * power(x, y / 2); } // Function performing Calculation public static ArrayList<Integer> solve(int N) { int binary[] = new int[32]; ArrayList<Integer> answer = new ArrayList<Integer>(); // Storing the binary of the number // N in the binary array. for (int i = 31; i >= 0; i--) { // Checking if the bit is set // or not if ((N & (1 << i)) != 0) binary[i] = 1; } // Storing power of 2 in the answer // array for (int i = 31; i >= 0; i--) { // If the bit is set and is at odd // position the store the power of // 2 of i. if (binary[i] == 1 && (i & 1) != 0) { answer.add(power(2, i)); } // If the bit is set and is at // even position // then store 2 numbers with // the power of 2 of i-1. else if (binary[i] == 1 && (i & 1) == 0) { answer.add(power(2, i - 1)); answer.add(power(2, i - 1)); } else continue; } return answer; } // Driver Code public static void main(String[] args) { int N = 18; // Checking if the number is odd if ((N & 1) != 0) { System.out.println(-1); return; } // Function call ArrayList<Integer> ans = solve(N); for (Integer x : ans) System.out.print(x + " "); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code for the above approachimport math# Function to calculate power of 2 .def power( x, y): if (y == 0): return 1; elif (y % 2 == 0): return power(x, math.floor(y / 2)) * power(x, math.floor(y / 2)); else: return x * power(x, math.floor(y / 2)) * power(x, math.floor(y / 2));# Function performing Calculationdef solve( N): binary = [0]*(32); answer =[]; # Storing the binary of the number # N in the binary array. for i in range(31,0,-1) : # Checking if the bit is set # or not if ((N & (1 << i)) != 0): binary[i] = 1; # Storing power of 2 in the answer # array for i in range(31,0,-1): # If the bit is set and is at odd # position the store the power of # 2 of i. if binary[i] == 1 and i & 1: answer.append(power(2, i)); # If the bit is set and is at # even position # then store 2 numbers with # the power of 2 of i-1. elif binary[i] == 1 and (i & 1)==0: answer.append(power(2, i - 1)); answer.append(power(2, i - 1)); else: continue; return answer;# Driver FunctionN = 18; # Checking if the number is oddif (N & 1): print(-1) # Function callans = solve(N);for x in ans: print(x,end=" "); # This code is contributed by Potta Lokesh |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ // Function to calculate power of 2 . public static int power(int x, int y) { if (y == 0) return 1; else if (y % 2 == 0) return power(x, y / 2) * power(x, y / 2); else return x * power(x, y / 2) * power(x, y / 2); } // Function performing Calculation public static List<int> solve(int N) { int[] binary = new int[32]; List<int> answer = new List<int>(); // Storing the binary of the number // N in the binary array. for (int i = 31; i >= 0; i--) { // Checking if the bit is set // or not if ((N & (1 << i)) != 0) binary[i] = 1; } // Storing power of 2 in the answer // array for (int i = 31; i >= 0; i--) { // If the bit is set and is at odd // position the store the power of // 2 of i. if (binary[i] == 1 && (i & 1) != 0) { answer.Add(power(2, i)); } // If the bit is set and is at // even position // then store 2 numbers with // the power of 2 of i-1. else if (binary[i] == 1 && (i & 1) == 0) { answer.Add(power(2, i - 1)); answer.Add(power(2, i - 1)); } else continue; } return answer; }// Driver Codepublic static void Main(){ int N = 18; // Checking if the number is odd if ((N & 1) != 0) { Console.Write(-1); return; } // Function call List<int> ans = solve(N); foreach (int x in ans) Console.Write(x + " ");}}// This code is contributed by sanjoy_62. |
Javascript
<script> // Code for the above approach // Function to calculate power of 2 . const power = (x, y) => { if (y == 0) return 1; else if (y % 2 == 0) return power(x, parseInt(y / 2)) * power(x, parseInt(y / 2)); else return x * power(x, parseInt(y / 2)) * power(x, parseInt(y / 2)); } // Function performing Calculation const solve = (N) => { let binary = new Array(32).fill(0); let answer = []; // Storing the binary of the number // N in the binary array. for (let i = 31; i >= 0; i--) { // Checking if the bit is set // or not if ((N & (1 << i)) != 0) binary[i] = 1; } // Storing power of 2 in the answer // array for (let i = 31; i >= 0; i--) { // If the bit is set and is at odd // position the store the power of // 2 of i. if (binary[i] == 1 && i & 1) { answer.push(power(2, i)); } // If the bit is set and is at // even position // then store 2 numbers with // the power of 2 of i-1. else if (binary[i] == 1 && !(i & 1)) { answer.push(power(2, i - 1)); answer.push(power(2, i - 1)); } else continue; } return answer; } // Driver Function let N = 18; // Checking if the number is odd if (N & 1) { document.write("-1<br/>"); } // Function call let ans = solve(N); for (let x in ans) document.write(`${ans[x]} `); // This code is contributed by rakeshsahni</script> |
Output
8 8 2
Time Complexity: O(N*log N) where in the worst case N is 32.
Auxiliary Space: O(N) where N is 32.
