Generate a number such that the frequency of each digit is digit times the frequency in given number

0 0 7 minutes read

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 number
void 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 code
int 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 number
def 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 code
n = 3225
printNumber(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 number
function 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 code
let 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 number
void 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 code
int 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 number
static 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 number
def 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 code
if __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 number
static 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 code
public 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 number
function 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 number
function 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(log₁₀n), 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 zambiatek!