RiponCoder
BAN USERSolution in Java(N log N)
public class FindMissingElements {
private static void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
/* This function takes last element as pivot, places the pivot element at its
correct position in sorted array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right of pivot */
private static int partition (int arr[], int l, int h)
{
int x = arr[h]; // pivot
int i = (l - 1); // Index of smaller element
for (int j = l; j <= h- 1; j++)
{
// If current element is smaller than or equal to pivot
if (arr[j] <= x)
{
i++; // increment index of smaller element
swap(arr, i , j); // Swap current element with index
}
}
swap(arr, i+1, h);
return (i + 1);
}
/* arr[] --> Array to be sorted, l --> Starting index, h --> Ending index */
private static void quickSort(int arr[], int l, int h)
{
if (l < h)
{
int p = partition(arr, l, h); /* Partitioning index */
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
}
private static int findOneNumber(int[] a, int[] b) {
int x = 0;
int len = 0;
int i = 0;
if(a.length > b.length) {
len = b.length;
while(len > i) {
if(a[i] != b[i])
return a[i];
i++;
}
if(len == i) return a[len];
} else {
len = a.length;
while(len > i) {
if(a[i] != b[i])
return b[i];
i++;
}
if(len == i) return b[len];
}
return x;
}
private static int findOtherNumber(int[] a, int[] b, int oneNumber) {
int sumA = 0, sumB = 0, diff = 0;
for(int i = 0 ; i < a.length ; i++)
sumA += a[i];
for(int i = 0 ; i < b.length ; i++)
sumB += b[i];
diff = sumA - sumB;
if(diff > 0) {
return diff - oneNumber;
} else {
return -1 * diff - oneNumber;
}
}
public static void main(String[] args) {
int[] a = {1, 6, 8, 3, 16, 33, 192, 145, 25, 28, 29, 38, 73, 66, 71};
int[] b = {1, 6, 8, 3, 16, 19, 33, 192, 145, 25, 28, 29, 38, 44, 73, 66, 71};
int lenA = a.length;
int lenB = b.length;
quickSort(a, 0, lenA - 1);
quickSort(b, 0, lenB - 1);
int oneNumber = findOneNumber(a, b);
int otherNumber = findOtherNumber(a, b, oneNumber);
System.out.println(oneNumber + ", " + otherNumber);
}
}
If there are any error or improvement, please let me know.
- RiponCoder March 04, 2014What about if we use stack (LIFO).
import java.util.Stack;
public class WordsReversed {
private String reverse(String str) {
Stack<String> stack = new Stack<String>();
String temp = "";
while(true) {
if(str.indexOf(' ') > 0) {
temp = str.substring(0, str.indexOf(' '));
str = str.substring(temp.length()+1, str.length());
stack.push(temp.trim());
}
else {
stack.push(str.trim());
break;
}
}
str = "";
while(!stack.empty())
{
str = str + stack.pop() + " ";
}
return str;
}
public static void main(String[] args) {
WordsReversed wr = new WordsReversed();
String string = "I love programming";
System.out.println(wr.reverse(string));
}
}
LinkedList is fast for insertion and deletion except random selection. In this scenario I think HashTable may be appropriate.
- RiponCoder February 21, 2014if n = 8
x[1] = x[2] = 1;
while(n > 1){
int m = 9;
while(m > 1) {
if(n % m == 0) {
x[i++] = m;
n /= m;
}
m--;
}
}
x[0] = 8, x[1] = 1, x[2] = 1.
So, for 8 ans: x[2] x[1] x[0] = 118
If we divide the number n by 9 ... 2 until n > 1 then we will get the smallest number
If n = 100 then
n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = 10
now n = 10 then
n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = 2
now n = 2 then
n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = x
n / 4 = x
n / 3 = x
n / 2 = 1
2x5x5 = 100.
So, 255 is the smallest number.
If n = 12 then
n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = 2
now n = 2
n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = x
n / 4 = x
n / 3 = x
n / 2 = 1
so, 2 * 6 = 12. i.e. 1 x 2 x 6 = 12 that's why 126 is the smallest number
public class Smallest {
private static int[] min(int n) {
int[] x = new int[50];
int i = 0;
x[1] = x[2] = 1;
boolean isItNotDivisible = true;
while(n > 1){
isItNotDivisible = true;
int m = 9;
while(m > 1) {
if(n % m == 0) {
x[i++] = m;
n /= m;
isItNotDivisible = false;
break;
}
m--;
}
if(isItNotDivisible == true) {
x[0] = 0;
return x;
}
}
return x;
}
public static void main(String[] args) {
int[] x;
int n = 112;
x = min(n);
if(x[0] != 0 && x[3] == 0) {
System.out.print(x[2]);
System.out.print(x[1]);
System.out.print(x[0]);
}
}
}
I tried in this way:
Step 1: Node linkHead = new Node()
Step 2: Store first Node of Every Nth Nodes
Step 3: Reverse the next N nodes
Step 4: link the tail of reverse list to linkHead
Step 5: Continue Step 2 - Step 4 until the list is traversed.
Complexity: O(n)
I have added my solution. Appreciate any suggestion or improvement.
- RiponCoder May 14, 2014