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
Repmariawharris2, 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 ...
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;
}