Given are two integers (x and n). The task is to find an array such that it contains the frequency of index numbers occurring in (x^1, x^2, …., x^(n-1), x^(n) ).
Examples:
Input: x = 15, n = 3 Output: 0 1 2 2 0 3 0 1 0 0 Numbers x^1 to x^n are 15, 225, 3375. So frequency array is 0 1 2 2 0 3 0 1 0 0. Input: x = 1, n = 5 Output: 0 5 0 0 0 0 0 0 0 0 Numbers x^1 to x^n are 1, 1, 1, 1, 1. So frequency of digits is 0 5 0 0 0 0 0 0 0 0.
Approach:
- Maintain a frequency count array to store the count of digits 0-9.
- Traverse through each digit from x^1 to x^n, for each digit add 1 to the corresponding index in the frequency count array.
- Print the frequency array
Below is the implementation of the above approach:
C++
// CPP implementation of above approach#include<bits/stdc++.h>using namespace std;// Function that traverses digits in a number and// modifies frequency count arrayvoid countDigits(double val, long arr[]){ while ((long)val > 0) { long digit = (long)val % 10; arr[(int)digit]++; val = (long)val / 10; } return;}void countFrequency(int x, int n){ // Array to keep count of digits long freq_count[10]={0}; // Traversing through x^1 to x^n for (int i = 1; i <= n; i++) { // For power function, both its parameters are // to be in double double val = pow((double)x, (double)i); // calling countDigits function on x^i countDigits(val, freq_count); } // Printing count of digits 0-9 for (int i = 0; i <= 9; i++) { cout << freq_count[i] << " "; }}// Driver codeint main(){ int x = 15, n = 3; countFrequency(x, n);}// This code is contributed by ihritik |
Java
// Java implementation of above approachimport java.io.*;import java.util.*;public class GFG { // Function that traverses digits in a number and // modifies frequency count array static void countDigits(double val, long[] arr) { while ((long)val > 0) { long digit = (long)val % 10; arr[(int)digit]++; val = (long)val / 10; } return; } static void countFrequency(int x, int n) { // Array to keep count of digits long[] freq_count = new long[10]; // Traversing through x^1 to x^n for (int i = 1; i <= n; i++) { // For power function, both its parameters are // to be in double double val = Math.pow((double)x, (double)i); // calling countDigits function on x^i countDigits(val, freq_count); } // Printing count of digits 0-9 for (int i = 0; i <= 9; i++) { System.out.print(freq_count[i] + " "); } } // Driver code public static void main(String args[]) { int x = 15, n = 3; countFrequency(x, n); }} |
Python 3
# Python 3 implementation # of above approachimport math# Function that traverses digits # in a number and modifies # frequency count arraydef countDigits(val, arr): while (val > 0) : digit = val % 10 arr[int(digit)] += 1 val = val // 10 return;def countFrequency(x, n): # Array to keep count of digits freq_count = [0] * 10 # Traversing through x^1 to x^n for i in range(1, n + 1) : # For power function, # both its parameters # are to be in double val = math.pow(x, i) # calling countDigits # function on x^i countDigits(val, freq_count) # Printing count of digits 0-9 for i in range(10) : print(freq_count[i], end = " ");# Driver codeif __name__ == "__main__": x = 15 n = 3 countFrequency(x, n)# This code is contributed # by ChitraNayal |
C#
// C# implementation of above approachusing System;class GFG {// Function that traverses digits // in a number and modifies // frequency count arraystatic void countDigits(double val, long[] arr){ while ((long)val > 0) { long digit = (long)val % 10; arr[(int)digit]++; val = (long)val / 10; } return;}static void countFrequency(int x, int n){ // Array to keep count of digits long[] freq_count = new long[10]; // Traversing through x^1 to x^n for (int i = 1; i <= n; i++) { // For power function, both its // parameters are to be in double double val = Math.Pow((double)x, (double)i); // calling countDigits // function on x^i countDigits(val, freq_count); } // Printing count of digits 0-9 for (int i = 0; i <= 9; i++) { Console.Write(freq_count[i] + " "); }}// Driver codepublic static void Main(){ int x = 15, n = 3; countFrequency(x, n);}}// This code is contributed // by Shashank |
PHP
<?php// PHP implementation of above approach// Function that traverses digits // in a number and modifies // frequency count arrayfunction countDigits($val, &$arr){ while ($val > 0) { $digit = $val % 10; $arr[(int)($digit)] += 1; $val = (int)($val / 10); } return;}function countFrequency($x, $n){ // Array to keep count of digits $freq_count = array_fill(0, 10, 0); // Traversing through x^1 to x^n for ($i = 1; $i < $n + 1; $i++) { // For power function, // both its parameters // are to be in double $val = pow($x, $i); // calling countDigits // function on x^i countDigits($val, $freq_count); } // Printing count of digits 0-9 for ($i = 0; $i < 10; $i++) { echo $freq_count[$i] . " ";}}// Driver code$x = 15;$n = 3;countFrequency($x, $n)// This code is contributed by mits?> |
Javascript
<script>// Javascript implementation of above approach // Function that traverses digits in a number and // modifies frequency count array function countDigits(val,arr) { while (val > 0) { let digit = val % 10; arr[digit]++; val = Math.floor(val / 10); } return; } function countFrequency(x,n) { // Array to keep count of digits let freq_count = new Array(10); for(let i=0;i<10;i++) { freq_count[i]=0; } // Traversing through x^1 to x^n for (let i = 1; i <= n; i++) { // For power function, both its parameters are // to be in double let val = Math.pow(x, i); // calling countDigits function on x^i countDigits(val, freq_count); } // Printing count of digits 0-9 for (let i = 0; i <= 9; i++) { document.write(freq_count[i] + " "); } } // Driver code let x = 15, n = 3; countFrequency(x, n);// This code is contributed by avanitrachhadiya2155</script> |
Output
0 1 2 2 0 3 0 1 0 0
Complexity Analysis:
- Time complexity: O(nlogn) since using a pow function “logn time complexity” inside a for loop
- Auxiliary Space: O(10)
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!
