|
Given an integer N, the task is to represent N as the sum of numbers such that the numbers can only be formed using the digits 0 and 1 and the total numbers used should be minimum.
Example:
Input: n = 9
Output:
9
1 1 1 1 1 1 1 1 1
Input: n = 32
Output:
3
10 11 11
Approach:
The requirement can be achieved by iteratively constructing the representation using powers of 10, starting from the most significant digit. The maximum digit encountered during the process determines the number of digits needed in the final representation.
Step by step algorithm:
- Set variables n, a[15], i, j, and k. where n is the given integer, a[15] is an array to count occurrences of digits, and i, j, k are loop variables and a variable to track the maximum digit.
- Start a loop (for) where i iterates over powers of 10 (1, 10, 100, …).
- Inside the loop:
- Calculate j as the current digit in the ith place (n/i%10).
- Update k as the maximum of k and j.
- For each non-zero value of j:
- Increment the corresponding count in the array a.
- This step effectively adds powers of 10 to the representation.
- Print the maximum digit k.
- Print the representation using the array a.
Illustration:
Initialization:
- n = 32
- i = 1, j = 0, k = 0
First Iteration (i = 1):
- Extract the rightmost digit: j = n / i % 10 = 32 / 1 % 10 = 2
- Update maximum digit to 2.
- Iterate through each non-zero value of the digit (j = 2):
- a[2] += 1; (Add 1 to the representation of 2)
Second Iteration (i = 10):
- Extract the next digit: j = n / i % 10 = 32 / 10 % 10 = 3
- Update maximum digit to 3.
- Iterate through each non-zero value of the digit (j = 3):
- a[3] += 10; (Add 10 to the representation of 3)
Third Iteration (i = 100):
- Extract the next digit: j = n / i % 10 = 32 / 100 % 10 = 0
- Maximum digit remains 3 (no change).
- Since j is 0, nothing is added to the representation.
Output:
- Maximum Digit: 3
- Representation: 11 11 10
Below are the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int n, a[15], i, j, k;
int main()
{
n = 32;
for (i = 1; i <= n; i *= 10) {
j = n / i % 10;
k = max(k, j);
for (; j; --j)
a[j] += i;
}
printf("%d\n", k);
for (i = k; i; --i)
printf("%d ", a[i]);
return 0;
}
|
Java
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int n = 32;
int[] a = new int[15];
int i, j, k = 0;
for (i = 1; i <= n; i *= 10) {
j = n / i % 10;
k = Math.max(k, j);
for (; j > 0; --j) {
a[j] += i;
}
}
System.out.println(k);
for (i = k; i > 0; --i) {
System.out.print(a[i] + " ");
}
}
}
|
Python3
n = 32
a = [0] * 15
i, j, k = 1, 0, 0
while i <= n:
j = n // i % 10
k = max(k, j)
while j:
a[j] += i
j -= 1
i *= 10
print(k)
for i in range(k, 0, -1):
print(a[i], end=" ")
|
C#
using System;
class Program {
static void Main()
{
int n = 32;
int[] a = new int[15];
int i, j, k = 0;
for (i = 1; i <= n; i *= 10) {
j = n / i % 10;
k = Math.Max(k, j);
for (; j > 0; j--)
a[j] += i;
}
Console.WriteLine(k);
for (i = k; i > 0; i--)
Console.Write($"{a[i]} ");
}
}
|
Javascript
let n = 32;
let a = new Array(15).fill(0);
let i, j, k = 0;
for (i = 1; i <= n; i *= 10) {
j = Math.floor((n / i) % 10);
k = Math.max(k, j);
for (; j; j--) {
a[j] += i;
}
}
console.log(k);
for (i = k; i; i--) {
process.stdout.write(`${a[i]} `);
}
|
Time Complexity: O(log n), where n is the input integer.
Auxiliary Space: O(1)
|
