Given a number N containing digits from 1 to 9 only. The task is to generate a new number using the number N such that the frequency of each digit in the new number is equal to the frequency of that digit in N multiplied by the digit itself.
Note: The digits in the new number must be in increasing order.
Examples:
Input : N = 312
Output : 122333
Explanation : The output contains digit 1 once, digit 2 twice and digit 3 thrice.
Input : N = 525
Output : 225555555555
Explanation : The output contains digit 2 twice and digit 5 ten times. 5 is ten times because its frequency is 2 in the given integer.
Brute Force Approach:
We can use a map to store the frequency of each digit in the given number. Then, for each digit from 1 to 9, we can append that digit to the output string as many times as its frequency multiplied by the digit itself. Finally, we can sort the output string in increasing order and print it.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to print such a numbervoid printNumber(int n){ // Count the frequency of each digit map<int, int> freq; while (n > 0) { freq[n % 10]++; n /= 10; } // Construct the output string string output = ""; for (int i = 1; i <= 9; i++) { if (freq[i] > 0) { for (int j = 0; j < freq[i] * i; j++) output += to_string(i); } } // Sort and print the output string sort(output.begin(), output.end()); cout << output;}// Driver codeint main(){ int n = 3225; printNumber(n); return 0;} |
Java
import java.util.*;public class Main { // Function to print such a number public static void printNumber(int n) { // Count the frequency of each digit Map<Integer, Integer> freq = new HashMap<Integer, Integer>(); while (n > 0) { int digit = n % 10; freq.put(digit, freq.getOrDefault(digit, 0) + 1); n /= 10; } // Construct the output string StringBuilder output = new StringBuilder(); for (int i = 1; i <= 9; i++) { if (freq.containsKey(i) && freq.get(i) > 0) { for (int j = 0; j < freq.get(i) * i; j++) output.append(Integer.toString(i)); } } // Sort and print the output string char[] arr = output.toString().toCharArray(); Arrays.sort(arr); System.out.println(new String(arr)); } // Driver code public static void main(String[] args) { int n = 3225; printNumber(n); }} |
Python3
# Function to print such a numberdef printNumber(n): # Count the frequency of each digit freq = {} while n > 0: freq[n % 10] = freq.get(n % 10, 0) + 1 n //= 10 # Construct the output string output = "" for i in range(1, 10): if freq.get(i, 0) > 0: for j in range(freq[i] * i): output += str(i) # Sort and print the output string print(''.join(sorted(output)))# Driver coden = 3225printNumber(n) |
C#
using System;using System.Collections.Generic;using System.Linq;class Program { // Function to print such a number static void PrintNumber(int n) { // Count the frequency of each digit Dictionary<int, int> freq = new Dictionary<int, int>(); while (n > 0) { if (freq.ContainsKey(n % 10)) { freq[n % 10]++; } else { freq.Add(n % 10, 1); } n /= 10; } // Construct the output string string output = ""; for (int i = 1; i <= 9; i++) { if (freq.ContainsKey(i) && freq[i] > 0) { for (int j = 0; j < freq[i] * i; j++) { output += i.ToString(); } } } // Sort and print the output string Console.WriteLine(output); } // Driver code static void Main(string[] args) { int n = 3225; PrintNumber(n); }} |
Javascript
// Function to print such a numberfunction printNumber(n) { // Count the frequency of each digit let freq = new Map(); while (n > 0) { freq.set(n % 10, (freq.get(n % 10) || 0) + 1); n = Math.floor(n / 10); } // Construct the output string let output = ""; for (let i = 1; i <= 9; i++) { if (freq.get(i) > 0) { for (let j = 0; j < freq.get(i) * i; j++) { output += i.toString(); } } } // Sort and print the output string output = output.split('').sort().join(''); console.log(output);}// Driver codelet n = 3225;printNumber(n); |
Output
222233355555
Time Complexity: O(N LOG N)
Auxiliary Space: O(N)
Approach:
The idea is to store the count or the frequency of the digits in the given number N using a counting array or hash. Now, for each digit add it to the new number, K number of times where K is equal to its frequency in the counting array multiplied by the digit itself.
Below is the implementation of the above approach:
C++
// CPP program to print a number such that the// frequency of each digit in the new number is // is equal to its frequency in the given number // multiplied by the digit itself.#include <bits/stdc++.h>using namespace std;// Function to print such a numbervoid printNumber(int n){ // initializing a hash array int count[10] = { 0 }; // counting frequency of the digits while (n) { count[n % 10]++; n /= 10; } // printing the new number for (int i = 1; i < 10; i++) { for (int j = 0; j < count[i] * i; j++) cout << i; }}// Driver codeint main(){ int n = 3225; printNumber(n); return 0;} |
Java
// Java program to print a number such that the// frequency of each digit in the new number is // is equal to its frequency in the given number // multiplied by the digit itself.import java.io.*;class GFG { // Function to print such a numberstatic void printNumber(int n){ // initializing a hash array int count[] = new int[10]; // counting frequency of the digits while (n>0) { count[n % 10]++; n /= 10; } // printing the new number for (int i = 1; i < 10; i++) { for (int j = 0; j < count[i] * i; j++) System.out.print(i); }}// Driver code public static void main (String[] args) { int n = 3225; printNumber(n); }}// This code is contributed by inder_verma |
Python3
# Python 3 program to print a number such that the# frequency of each digit in the new number is # is equal to its frequency in the given number # multiplied by the digit itself.# Function to print such a numberdef printNumber(n): # initializing a hash array count = [0]*10 # counting frequency of the digits while (n) : count[n % 10] += 1 n //= 10 # printing the new number for i in range(1,10) : for j in range(count[i] * i): print(i,end="")# Driver codeif __name__ == "__main__": n = 3225 printNumber(n) # This code is contributed by# ChitraNayal |
C#
// C# program to print a number such // that the frequency of each digit // in the new number is equal to its // frequency in the given number // multiplied by the digit itself.using System;class GFG {// Function to print such a numberstatic void printNumber(int n){ // initializing a hash array int []count = new int[10]; // counting frequency of // the digits while (n > 0) { count[n % 10]++; n /= 10; } // printing the new number for (int i = 1; i < 10; i++) { for (int j = 0; j < count[i] * i; j++) Console.Write(i); }}// Driver codepublic static void Main () { int n = 3225; printNumber(n);}}// This code is contributed// by inder_verma |
PHP
<?php// PHP program to print a number such // that the frequency of each digit // in the new number is equal to its// frequency in the given number // multiplied by the digit itself.// Function to print such a numberfunction printNumber($n){ // initializing a hash array $count = array(); for($i = 0; $i<= 10; $i++) $count[$i] = 0; // counting frequency of the digits while ($n) { $count[$n % 10]++; $n /= 10; } // printing the new number for ($i = 1; $i < 10; $i++) { for ($j = 0; $j < $count[$i] * $i; $j++) echo $i; }}// Driver code$n = 3225;printNumber($n);// This code is contributed // by Akanksha Rai(Abby_akku) |
Javascript
<script>// JavaScript program to print// a number such that the// frequency of each digit // in the new number is// is equal to its frequency // in the given number// multiplied by the digit itself.// Function to print such a numberfunction printNumber(n){ // initializing a hash array let count = new Uint8Array(10); // counting frequency of the digits while (n) { count[n % 10]++; n = Math.floor(n / 10); } // printing the new number for (let i = 1; i < 10; i++) { for (let j = 0; j < count[i] * i; j++) document.write(i); }}// Driver code let n = 3225; printNumber(n);// This code is contributed by Surbhi Tyagi.</script> |
Output
222233355555
Time Complexity : O(log10n), where n is the given integer.
Auxiliary Space : O(1), no extra space required so it is a constant.
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!
