Problem #1

Little penguin Polo adores strings. But most of all he adores strings of length n.

One day he wanted to find a string that meets the following conditions:

1. The string consists of n lowercase English letters (that is, the string's length equals n), exactly k of these letters are distinct.
2. No two neighbouring letters of a string coincide; that is, if we represent a string as s = s₁s₂... s_n, then the following inequality holds, s_i ≠ s_i + 1(1 ≤ i < n).
3. Among all strings that meet points 1 and 2, the required string is lexicographically smallest.

Help him find such string or state that such string doesn't exist.

String x = x₁x₂... x_p is lexicographically less than string y = y₁y₂... y_q, if either p < q and x₁ = y₁, x₂ = y₂, ... , x_p = y_p, or there is such number r (r < p, r < q), that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 < y_r + 1. The characters of the strings are compared by their ASCII codes.

Input

A single line contains two positive integers n and k (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 26) — the string's length and the number of distinct letters.

Output

In a single line print the required string. If there isn't such string, print "-1" (without the quotes).

Sample test(s)

input

7 4

output

ababacd

input

4 7

output

-1

Solution

Solution for the above problem can be downloaded from here

Sum Of Subset (Using PowerSet)

for those who don't know sum of subset problem just google it.

But allow me to explain what is power set 

e.g. let X be an set, X = { 1,2,3}
then power set will contain = 2^n subset of set X, where n is no. of elements in set X
so our power set will contain total 8 subset of set X
power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
notice that the 1st set is a null set because a null set is a subset of every set.

Now consider sum of subset problem 
let X be an array which contains input from user let X = {1,2,3}
then power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
let m = 3

then the output of sum of subset problem is { {3},{1,2} }

if you are reading from beginning than now you must have a fair idea about what we are going to do, if you didn't understand than chill, the concept will be very clear in 5 minutes from now.

once we have computed the power set, we will take each individual set from the power set, if the power set contains only 1 element than we will compare that element with m if that element is equal to m than we will print that set as  1 of the solution, but if set contain multiple elements in it than we will add them all and compare the sum with m if it is equal than we will print the set. that's it!

Program:

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;


 //@author Naved Momin navedmomin10@gmail.com;

public class SumOfSubsets {


    public ArrayList powerSet(int a[]){
        ArrayList pw = new ArrayList();
        
        pw.add(" ");
        for (int i = 1; i <= a.length; i++) {
            ArrayList tmp = new ArrayList();
            
            for (String e : pw) {
                if(e.equals(" "))
                    tmp.add(""+a[i-1]);
                else
                    tmp.add(e+ " " + a[i-1]);
            }
            pw.addAll(tmp);
        }
       
        return pw;
    }
    int m ;
   
    
    public void navedsSOS( ArrayList p ){
        int sum = 0;
        System.out.println( "output: ");
        for (String string : p) {
            
                String[] split = string.split(" ");
                
                if(split.length > 1){
                    for (String no : split) {
                    sum += Integer.parseInt(no); 
                    }
                    if( sum == m){
                        if(!set.contains(string)){
                            set.add(string);
                            System.out.println( string );
                           
                        }
                    }
                    sum = 0;
                }else if( split.length == 1){
                    int k = Integer.parseInt(string);
                    if( k == m ){
                        if(!set.contains(string)){
                            System.out.println( " " + k );
                            set.add(string);
                        }
                    }

                }
            
        }
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SumOfSubsets s = new SumOfSubsets();
        s.init();
    }
    int n ;
    int arr[];
    Scanner s = new Scanner(System.in);
    Set set = new LinkedHashSet();
    private void init() {
        System.out.println( "enter n ");
        n = s.nextInt();
        System.out.println( "enter m ");
        m = s.nextInt();
        arr = new int[n];
        System.out.println( "enter elemets ");
        
        
        
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
                    
            //set.add(arr[i]);
        }
  
        ArrayList powerSet = powerSet(arr);
        navedsSOS(powerSet);
    }
}

outout:

Round Robin In Java

for those who don't know Round Robin algorithm

Program

import java.util.Scanner;

 
 //@author Naved Momin naved.spartans.rocks75@gmail.com/navedmomin10@gmail.com
 
public class SimpleRR {

    int [] temp;
    int commBT, k, tq;
    int[][] d;
    int btcache;

    
    void getData( ){
        Scanner s = new Scanner(System.in);
        System.out.println( "enter no. of process");
        int pcount = s.nextInt();
        d = new int[pcount][2];

        temp = new int[pcount];
        System.out.println( "enter BT");
        for (int i = 0; i < pcount; i++) {
            d[i][0] = i;

            int m = s.nextInt();
            d[i][1] = m;

            commBT += m;
        }
        System.out.println( "enter TQ ");
        tq = s.nextInt();
        start();
        display( );
        
    }
    void start( ){
        for (int i = 0; i < d.length; i++) {
            int bt  = d[i][1];
            if( bt > 0){
                if( bt <= tq){
                    temp[i] = btcache+bt;
                    btcache = temp[i];
                    k += bt;
                    bt -= bt;
                     
                }
                else{
                    temp[i] = btcache+tq;
                    btcache = temp[i];
                    bt -= tq;
                    k += tq;
                }
                
                d[i][1] = bt;
               
                
            }
        }
        if( k!= commBT)
            start();
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SimpleRR r = new SimpleRR();
        r.getData();
    }

