#interviewstreet

[antonio081014]

InterviewStreet: Equation.

Problem Links:

InterviewStreet:EQUATION.

Problem:

EQUATIONS (45 points)

Find the no of positive integral solutions for the equations (1/x) + (1/y) = 1/N! (read 1 by n factorial) Print a single integer which is the no of positive integral solutions modulo 1000007. Input: N Output: Number of positive integral solutions for (x,y) modulo 1000007 Constraints: 1 <= N <= 10^6 Sample Input00: 1 Sample Output00: 1

Sample Input01:

32327

Sample Output 01:

656502

Sample Input02:

40921

Sample Output 02:

686720

Solution:

No of solutions for the equation XY=N! is (e1+1)(e2+1)………..(en+1) where e1,e2…en are multiplicities of Prime Numbers below N.

For Ex: XY=4! No of primes below 4= {2,3} 4!= 24= 23*31 where 3 and 1 are prime multiplicities of 24. so applying the formula (3+1)*(1+1)=8 (no of factors of 24={1,2,3,4,6,8,12,24}.

Now the equation 1⁄x+1⁄y= N! can be transformed into (x-N!)(y-N!)=N!2 Hence No. of solutions of the above equation is (2e1+1)(2e2+1)………..(2en+1)

Hence to solve the problem: 1) First find out the primes less than N 2) Find the prime multiplicities 3) Apply the formula.

For step two, it's not easy to have a fast solution. Compare with two methods I provided here, I still don't know how the second one could work, while the first one is definitely too slow. Updated: This LINK greatly explains why the second method is also right.

Source Code:

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Solution { private static final int MOD = 1000007; private boolean[] isPrime; private int[] multiplier; private List<Integer> prime; public static void main(String[] args) throws Exception { Solution main = new Solution(); main.run(); System.exit(0); } public void run() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); isPrime = new boolean[N + 1]; multiplier = new int[N + 1]; prime = new ArrayList<Integer>(); generatePrime(N); // for (int i = 0; i <= N; i++) // System.out.println("" + i + ", " + isPrime[i]); generateMultiplier(N); long sum = 1L; for (int i = 1; i <= N; i++) if (multiplier[i] != 0) { sum *= (long) (2 * multiplier[i] + 1) % MOD; sum %= MOD; } System.out.println(sum); } public void generatePrime(int N) { for (int i = 2; i <= N; i++) if (isPrime[i] == false) { prime.add(i); for (int j = 2; j * i <= N; j++) isPrime[i * j] = true; } } public void generateMultiplier(int N) { // int left = 1; // for (int i = 1; i <= N; i++) { // left *= i; // for (int j : prime) { // while (left % j == 0) { // multiplier[j]++; // left /= j; // } // if (left < j) // It helps prune and save the time. // break; // } // } for (int j : prime) { int cpy = N; int e = 0; while (cpy != 0) { e += cpy / j; cpy /= j; } multiplier[j] = e; } } public boolean check(int x, int N) { return true; } }

[antonio081014]

InterviewStreet: Flowers

Problem Links:

Link;

Problem:

You and your K-1 friends want to buy N flowers. Flower number i has host ci. Unfortunately the seller does not like a customer to buy a lot of flowers, so he tries to change the price of flowers for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*cidollars to buy flower number i. You and your K-1 firends want to buy all N flowers in such a way that you spend the as few money as possible. Input:

The first line of input contains two integers N and K. next line contains N positive integers c1,c2,...,cN respectively. Output:

Print the minimum amount of money you (and your friends) have to pay in order to buy all n flowers.

Sample onput :

3 3 2 5 6

Sample output :

13

Explanation : In the example each of you and your friends should buy one flower. in this case you have to pay 13 dollars.

Constraint :

1 <= N, K  <= 100 Each ci is not more than 1000,000

Solution:

Here, 1st, sort the array, then use greedy to collect flowers from the largest cost, since the later you collect the high price flower, that will cost you more.

Source Code:

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; /** * */ /** * @author antonio081014 * @time Oct 6, 2012, 11:57:39 PM */ public class Solution { public static void main(String[] args) throws Exception { Solution main = new Solution(); main.run(); System.exit(0); } public void run() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split("\\s"); int N = Integer.parseInt(str[0]); int K = Integer.parseInt(str[1]); str = br.readLine().split("\\s"); int[] cost = new int[N]; for (int i = 0; i < N; i++) { cost[i] = Integer.parseInt(str[i]); } Arrays.sort(cost); int total = 0; int _K, i; for (i = N - 1, _K = K; i >= 0 && _K > 0; i--, _K--) { total += cost[i]; } int index = 0; int round = 1; for (; i >= 0; i--) { total += cost[i] * (round + 1); index++; if (index >= K) { round++; index = 0; } } System.out.println(total); } }

[antonio081014]

InterviewStreet: Pairs

Problem:

For the problem statement, follow the link. Statement:

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9] Input Format: 1st line contains N & K (integers). 2nd line contains N numbers of the set. All the N numbers are assured to be distinct. Output Format: One integer saying the no of pairs of numbers that have a diff K. Sample Input #00: 5 2 1 5 3 4 2 Sample Output #00:3

 Sample Input #01:

