Python program to find the largest prime factor of the number

Recently I started learning Python. Having programmed in C, C++ and Java up to now, I found it rather different, but easy :). Here is my small and first ("Hello World" is too boring now!) program in Python-

#Computes the largest prime factor for the number
#Solution for Problem 3 on Project Euler.net

import math

x = int(raw_input('Enter Number : '))
max_factor = 2

i = (x+1)/2

while i > 1:
    if x % i == 0:
        j = 2
        while j <= int(math.sqrt(i)):
            if i % j == 0:
                break
            j = j + 1
        else:
            max_factor = i
            break
    i = i - 1

print max_factor

To find all the prime factors just use a list instead of max_factor, and keep appending "i" to it. Also remove the 'break' statement in 'else:'.

Reverse a linked list in group of k

This is one of a candidate interview question. I don't see any practical application of this-

Given a linked list, reverse the list in groups of size k. 

I am sure it is not clear to you, so here is a example-
Input -    1=>2=>3=>4=>5=>6=>7=>8
Output -  3=>2=>1=>6=>5=>4=>8=>7

Try solving it yourself before going through the code.

#include <stdio.h>
#include <stdlib.h>

typedef struct node 
{
 int v;
 struct node *next;
} node;

node * revk(node *head, int k)
{
 int i = 1;
 node *p, *b, *s1, *s2, *t;
 p = head;
 b = NULL;
 s1 = NULL;
 s2 = head;

 while (p)
 {
  t = p;
  p = p->next;
  if (t)
   t->next = b;
  b = t;

  if (i == k)
  {
   if (s1)
    s1->next = b;
   else
    head = b;
   s1 = s2;
   s2 = p;
   i = 0;
  }
  i++;
 }
 s1->next = b;
 s2->next = NULL;
 return head;
}

void print(node *head)
{
 node *p = head;
 while (p)
 {
  printf("%d -> ", p->v);
  p = p->next;
 }
 printf("$\n");
}

void insert(node **t, int v)
{
 node *p = malloc(sizeof(node));
 p->v = v;
 p->next = NULL;
 (*t)->next = p;
 *t = p;
}

int main(int argc, char *argv[])
{
 node *head, *tail = NULL;
 head = malloc(sizeof(node));
 head->next = NULL;
 head->v = 1;
 tail = head;
 insert(&tail, 2); 
 insert(&tail, 3); 
 insert(&tail, 4); 
 insert(&tail, 5); 
 insert(&tail, 6); 
 insert(&tail, 7); 
 insert(&tail, 8);

 print(head);

 head = revk(head, 3);

 print(head);

 tail = head;

 while (tail)
 {
  head = tail;
  tail = tail->next;
  free(head);
 }

 printf("\n");
 return 0;
}

C Program : Rank of a word

Rank of a word is the position of the word when all the permutations of the letters in the word are listed in dictionary order. So for example "cat" is the word, then, various permutations in dictionary order are-

1. act
2. atc
3. cat
4. cta
5. tac
6. tca

Hence the rank of "cat" is 3.
Here is the logic in short-

Sort the word, find number of permutations that can be formed with letters which come before i^th letter in original word.

So for i = 0, i^th letter is 'c' and the sorted word is "act", so we need to find all permutations starting with 'a' and so on.

Below is the program that takes care of duplicates as well.

#include <stdio.h>
#include <string.h>

long fact(int n)
{
 long f = 1;
 while (n > 0)
 {
  f *= n;
  n--;
 }
 return f;
}

int find_rank(char s[], int len)
{
 long rank = 1;
 int i, j, k, l, fr[26], f; //fr is frequency
 char sorted[100], cur, t, pre;

 for (i = 0; i < len -1 ; ++i)
 {
  cur = s[i];
  strcpy(sorted, s + i);
  l = len - i;
  memset(fr, 0, sizeof(fr));
  fr[sorted[0] - 'a']++;
  for (j = 1; j < l; ++j)
  {
   t = sorted[j];
   fr[t-'a']++;
   for (k = j-1; k >=0 && sorted[k] > t; --k)
    sorted[k+1] = sorted[k];
   sorted[k+1] = t;
  }
  pre = 1;
  for (k = 0; sorted[k] != cur ;++k)
  {
   if (sorted[k] == pre)
    continue;
   pre = sorted[k];

   f = fact(l - 1);
   fr[pre - 'a']--;
   for (j = 0; j < 26; ++j)
    if (fr[j])
     f /= fact(fr[j]);
   rank += f;
   fr[pre - 'a']++;
  }
 }
 return rank;
}

