## Srinu Kolukuluri

BAN USER1. Good with Data Structures and Algorithms

2. Good with Object Oriented Programming

and a Good Dancer too...,

well, give me an example.

is it the following ????

input: -8754365

output: -3455678

if so, follow the same algo, print the numbers in the map from o'th index to last.

Hi, Let me try

Lets assume the following:

Count of digit 0 is -----> x0

Count of digit 1 is -----> x1

Count of digit 2 is -----> x2

Count of digit 3 is -----> x3

Count of digit 4 is -----> x4

Count of digit 5 is -----> x5

Count of digit 6 is -----> x6

Count of digit 7 is -----> x7

Count of digit 8 is -----> x8

Count of digit 9 is -----> x9

Lenth of given number is ---> n

Take a constant ----> k (I will explain why we needed)

So, the following is true for every digit :

x0<=n, x1<=n, x2<=n, x3<=n, x4<=n, x5<=n, x6<=n, x7<=n, x8<=n, x9<=n (Consider the count of each digit is positive integer only) --- > 0<=xi<=n

x0+x1+x2+x3+x4+x5+x6+x7+x8+x9 = n

Time complexity to access Hash Table:

Here there are two types of cells will be there in our hash table/hash map,

1) Cell of Hash table with zero counts

2) Cell of Hash table with Non-zero counts

Lets assume Number of accesses for ith cell of hash table is “ai”

i.e..., For 0th index ----> a0; 1<=a0<=n

For 1st index ----> a1; 1<=a1<=n

…………….

And so on upto --a9

So,

the total accesses will be: a0+a1+a2+a3+………a9 >=n

Lets put it in this way:

a0+a1+a2+a3+………a9 =n+k

Here, n is to access cells with non-zero count of hash table, k is to access cells with zero count.

Lets take an example:

1) 999999999999999

Hash table = (0 0 0 0 0 0 0 0 0 15)

Accessing time = 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*15

= 15 + 9

= O (n + k), always k<=n

= O(n)

2) 999999998883210

Hash table = (1 1 1 1 0 0 0 0 3 8)

Accessing time = 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*3 + 1*8

= 8 + 3 + 8

= 15 + 4

= O(n + k), always k<=n

= O(n)

Correct me If I am wrong, I Just tried to analyse

Yeah, Simple array would work :) thanks

- Srinu Kolukuluri March 20, 2015We can use Hash Table to optimize further, --> O(n)

Algorithm:

1. Take a hash table with size 10 (0 to 9).

2. Store the count of every digit from 0 to 9.

3. Print the index of the Hash table with respect to digit count in the reverse direction (from 9 to 0).

Example:

Hash table after digit count for 8754365 -> (0 0 0 1 1 2 1 1 1 0)

Print the index of the hash table with respect to their count in reverse order -> 8765543

Time Complexity : O(n)

Correct me if I am wrong.

thanks

Rep**mariawharris2**, Computer Scientist at Adjetter Media Network Pvt Ltd.Hi I am an IT Project Management Professional with 2 years' experience,Handled project development and documentation of copier rentals ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Following is the recursive solution, One can easily derive DP solution.

- Srinu Kolukuluri May 18, 2016Please comment if there is any mistake.

Thanks.

Srinu

#include <iostream>

#include <string>

using namespace std;

int solRec(string str, int low, int high) {

string str1,str2;

str1 = str.substr(low,1);

str2 = str.substr(low,2);

int first = atoi(str1.c_str());

int second = atoi(str2.c_str());

if(low == high) return 1;

if(low+1 == high && second < 27) return 2;

if(low+1 == high && second > 26) return 1;

int res = 0, ret1 = 0, ret2 = 0;

ret1 = solRec(str, low+1, high);

if(second<27)

ret2 = solRec(str, low+2, high);

res = ret1 + ret2;

return res;

}

int main() {

string str;

cin>>str;

int len = str.length();

cout<<solRec(str,0,len-1)<<endl;

return 0;

}