    private void display() {
        float val = 0;
        int c = 1;
        for (int i : temp) {
            System.out.println( "BT for process " + c + " is " + i );
            val += i;
            c++;
        }
        System.out.println( "avg BT = " + val/temp.length);
    }
}

The above code finds & prints turn-around time & average turn around time for the given data.

Output

Finding Nth Largest Term In Unsorted Array

Given a task of finding nth largest term in an unsorted array by obeying following rules ...

Rules

1. You cannot sort an array
2. You cannot use a single library function (No API calls are allowed)
3. A separate copy of array should not be created

This can be easily implemented using a stack where we will start filling the stack with the smallest element, such that at the end we will get largest term at the top.

Algorithm:

1. accept array elements
2. determine the minimum element from the array
3. insert it into the stack
4. repeat step 2 & 3 until stack contains all elements of array
5. accept nth position from the user, say x
6. return the element which is stored at the x position
7. display the result
8. stop

Psuedo code for finding minimum element in an array

imin <-- 0;

        for ( i <-- 0; i < arr.length; i++) {

            imin <-- i;

            for (j <-- 0; j < arr.length; j++) {

                if( a[j] < a[imin] ){

                    imin <-- j;

                }

            }

        }

where " imin " stores index of the minimum element.

Code

package Kthlargestterm;

import java.util.Scanner;

 //@author Naved Momin(navedmomin10@gmail.com)
 
public class KthLargestTerm {

    static int[] a;
    static Scanner s = new Scanner(System.in);
    static int counter = 0;
    static StackUsingLL stack = new StackUsingLL();
    
    public KthLargestTerm(int size) {
        a = new int[size];
    }
    
    int getMin( ){
        int imin = 0;
        for (int i = 0; i < a.length; i++) {
            imin = i;
            for (int j = 0; j < a.length; j++) {
                if( a[j] < a[imin] ){
                    imin = j;
                }
            }
        }
        int k = a[imin];
        a[imin] = Integer.MAX_VALUE;
        return k;
    }
    
     
     static void getData( ){
        System.out.println( "enter size "); 
        int n = s.nextInt();
        KthLargestTerm kth = new KthLargestTerm(n);
        System.out.println( "enter data ");
        for (int i = 0; i < n; i++) {
            a[i] = s.nextInt();
        }
        
        int min = kth.getMin();
         int c = 0;
        while ( min != Integer.MAX_VALUE && c < n ) {             
            if(!stack.contains(min))
                stack.insert(min); 
            
            min = kth.getMin();
            c++;
         }
        
        System.out.println( "enter nTh position to view nth largest term ");
        int m = s.nextInt();
         while (m != -1) {     
             if( m >= 0 ) {
                    int item = stack.getItem(m);
                    String str =  (m == 1) ? "st" 
                            : (m==2) ? "nd" 
                            : (m == 3 ) ? "rd"
                            : "th";
                    
                    System.out.println( m + str +  " largest term is " + item );
                }
             System.out.println( "press -1 to exit or press any key to continue...");
             m = s.nextInt();
             if( m != -1 ){
                System.out.println( "enter nTh position to view nth largest term ");
                m = s.nextInt();
                
             }
         }
        
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        getData();
    
    }
}   




class Node{
    int data;
    Node next;
}

public class StackUsingLL {
 
    Node top ;
    static int insertAccount = 1;
    
    public boolean isempty( ){
       if( top == null ){
           return true;
       }else
           return false;
    }
    
    public void insert( int x ){
        Node newrec  = new Node();
        newrec.data = x;
        newrec.next = null;
        
        if( top == null ){
            top = newrec;
        }else{
        newrec.next = top;
        top = newrec;
        }

      insertAccount++;
    }
    
    public int delete( ){
        if( isempty() ){
            System.out.println( "stack empty" );
        return -1;
        }
        else{
            int x = top.data;
            top = top.next;
            return x;
        }
    }
    
    public boolean hasNext( ){
        
        if( top != null ){
            return true;
        }
        else{
            return false;
        }
    }
    
    public boolean contains( int min ){
        boolean val = false;
        Node p = top;
        while ( p != null ) {            
            if( stackTop( ) == min ){
                val = true;
                break;
            }
            else
                val = false;
            p = p.next;
        }
        return val;
    }
    