10 1

363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 

 Sample Output #01:

0 

Note: Java/C# code should be in a class named "Solution"

Read input from STDIN and write output to STDOUT. 

Solution:

From the problem statement, we could have N, the number of array, could be as large as 10^5, so our algorithm's up limit is O(nlogn), since usually the time cost scale could be no bigger than 10^7; After viewing the problem, we know all the numbers are distinct, so we could sort them first, as everybody know, quick-sort or merge-sort could take O(nlogn) time. So, after sorting, we have an non-decreasing array of numbers, and we need to find the pair which difference is K. Here, we could go through every element, then for each element, we can use binary search to find the other number. So, this will take O(N) to go through array, and O(logN) for using binary search, Thus, F(N) = f*g = O(N) * O(logN) = O(NlogN). But some minor bugs could be easily made here, 1st, there could be two distinct number to pair with ith number, and both of pairs' difference could be K. So, we need to search in both direction. 2nd, in binary search, take great care of the boundary case, don't make it infinite, and don't make any blind spot in that search. Code is as follow:

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; /** * */ /** * @author antonio081014 * @time: Oct 6, 2012, 2:32:58 PM */ public class Solution { private int K; /** * @param args */ public static void main(String[] args) throws Exception { Solution main = new Solution(); main.run(); System.exit(0); } public void run() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split("\\s"); int N = Integer.parseInt(str[0]); K = Integer.parseInt(str[1]); int[] array = new int[N]; str = br.readLine().split("\\s"); for (int i = 0; i < N; i++) array[i] = Integer.parseInt(str[i]); Arrays.sort(array); int count = 0; for (int i = 0; i < N; i++) { count += binaryLeft(0, i - 1, array, i); count += binaryRight(i + 1, N - 1, array, i); } System.out.println(count / 2); } private int binaryLeft(int low, int high, int[] array, int index) { while (low <= high) { int mid = (low + high) / 2; if (array[mid] + K == array[index]) { // System.out.println("" + array[index] + " " + array[mid]); return 1; } else if (array[mid] + K < array[index]) low = mid + 1; else high = mid - 1; } return 0; } private int binaryRight(int low, int high, int[] array, int index) { while (low <= high) { int mid = (low + high) / 2; if (array[mid] - K == array[index]) { // System.out.println("" + array[index] + " " + array[mid]); return 1; } else if (array[mid] - K < array[index]) low = mid + 1; else high = mid - 1; } return 0; } }

[antonio081014]

Insertion Sort @ InterviewStreet

Problem Links:

Interviewstreet,

Problem:

Insertion Sort (25 Points)

Insertion Sort is a classical sorting technique. One variant of insertion sort works as follows when sorting an array a[1..N] in non-descending order:

for i  = 2 to N    j = i   while j > 1 and a[j] < a[j - 1]        swap a[j] and a[j - 1]         j = j-1 

The pseudocode is simple to follow. In the ith step, element a[i] is inserted in the sorted sequence a[1..i - 1]. This is done by moving a[i] backward by swapping it with the previous element until it ends up in it's right position.

As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.

Input: The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1],a[2]...,a[N].

Output: Output T lines, containing the required answer for each test case.

Constraints:

1 <= T <= 5 1 <= N <= 100000 1 <= a[i] <= 1000000

Sample Input: 2 5 1 1 1 2 2 5 2 1 3 1 2

Sample Output: 0 4 

Source Code:

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; /**  * This problem actually ask the coder to count the number of inversions.  * The updated merge-sort could count this number perfectly.  */ /**  * @author antonio081014  * @since Jan 8, 2012, 4:41:26 PM  */ public class Solution {     public static void main(String[] args) throws Exception {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         // BufferedReader br = new BufferedReader(new InputStreamReader(         // new DataInputStream(new FileInputStream("input.txt"))));         // BufferedWriter bw = new BufferedWriter(new FileWriter(new File(         // "output.txt")));         int T = Integer.parseInt(br.readLine());         for (int t = 0; t < T; t++) {             int N = Integer.parseInt(br.readLine());             int[] nums = new int[N];             String[] strs = br.readLine().split(" ");             for (int j = 0; j < N; j++)                 nums[j] = Integer.parseInt(strs[j]);             System.out.println(Long.toString(sort_and_count(nums, 0, N - 1)));             // bw.write(Long.toString(sort_and_count(nums, 0, N - 1)) + "\n");         }         // br.close();         // bw.close();     }     public static long sort_and_count(int[] a, int x1, int x2) {         if (x2 <= x1)             return 0L;         if (x2 == x1 + 1) {             if (a[x1] > a[x2]) {                 a[x1] ^= a[x2];                 a[x2] ^= a[x1];                 a[x1] ^= a[x2];                 return 1L;             }             return 0L;         }         int mid = (x2 + x1) / 2;         long count = 0L;         count += sort_and_count(a, x1, mid);         count += sort_and_count(a, mid + 1, x2);         count += merge_and_count(a, x1, mid, mid + 1, x2);         return count;     }     public static long merge_and_count(int[] a, int x1, int x2, int y1, int y2) {         long count = 0L;         for (int i = x1, j = y1; i <= x2 && j <= y2;) {             if (a[i] > a[j]) {                 count += (long) (x2 - i + 1);                 j++;             }             else                 i++;         }         Arrays.sort(a, x1, y2 + 1);         return count;     }     public static long insertSort(int[] a) {         long count = 0;         for (int i = 1; i < a.length; i++) {             int j = i;             while (j >= 1 && a[j] < a[j - 1]) {                 a[j] ^= a[j - 1];                 a[j - 1] ^= a[j];                 a[j] ^= a[j - 1];                 count++;                 j--;             }         }         return count;     } }

[antonio081014]

2's complement

Problem Links:

InterviewStreet,

Problem:

2's complement (10 Points)

One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B inclusive in 2's complement representation using 32 bits. How many 1's will you write down in all ?

Input: The first line contains the number of test cases T (<1000). Each of the next T lines contains two integers A and B.

Output: Output T lines, one corresponding to each test case.

Constraints: -2^31 <= A <= B <= 2^31 - 1

Sample Input: 3 -2 0 -3 4 -1 4

Sample Output: 63 99 37

Explanation: For the first case, -2 contains 31 1's followed by a 0, -1 contains 32 1's and 0 contains 0 1's. Thus the total is 63. For the second case, the answer is 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

The big part of this problem is to deal with the big number, the programmer needs to convert the integer to long very first, then do the other operations.

Source Code:

import java.io.BufferedReader; import java.io.InputStreamReader; /**  * Problem: 2's complement, from interviewStreet.  *  * The solution is from the link, which reached a log(n) time complexity on this  * one.  */ /**  * @author antonio081014  * @since Jan 5, 2012, 1:41:35 PM  */ public class Solution {     public static void main(String[] args) throws Exception {         // BufferedReader br = new BufferedReader(new InputStreamReader(         // new DataInputStream(new FileInputStream(args[0]))));         // BufferedWriter bw = new BufferedWriter(new FileWriter(args[1]));         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int T = Integer.parseInt(br.readLine());         for (int t = 1; t <= T; t++) {             String[] str = br.readLine().split(" ");             int a = Integer.parseInt(str[0]);             int b = Integer.parseInt(str[1]);             System.out.println(solve(a, b));             // bw.write(Long.toString(solve(a, b)) + "\n");         }         br.close();         // bw.close();     }     /**      * http://stackoverflow.com/questions/7942732/number-of-1s-in-the-twos-      * complement-binary-representations-of-integers-in-a-ran      *       * The explanation greatly explans everything.      *      * */     public static long solve(int a, int b) {         if (a >= 0) {             long ret = counter(b);             if (a > 0)                 ret -= counter(a - 1);             return ret;         }         long ret = ((long) 32 * (-(long) a)) - counter(-a - 1);         if (b > 0)             ret += counter(b);         else if (b < -1) {             b++;             ret -= ((long) 32 * (-(long) b)) - counter(-b - 1);         }         return ret;     }     /**      * Calculate the number of 1s from number 0 to number num;      *       * */     public static long counter(int num) {         if (num == 0)             return 0L;         if (num % 2 == 0)             return counter(num - 1) + ones(num);         return (((long) num + 1) / 2) + 2 * counter(num / 2);     }     /**      * Calculate the number of 1s in the number      */     public static long ones(int num) {         String str = Integer.toBinaryString(num);         long sum = 0L;         for (int i = 0; i < str.length(); i++)             if (str.charAt(i) == '1')                 sum++;         return sum;     } }

[suprheavn]

2013: THE PRESENT FUTURE

Oh hello blog that I've been regularly ignoring. It is currently the second day of the new year and I am writing this during the last moments I have in Nevada for a while. 

Fall semester of school ended with me being sick taking finals and generally being miserable. Luckily, the misery didn't last long as I had a nice Christmas with the fam and experienced snow in a way that made me realize I don't have proper snow experiencing attire.

Over the break I tried some Java problems on Interviewstreet and learned that interpreting the questions was maybe more of an issue than actually coding them. So I reviewed Python and JavaScript on Learnstreet and was introduced to Ruby finally. Ruby is kind of silly. I did enjoy placing the objects that were being acted on in the function definitions. Plus the default methods are sort of nice although they'd be better listed alphabetically. Does object.methods.sort() exist??

OH HOLY SHIT THAT IS A THING :: http://codepad.org/yRp6Mq5K

Plus I've been doing this MIT online C programming course which has been all sorts of interesting. I finally understand bit shifting better. It's been a pain to figure out how to make the CDT Eclipse download behave though. Almost each time I run build it wants me to give it a different toolchain. Super bizarre...

Also, a fellow student has been posting cool stuff on our class board such as Google Summer of Code that I'd be totally interested in doing. But regardless of whether they do it again this year I'm going to attempt to get involved in open source soon. I'm looking at you, Eclipse.