int main()
{
 char s[100];
 
 scanf("%s", s);
 printf("%d", find_rank(s, strlen(s)));
 return 0;
}

C++ Program - Finding the kth element in a dynamic sorted list

A common programming problem goes something like -

To find the k^th minimum(/maximum) element in a dynamic list, which is kept sorted.

The catch here is that, the list is dynamic, i.e. the list is increasing in size (due to insertion of element), and at any instant, you may be asked to report the k^th minimum element.

There are in general 3 approaches (considering we have 'n' elements at any instant)-

1. To have O(1) insertion, i.e insert at the end of the list. And O(n log n) search, i.e when asked to give k^th element, sort the list and output the element at k^th offset. As is evident, if the queries are frequent this approach is not going to be efficient.
2. To have O(n) insertion, i.e insert the new element at its correct position in sorted list by shifting all elements from  k^th to  n^th offset by 1. And to have O(1) output. Again this is not very efficient as it is O(n²) overall.
3. To have O(log n) insertion and O(1) output time. Now this seems rather efficient! This is overall O(n log n). This is the method I am discussing below.

The difference in second and third approach is that we use a array in former and 2 heaps in later.

Using 2 heaps-

If we need the  k^th minimum element, we will need 2 heaps. One is a MIN heap other is a MAX heap. And at any time we need to ensure that MAX heap has exactly 'k' elements and MIN heap has the rest (N-K). Then the  k^th element is at the top of MAX heap at any time. Let me illustrate with an example, followed by a C++ program.

Consider a stream of insertion and queries (?), for k = 4 - 

9 5 4 7 ? 6 2 ? 1 ? 2 ?

Stream	MIN heap	MAX heap	Output
9		9
5		9 5
4		9 5 4
7		9 7 5 4
?		9 7 5 4	9
6	9	7 6 5 4
2	7 9	6 5 4 2
?	7 9	6 5 4 2	6
1	6 7 9	5 4 2 1
?	6 7 9	5 4 2 1	5
2	5 6 7 9	4 2 2 1
?	5 6 7 9	4 2 2 1	4

Now there are several points to be noted -

• For first k insertions, we are not able to maintain the size of MAX heap as k. But we insert all of the first k elements in MAX heap.
• After k elements are inserted, and we have new element "x", then we compare x with MAX heap's top "t". If x > t, we insert x in MIN heap, else we delete t from MAX heap, and put it in MIN heap, and then insert x in MAX heap.
• Do we really need MIN heap? This is a question that should come in your mind. Answer is No! Just throw the numbers being inserted in MIN heap. This method is so general that it can be easily adapted for problems in which k is not a number but a fraction. Like to output the 1/3th element. In that case just maintain size of MAX heap to 1/3 of total. In this you may have to transfer elements from MIN heap to MAX heap as well.
• C++ does not have Heap data structure, at least not with the name "heap". Either you can create your own, or use Priority Queue in STL. 

So here is the program-

#include <iostream>
#include <queue>

using namespace std;

class Rlong //Reverse Long
{
 long m_l;
public:
 Rlong(long l) : m_l(l)
 { }
 operator long const &() const
 { return m_l; }
 bool operator<(Rlong const &right) const
 { return m_l > right.m_l; }
};

int main()
{
 long n, k, x, y, i;

 priority_queue<Rlong> minpq;
 priority_queue<long>  maxpq;

 cin >> n >> k;

 for (i = 0; i < k; ++i)
 {
  cin >> x;
  maxpq.push(x);
 }
 for (; i < n; ++i)
 {
  cin >> x ;
  if (x != -1) // assuming -1 as '?'
  {
   if (x < maxpq.top())
   {
    y = maxpq.top();
    maxpq.pop();
    maxpq.push(x);
    minpq.push(y);
   }
   else
   {
    minpq.push(x);
   }
  }
  else
  {
   x = maxpq.top();
   cout << x;
  }
 }
 return 0;
}