   public int getItem( int index ){
        if( index <= insertAccount ){
            int i = 1;
            int d = -1;
            Node p = top;
            while (p != null) {            
                if( index == i ){
                    d = p.data;
                    break;
                }
                i++;
                p = p.next;
            }
            return d;
        }else{
            System.err.println( "index was out of range ...");
            return -1;
        }
    }
    
    public int stackTop(){
        return top.data;
    }
    
    public void display( ){
        if( isempty() )
            System.out.println( "stack empty");
        else{
            Node p = top;
            while (p != null) {
                System.out.println( p.data + " ");
                p = p.next;
            }
        }
    }
    
}

Output

In case you want *.jar file then download it from here

Correct Implementation of Insertion Sort

Given a task of implementing insertion sort, many people end up with following code 

    
void insertionSort(int a[]){
 for (int i = 0; i < a.length; i++) {
                
                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }
                    
                }
 }
}

Although the code works as expected & sorts the given data in O(n^2) time, but this is the wrong implementation of insertion sort.

Do You Know Why ?

The reason is best case time complexity of insertion sort is O(n) but this code has O(n^2), in short no matter what sequence of data you through at this code it will take O(n^2) time i.e best, avg. & worst case time complexity of this code is O(n^2).

Note: If you have clear your "Analysis of Algorithms & Design" paper you will understand what is written above.

If you have understand the above statements than you can fix the wrong implementation on your own, the above implementation can be corrected by just adding one statement which i left it for you as an exercise.

In case you are in hurry you can adopt My way to write insertion sort

Correct Implementation 

    
 int[] insertionSort(int [] a ){
        for (int j = 1; j < a.length; j++) {
            int i = j-1;
            while ( ( i >= 0 ) && a[i] > a[i+1] ) {                
                int k = a[i];
                a[i] = a[i+1];
                a[i+1] = k;
                i -= 1;
            }
        }
        return a;
    }

The best case time complexity(i.e when array elements are already in ascending order) of this code is O(n) & worst case time complexity is O(n^2), which proves that this code is correct implementation of Insertion Sort.

Swapping Using 2 Variables

Some of mine friends asked me a question, the Question was

Agreed that we can swap two numbers using some math, but how can we swap two chars & string without using 3rd variable ?

This blog post will answer the question, the method i have used is preety simple & straight forward
We will do following swapping

• Number Swapping
• Chars Swapping 
• Strings Swapping

To begin with lets quickly see the codes

• Number Swapping

 void swappingNumbers( int a, int b ){

        System.out.println( "input value  a = " + a + "  b = " + b );
        a = a+b;
        b = a-b;
        a = a-b;
        System.out.println( "swapped values a = " + a + " " + " b = " + b );
    }

The above code swaps two ( signed & unsigned ) numbers without using any 3rd variable

• Chars Swapping 

 void swappingChars(char a, char b ){
        System.out.println( "input value  a = " + a + "  b = " + b );
        int p = (int)a ,q = (int)b;
        p =  ( ( (int) p ) + ((int)q) ) ;
        q = ( ( (int) p ) - ((int)q) ) ;
        p = ( ( (int) p ) - ((int)q) ) ;
        System.out.println( "swapped values p = " +  ( (char)p) + " q = " + ((char)q) );
    }

The above code swaps 2 chars without using 3rd variable. Here using two variable i.e p & q we have swap the chars

• String Swapping

 
void swappingStrings(String str1, String str2){
        System.out.println( "input value  str1 = " + str1 + "  str2  = " + str2 );
        str2 = str1 + " " + str2;
        String[] split = str2.split(" ");
        str1 = split[1];
        str2 = split[0];
        System.out.println( "swapped values = str1 = " + str1 + " str2 = " + str2);
    }

The above code swaps 2 Strings without using 3rd variable.

Output

Hope this helps.

Java Matrix Multiplication (JMM)

Often in many areas of programming people require a tool which can simplify there n*n matrix multiplication problem in reasonable amount of time.

This can usually be done with 3 tight for loop and special care for handling dimension errors(which i assumes most of you knows) to do this i have a designed a special class and added it to my Utilities framework 1.1.2

Lets quickly take 1 example for 2*2 matrix multiplication using Utilities-1.1.2

  

class MatrixMultiplication
{
public static void main(String[] str) throws DimensionError{
        double[][] a = { {1.2,2.25}, {25.0,28.2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
    }
}
}

Output

So, now you know how simple is matrix multiplication.

Dimension Errors

A special care has been taken to indicate that matrix multiplication is not possible and this is indicated using DimensionError Exception

consider the following example

import math.DimensionError;
import math.Math;
public class MatrixMultiplication {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] str) {
        double[][] a = { {1.2,2.25,2}, {25.0,28.2,2}, {25.2, 14.25,2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
 try{
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
 }catch(DimensionError ex){
  System.out.println(ex.getErrorMessage());
 }
    }
}

Output

Speed

Worst case time complexity is O(n^3)


Download