it can be done with O(N * S) time complexity.
where N = number of digits
S = sum
intilize : input[1][j]=0 1=j = S
input[j][0]=1 0=j=N
now fill table using following recurrence :-
input[i][j] = input[i-1][j] or input[i-1][j-input[i]];
now after creating table...check if
Code:-
#includeiostream
#includevector
using namespace std;
void recursion(int sum,int i,vectorint v,int size)
{
vectorint v1=v;
int size1=size;
if(sum==0)
{
for(int k=0;ksize;k++)
coutv[k] ;
coutendl;
}
else
{
for(int j=i+1;j10;j++)
keep a hash to check if digit is already used for that combination or not.
add this logic to existing combinations generator code.
On Sat, Aug 25, 2012 at 12:34 AM, amrit harry dabbcomput...@gmail.comwrote:
find the all possible combination of digits ranging 1 to 9 whose sum is
10,
no digit
find the all possible combination of digits ranging 1 to 9 whose sum is 10,
no digit shud be repeated in any combination.
1234
127
136
145
19
235
28
37
46
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web
Hi,
sorry i mis-understood the problem
ll check and submit asap..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
For the given number n find the minimal positive integer divisable by
n, with the sum of digits equal to n.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from
Hi,
1.find the sum of the digits of the number
[acc. to fact that number+9 has the same sum of the digits as number]
2. for i=sum_of_the_digits_of_the_number; i=number; i=i+9
3.find if number is divisible by i then print it
code:
#includestdio.h
int sum_of_the_digits(int n)
{
if(n==0)
Steps:
1) hashmapping and to keep track of value with its count..
2)now put these elements in 2D array...m[r][2].r - number of different
elements...
1st
col...have... the value..
2nd col...have ..the frequency..
3) Now
@shashank:
sorting the hashed values is more intensive than using the heap with size
K. (as kN)
sorting hash -- N log N
using heap -- N log k
also, i just read about the splay trees.. this can improve the performance
of 'N log N factor' right when used on input, though it can be used on a
@atul approach sounds good but we have to check for each time counts
updated isn't it , though even can sort the hash table return top k
number .
also as i know we have splay tree , even google uses it , to get most
frequent item .
Thanks
Shashank.
--
You received this message because
@Shashank:
well i guess there is one more issue with my algo. if counter is updated
for say number 3.
and heap has already node with value 3 and count 2.
now root could be node with value 5 and count 1.
if i remove root from the heap, then heap will be havingi will be having 2
node with value 3
Trie data structure can be used...
In the trie, you can record item count in each node representing frequency
of word consisting of characters on the path from root to current node.
The time complexity to setup the trie is O(Ln) (where L is number of
characters in the longest item). To find the
we can use hashtable to maintain count of each number coming from the file.
now make a MIN heap of size K
now every time a count is updated in the hastable , compare it with the
root of the Min heap.
if root of heap is smaller then replace it with new greater count and then
heapify again.
In the
@Karthikeyan : i have little doubt in you algorithm...
acc to the question input stream is the stream of numbers not words.
now if we consider Trie , first you have to extract digits from each input
number and use those digit to created trie.
so how will you get k most frequent occurring words
suggest algo to find k most frequently occuring numbers from a file of very
large size containing numbers.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from
Given an array-based heap on n elements and a real number x, efficiently
determine whether the kth smallest element in the heap is greater than or
equal to x. Your algorithm should be O(k) in the worst-case, independent of
the size of the heap.
This question was also asked in Amazon
--
You
O(k) in the worst-case , then i guess it would better to use
median-of median algo to find element at rank k. and comparing with x.
or
we can us hashtable to solve this.
On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote:
Given an array-based heap on n elements and a real
Why can't we keep removing the minimum element each time and compare it
with x? This should take O(k) time since in a Min heap, the minimum element
can be removed in O(1) time? Am I missing something?
On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.com wrote:
O(k) in the
@gaurav : you need to first build heap and then maintain heap property ever
time you remove element.so this would take O(n logn ).
On Wed, Dec 14, 2011 at 1:38 AM, Gaurav Kumar gkuma...@gmail.com wrote:
Why can't we keep removing the minimum element each time and compare it
with x? This
One approach could be using the file.
Say x = 50 %, so every alternate run, the output should be true.
1. First run, store 0.5 in the file
2. Second run, add 0.5 to the previous value
3. Check if the sum is 1.d where 0 = d 1, return true and store 0.d in
the file
We can extend the same logic
@nitin : as mentioned in the subject , its for Apple
BTW @siddharth , i did not understand your question . little more
explanation please.
On Mon, Nov 28, 2011 at 7:14 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
Please clarify. Also tell offcampus interview for which company?
On Mon, Nov
Please clarify. Also tell offcampus interview for which company?
On Mon, Nov 28, 2011 at 7:10 PM, Siddharth Pipriya sid@gmail.comwrote:
write a program that takes as input a number x and gives output true x
percent of the time it is run.
--
You received this message because you are
22 matches
Mail list logo
