The way i see it this problem is a bit more complicated.
Say, for example the given no. is X = 2^3 * 3^5 ... Now if we want to
reduce X in the form M^N where both M and N 1 then its not possible.
Hence, the actual problem reduces to finding not only the prime
factors but actual prime
@Gene :
sorting given input will give:-
1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
consider 2-d array;
4 3 5 2 1 - frequency of corresponding unique data at position arr[1][]
1 2 3 4 5 - unique data
min-heapify arr[0][] - first row and keep track of
the corresponding frequency.
now extract-min and
Hello Sid
Your code is working for N=4,8 but failing when N=9
9 is expressed as 3^2 but your code is giving output as :Not possible.
On Dec 26, 9:36 pm, sid1 siddhantkhann...@gmail.com wrote:
This algorithm won't work as primes might have different power. for
eg. N=12
12 is divisible by 2
@sunny
I became an active follower of this group recently.. May be that's the
reason i didn't realize it... You are right, once u post, a text
appears at the bottom of the page saying that its moderated...
Well if the moderators feel that it helps in reducing spams then
that's great... :)
Well
As you are looking for a dp app...
@ Non-Decreasing Digits
Say the no. of digits is N..
Lets take an array A[9] to store the individual intermediate counts...
if (N 1)
{
int iter = 0;
int totalCount = 10; // this is when N = 1 ...
for (int i=0; i 9; ++i)
A[i] = 1;
considering number to be a 32 number(also applicable in the same way to 64 bit)
one possibility is
let x be the number
find log10x
for 32 bit numbers max value of n is 64
so for n = 1 to 64
find p = logx10/n
take antilog and take nearest integer as m
m = 10^p;
again find m^n
if it is equal to x
@Sid small Modification in ur code in 3rd line it should be float ans
= log(n)/log(i); instead of float ans = log(n)/log(2);
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@above
A slight correction in the above code, inside the while loop..
while(++iter N)
{
for (int i = 8; i 0 ; --i)
{
A[i]+= A[i-1];
totalCount +=A[i];
}
totalCount+=1;
}
On Dec 27, 9:34 pm, Lucifer sourabhd2...@gmail.com wrote:
As you are looking for a dp app...
@another app...
slightly different code for the while loop...
while(++iter N)
{
for (int i = 0; i 9 ; ++i)
{
A[i] = ( A[i] * (i + iter) ) / iter ;
totalCount +=A[i];
}
}
On Dec 27, 9:36 pm, Lucifer sourabhd2...@gmail.com wrote:
@above
A slight correction in the above
I think u hav misunderstood my logic .
I told What comes to my mind is to get all PRIME FACTORS from 2 to
SQRT(N) [Prime Sieve] , Here N is the Given Integer .
So I wrote the code and let me know if there is any problem :-
#includecstdio
#includeiostream
#includecmath
using namespace
Continued:--
Sry , I misunderstood the problm I thought it to be the power of Prime
factor ...
For finding the required answer of N can be done N = a^p b^q
Need to find the hcf of (p,q,...) 1 then the number can be
expressed as m^n ..
--
You received this message because you are
Hey Guys,
Why suddenly all the posts are being moderated.. I think by doing so
we will fall out of sync on who is posting what.. Do you guys agree ?
I think the posts should be updated instantly.. What do u think?
--
You received this message because you are subscribed to the Google Groups
this is not suddenly, this is happening from the last few months, you
might not have noticed.
this was done because of a lot of unrelated topics and interview queries.
one better thing that can be done is to allow some users for direct posting :)
On Tue, Dec 27, 2011 at 3:34 PM, Lucifer
isn't the solution is counting sort?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, Dec 24, 2011 at 11:48 PM, atul anand atul.87fri...@gmail.comwrote:
first sort the given array , you will get
1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
now count
fine we will do that.
On Tue, Dec 27, 2011 at 6:57 PM, SAMMM somnath.nit...@gmail.com wrote:
Yess I agree. The post very often comes out of sync giving rise to
confusion . And also it get difficult to follow up with the
continuation of the previous post .
Atleast the post should be queued
int row = 0;
int col = 0;
int prevColCnt = 0;
int rowMax = 0;
while (row N)
{
while (col N)
A[row][col] == 1 ? col++ : break;
if (prevColCnt col)
{
prevColCnt = col;
rowMax = row;
}
row++;
}
printf(%d, rowMax);
If there are more than one rows with max 1's, then
start from first row i=0;
move right until you find 1.
if you find 0 , say at index j ( arr[0][j] ), them one row down i.e at
row[1][j]and then move right.
continue in this this fashion and keep track row at which latest '1' is
found.
when you reach j=N...you will have the row index which has
@shashank and @samm: Is the deletion and searching is o(1). I doubt
On Sat, Oct 1, 2011 at 6:30 PM, SAMM somnath.nit...@gmail.com wrote:
Yaa it will work , but in case of deletion don't u think array will
not as efficient as linked list becoz array is Static we need to
define the memory b4
Yess I agree. The post very often comes out of sync giving rise to
confusion . And also it get difficult to follow up with the
continuation of the previous post .
Atleast the post should be queued in the order it is coming and after
validating the post , it can be posted in the same order as
in above algo..little correction.
move down every time you find 0 , and move right every time you find 1.
On Tue, Dec 27, 2011 at 3:42 PM, atul anand atul.87fri...@gmail.com wrote:
start from first row i=0;
move right until you find 1.
if you find 0 , say at index j ( arr[0][j] ), them one
@Arun..
If the no. of elements are odd then the median would be the middle
element... But, diff would be 0.
In case of even elements diff is either -1 or 1.
To prove the above,
Say currently diff is -1. and say maxH has X elements. That means minH
has X+1 elements.
Hence the total no. of
@ SAmmm
Also i would like to mention that we don't need to explicitly
calculate all the primes...All we need to do is cancel out the factors
and keep track of the powers..
On Dec 26, 11:43 pm, SAMMM somnath.nit...@gmail.com wrote:
Continued:--
Sry , I misunderstood the problm I thought it to
int max_ones(int mat[N][N])
{
int r = 0, c = 0;
while(r N) {
if(c N mat[r][c] == '1')
++c;
else
++r;
}
return c;
}
On Dec 27, 3:24 am, jyoti saini jyotisaini1...@gmail.com wrote:
A NxN matrix is given containing only 1’s and 0’s. Every row is
A NxN matrix is given containing only 1’s and 0’s. Every row is sorted in
descending order. Find the row containing maximum no. of ones.
time complexity-O(n);
--
Jyoti Saini.
B.Tech-Final year.
Information Technology.
National Institute of Technology,Kurukshetra.
Alt Email jsa...@yahoo-inc.com
Hi
I have jus started to learn DP and I have coded the standard
algorithms(LCS,etc).
I have been trying these problems in SPOJ:
http://www.spoj.pl/problems/NOVICE63/
http://www.spoj.pl/problems/NY10E/
I understand these may be solved elegantly using DP,but I dont get to
code the same.
Can any1
I know tht it need GCD(a,b,) where N = p^a q^b...
I wrote it previously ... it's just tht my lates reply is not in
sequence . I hav added tht later ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@Ashish : not exactly ...
you can use counting sort 1st part where you find the frequency of each
elements. now u have to select frequency in decreasing order to give the
required output.
On Tue, Dec 27, 2011 at 7:49 PM, Ashish Goel ashg...@gmail.com wrote:
isn't the solution is counting
@Sammm
I have jolted down the code in my previous post... Have a look.. it
works on the GCD basis..
On Dec 26, 11:43 pm, SAMMM somnath.nit...@gmail.com wrote:
Continued:--
Sry , I misunderstood the problm I thought it to be the power of Prime
factor ...
For finding the required answer of N
I think the first problem involves some mathematics...
In this we fix the first bit and if the remaining no. of bits are odd then
we calculate the no. as follows
If we have 2^4=16 then total bits 5 so we do not include this.
Total no. of bits in one less than the given no. (in this eg. 15) is 4.
Find the longest continuous subsequence of numbers in an unsorted
array such that difference between any two nos. in that sequence
should not be more than K.
For example:
2,1,8,12, 10,15, 13, 25 and k=7
8,12,10,15,13 is the sequence (15-8=7)
--
You received this message because you are
@All
i was searching fr some better way for i/o . i came across this code and
many similar examples on net.
i think asm can provide a way to load .output directly nd take input
directly from i/o registers . but due to me being new to
asm these code's are giving me trouble.
It's an ATT type asm
@ Special Nos..
Well the actual logic would be :
int count = 0;for ( int i = 2; i = LOGbase2(N) ; i+=2) count+=
[ (i-1) C (i/2) ] ; // here xCy is nothing but the no. of ways y items
can be selected from a collection of x items.
Hence, the working code:
int totalCount = 0;
int interCnt = 1;
if (
Given a string of length N, find whether there exits an even length
palindrome substring.
what would be efficient way of solving this problem.?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@Lucifier:
Thanks a lot..
But,I am able to follow the code that u posted for Non-Decreasing Digits.
Can u jus explain ur algo instead of givin the code directly?
Thanks once again.
On Tue, Dec 27, 2011 at 10:44 PM, Lucifer sourabhd2...@gmail.com wrote:
@ Special Nos..
Well the actual logic
@Sammm Yes you are correct. I wrote 2 by mistake.
it should be i. because (log n)/log i = log n to the base i. So if i^m
= n
=log n to the base i = integer.
@Lucifer I think that your approach is the best optimized. My algo is
testing all the numbers while yours uses only prime factors of N.
On
*I am not able to follow..
On Tue, Dec 27, 2011 at 11:47 PM, kumar rajat thebossku...@gmail.com wrote:
@Lucifier:
Thanks a lot..
But,I am able to follow the code that u posted for Non-Decreasing Digits.
Can u jus explain ur algo instead of givin the code directly?
Thanks once again.
On
Given an inorder traversal only for a binary tree (not necessarily a
BST), give a pseudo code to generate all possible binary trees for
this traversal sequence.
Firstly, how many binary trees can be generated given an in-order
traversal? I know that given 'n' nodes, number of BTs possible is
int maxOnes(int arr[n][n])
{
int maxOnesRow = 0;
int i=j=0;
while( in jn ) {
if (arr[i][j]) {
j++;
}
else {
maxOnesRow = i++;
}
return maxOnesRow;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
one solution could be :-
hash every even number substring , starting from beginning.
after this.
hash every even number substring , starting from end.
if it exists..means palindrome exists.
complexity would be O(N^2).
On Tue, Dec 27, 2011 at 11:06 PM, atul007 atul.87fri...@gmail.com wrote:
Here I can think of O( n * log n ). can anyone think of better solution??
On Tue, Dec 27, 2011 at 11:06 PM, atul007 atul.87fri...@gmail.com wrote:
Given a string of length N, find whether there exits an even length
palindrome substring.
what would be efficient way of solving this problem.?
Find all possible permutations of a given string? I have got a
solution which takes (O(n!)) space. Can anybody help me in finding
this efficiently.
--
With love and regards,
Sairam Ravu
I M.Tech(CS)
Sri Sathya Sai Institute of Higher Learning
To live life, you must think it, measure it,
Have a look at this algo :- Steinhaus–Johnson–Trotter algorithm .
--
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
This might help..
http://groups.google.com/group/algogeeks/browse_thread/thread/d3dafdcd53f101a9#
On Dec 28, 11:53 am, SAMMM somnath.nit...@gmail.com wrote:
Have a look at this algo :- Steinhaus–Johnson–Trotter algorithm .
--
You received this message because you are subscribed to the Google
@all
plz point out wat's wrong with this code. works for small numbers but fails
for large number's
#includeconio.h
#includeiostream
using namespace std;
unsigned int find_nCp(unsigned int n,unsigned int p)
{ unsigned int j=p;
unsigned int num=1,den=1;
for(;j;j--)
Hi,
Using Backtracking,
void swap(char* x,char* y)
{
char temp;
temp=*x;
*x=*y;
*y=temp;
}
void permute(char* a,int i,int n)
{
int j;
if(i==n)
printf(%s\n,a);
else
{
for(j=i;j=n;j++)
{
swap((a+i),(a+j));
permute(a,i+1,n);
swap((a+i),(a+j));
}
}
}
But this takes O(n*n!) time
--
You received
45 matches
Mail list logo
