Source
BAN USER1. Firstly reverse the array
eg. arr = {1,2,3}
reversed array = {3,2,1}
2. add 1 to first element of reversed array and propagate carry accordingly
3. reverse the array to get actual array
eg. {9,9,9}
reversed array : {9,9,9}
adding 1 to first element
array after adding 1 : {0,0,0,1}
resultant array : {1,0,0,0}
O(n) complexity
Note: this can be done when there is sufficient space at the end of array.
1. Split the path by '\' , put the splits into an array
eg. input: \a\b\..\foo.txt
Array = {"a" ,"b", "..", "foo.txt" }
2. start from last index of array , count number of instances of string == ".." and remove all the strings from indexes from last-i to last-i-count
3. generate path from array
String Normalize( String s ){
String[] arr = s.split("\");
int count = 0 ;
for( int i = arr.length-1; i >= 0 ; i-- ){
if( arr[i] == ".." )
count++;
else if(count >0){
arr[i] = "";
count--;
}
}
StringBuffer sb = new StringBuffer();
char c = '';
for( int i = 0 ; i < arr.length; i++ ){
if( arr[i] != "" ){
sb.append(c+arr[i]);
c = '\';
}
}
return sb.toString();
}
1. Use Hashmap to get all the unique counts of strings .
2. Hash function :
I) assign prime numbers to all the alphabets starting from 3
a = 3 , b = 5, c = 7, d = 11 .... till z
II) for a given string generate the sum from above sequence
eg. for abc = 3+5+7 = 15
for bca = 5+7+3 = 15
III) for hash function string sum(generated above) is the output.
1. do sub array can be of length = 1?
2. sub arrays are to be selected randomly or we can have any particular sequence?
if we can have sub array of length = 1 , then this problem can be easily modified to get total number of swaps taking place sorting algo like bubble sort.
minimum swaps = nlogn for sub array length 1 .
this soln is based on too much of hypothesis!!
only 52 bits are needed
Idea is : int data type has 64 bits ie. can store 64 integers
say we get random sequence as : 1 , 15 , 20 , 30, 52 , 4
so int ans = 0
ans = ans | ( 1 << 1 )
ans = ans | ( 1 << 15 )
ans = ans | ( 1 << 20 )
ans = ans | ( 1 << 30 )
ans = ans | ( 1 << 52 )
ans = ans | ( 1 << 4 )
Now, ans carries now 6 random numbers information. Similarly 52 random numbers can be stored in 52 LSB of integer .
so only sending 52 LSB of ans is enough to get information regarding the sequence
O(nlogn) solution
class xyz{
public static void main(String args[]){
point arr[] = { new point( 4,8 ),
new point( 3, 5 ),
new point( -1,2 ),
new point(9,12),
new point(13,15) };
Arrays.sort( arr );
Queue<point> q = new LinkedList<point>();
point p1 = arr[0];
for( int i = 1 ; i < arr.length ; i++ ){
point p2 = arr[i];
if( p1.y+1 >= p2.x )
p1.y = p2.y;
else{
q.add(p1);
p1 = p2;
}
}
q.add(p1);
for( point z : q ){
System.out.println( z.x + " " + z.y );
}
}
}
class point implements Comparable<point>{
int x ;
int y;
public point( int x, int y ){
this.x = x;
this.y = y;
}
@Override
public int compareTo( point p ) {
return this.x - p.x;
}
}
I think this program will work
As stated above for DBNZ X L10 "This instruction decrement X by one and checks X, if X is not zero than branches line 10"
Hence, The statement first decrements!!
Let x = 0,
NEGATE X, Y:
Step 1. CLEAR Y
Step 2. L1: DBNZ Y L2
Step 3. L2: DBNZ X L1
Step 1. Y = 0
Step 2. Y = -1 , X = 0
Step 3. Y = -1 , X = -1
Step 2. Y = -2, X = -1
Step 3. Y = -2, X = -2
....
Step 2. Y = -65536, X = -65535
Step 3. Y = -65536, X = -65536
Step 2. Y = 65535, X = -65536
Step 3. Y = 65535, X = 65535
....
Step 2. Y = 1, X = 2
Step 3. Y = 1, X = 1
Step 2. Y = 0, X = 1
Step 3. Y = 0, X = 0
therefore Y = -X = 0 which is correct.
Now let x = -1,
NEGATE X, Y:
Step 1. CLEAR Y
Step 2. L1: DBNZ Y L2
Step 3. L2: DBNZ X L1
Step 1. Y = 0
Step 2. Y = -1 , X = -1
Step 3. Y = -1 , X = -2
Step 2. Y = -2 , X = -2
Step 3. Y = -2 , X = -3
....
Step 2. Y = -65535 , X = -65535
Step 3. Y = -65535 , X = -65536
Step 2. Y = -65536 , X = -65536
Step 3. Y = -65536 , X = 65535
Step 2. Y = 65535 , X = 65535
Step 3. Y = 65535 , X = 65534
...
Step 2. Y = 1 , X = 1
Step 3. Y = 1 , X = 0
For this one also Y = -X => Y = -(-1) => Y = 1
@pavelkushtia :
Here i'm copying elements from Array {9,1,3,7,8,5,2 } into an hashtable
then while iterating over linked list, i check whether that value is in hashtable , if exists then printing the value , else simply escaping the node in linked list.
hence the output is : 1 2 3 5 7 8 9
I'm only printing the above output on screen , one can easily count these chunks!!!
Also i've mentioned an approach in which i'm modifying the structure of linked list.
as array contains pointers to the nodes , so on one iteration over that array i'm making the pointed node's previous pointer as null
and afterwards, iterating over linked list with the help of next pointer we'll print all the nodes which are having previous pointer as null and escaping those whose previous pointer is not null.
do revert if anything is not clear!!!
This is my solution , but don't know about its time complexity . Someone please suggest.
int total( int n ){
if ( n <= 0 )
return 0;
if( n == 0 || n == 1 )
return n;
int x = sqrt(n);
int minv = INT_MAX;
for( int i = x ; i>= 1; i--)
{
minv = min( minv, 1 + total(n-i*i) );
}
return minv;
}
thanks Koosha ,
As the array list is already sorted, we can use binary search ( O(logn) ) for finding the index of element to be removed.
once the index of element is known then deletion is O(1) .
Similarly Binary search can be used for finding number of elements after a certain element .
Hence the over all complexity would be O(nlogn) only!
Both the methods are O(n)
Method 1. by using extra space ( HashMap )
Method 2. by modifying linked list structure ie by removing the prev pointers of nodes
class DDL_Pointer{
private static void resultType_DLL( node arr[] , node head ){
node curr = head;
for( int i = 0 ; i < arr.length; i++ ){
node n = arr[i];
if( n.next != null )
n.next.prev = null;
}
while( curr.next != null ){
if( curr.next.prev == null )
System.out.println( curr.val );
else
System.out.println();
curr = curr.next;
}
}
private static void resultType_HashMap( node arr[] , node head ){
HashMap hm = new HashMap();
for( int i = 0 ; i < arr.length ; i++ ){
node n = arr[i];
hm.put( n.val, 1);
}
node curr = head;
while(curr.next != null){
if( hm.containsKey(curr.val) )
System.out.println( curr.val );
else
System.out.println();
curr = curr.next;
}
}
public static void main( String args[] ){
node Node1 = new node( 1, null, null);
node Node2 = new node( 2, Node1 ,null);
node Node3 = new node( 3, Node2 ,null);
node Node4 = new node( 4, Node3 ,null);
node Node5 = new node( 5, Node4 ,null);
node Node6 = new node( 6, Node5 ,null);
node Node7 = new node( 7, Node6 ,null);
node Node8 = new node( 8, Node7 ,null);
node Node9 = new node( 9, Node8 ,null);
Node1.next = Node2;
Node2.next = Node3;
Node3.next = Node4;
Node4.next = Node5;
Node5.next = Node6;
Node6.next = Node7;
Node7.next = Node8;
Node8.next = Node9;
node head = Node1;
node arr[] = { Node9,Node1,Node3,Node7,Node8,Node5,Node2};
// using hashmap
resultType_HashMap( arr, head );
// modifying structure of linked list
resultType_DLL( arr, head );
}
}
class node{
int val;
node next;
node prev;
public node( int val, node prev, node next ){
this.val = val;
this.next = next;
this.prev = prev;
}
}
class squareRepresentation{
public static void main( String a[] ){
Scanner in;
in = new Scanner( System.in );
int n = in.nextInt();
int x = getSquares( n );
System.out.println( "total = "+ x );
}
public static int getSquares( int n ){
if( n == 0 )return 0 ;
int x = (int)Math.sqrt( (double)n );
System.out.print( x+"\t" );
int total = 0;
return 1+getSquares( n- x*x );
}
}
modified merge sort is nice solution.
I do have 1 more algo which is having complexity : O(nlogn).
say array is
A [] = { 33 , 25 , 26 , 58 , 41 , 59}
step 1 : create ArrayList of size = A.length
step 2 : sort ArrayList in ascending order O(nlog(n))
ArrayList => { 25 , 26 , 33, 41, 58 , 59 }
step 3 : choose 1st element of A[] ie 33
=> qaz(33) => total elements in ArrayList after 33
=> qaz(33) = 3
remove element 33 from ArrayList
now ArrayList = {25 , 26 , 41, 58 , 59 }
step 4: choose next element from A[] ie 25
=> qaz(25) = total elements in ArrayList after 25
=> qaz(25) = 4
remove element 25 from ArrayList
now ArrayList = {26 , 41, 58 , 59 }
step 5: choose next element from A[] ie 26
=> qaz(26) = total elements in ArrayList after 26
=> qaz(26) = 3
remove element 26 from ArrayList
now ArrayList = {41, 58 , 59 }
step 6: choose next element from A[] ie 58
=> qaz(58) = total elements in ArrayList after 58
=> qaz(58) = 1
remove element 58 from ArrayList
now ArrayList = {41 , 59 }
step 7: choose next element from A[] ie 41
=> qaz(41) = total elements in ArrayList after 41
=> qaz(41) = 1
remove element 41 from ArrayList
now ArrayList = { 59 }
last step: choose next element from A[] ie 59
=> qaz(59) = total elements in ArrayList after 59
=> qaz(59) = 0
remove element 59 from ArrayList
now ArrayList = {}
@root545 - here i'm calculating total number of digits between 0 to n numbers .
say digit 1 comes 1 time between 0-9 hence f(10) = 1 , and between 0-99 it came for about 20 times hence f(100) = 20.
now for total occurrences given , let say k = 32, we'll calculate the maximum digit till when we'll get k = 32 ie. 0 to max_digits contains exactly 32 occurrences of 1.
Now for minimum digit for sure it will lie in 0-9 range only, for d = 1 minim_digit = 1.
Accordingly , for k = 0 , we'll calculate where the first occurrence of digit starts, so range would be min_digit = 0 , max_digit = d-1
For digit = 3 , let no of occurences k = 32
Precalculated
1. number of occurences of 3 from 0-9, f(10) = 1
2. number of occurences of 3 from 0-99, f(100) = f(10) * 10 + 10 = 20
algo :
if( k > 0 ) {
1. k++
2. H = k/f(100) = 33/20 = 1
3. k = k - H*f(100) = k - 1*20 = 33 - 20 = 13
4. last_number = 0;
for( i = 0 ; i <= 9 ; i++) {
if(digit == i)
if( k-10 < 0){
break;
}
else
k = k - 10;
}
if( k > 0 ){
k--;
}
else
break;
}
last_number = H*100 + 10 * (i+1) + d;
5. from = d ; to = last_number-1
}
else{
from = 0 ; to = d -1;
}
nice solution by @xiejilin@limijiaoyin.com
I have 1 more idea for the problem :
1. O(n) - add all numbers ; let total sum = Sum
2. while loop over all elements, subtract current element (a[i]) from sum
for( i = 0 ; i < n ; i++){
a[i] = Sum +(~a[i] +1); /* (~a[i] +1) is a[i]'s 2's complement */
}
hence over all complexity : O(n)
O(n^2) algorithm:
Firstly sort array with O(nlogn)
for( k=0; k<n ;k++){
i = 0; j = n-1;
while( i<n && j>=0 ){
if( a[i] + a[j] + a[k] <= d ){
system.out.println (a[i] +" "+ a[j] + " "+ a[k]);
i++;j--;
}
else if( a[i] + a[j] + a[k] > d ){
j--
}
else
i++;
}
}
also for handling duplicates we can maintain hash table.
Please do comment if you find anything wrong!!
O(n) solution
inorder traversal of tree:
void traversal( node treenode , node head ){
static node prev = null;
if( treenode == null )
return;
traversal( treenode.left , head );
if( prev == null )
head = treenode;
else{
treenode.left = prev;
prev.right = treenode;
}
prev = treenode;
traversal( treenode.right , head );
}
I'll use Dictionary in a Hash table format where Keys are in alphabetically sorted order , and values are all possible dictionary strings that can be made from key:
example :
[e] => {}
[g] => {}
[eg] => {egg , /*strings containing only e and g alphabets in dictionary order*/ }
[0] => {}
[go] => {go}
[ego] => {ego}
1. now , sort the string s /* = "ogeg */ and remove duplicates , hence s' = ego , and character counts as g = 2, e = 1, o = 1
2. traverse over all permutations of strings
string permutations[] ;
for( i = 1 ; i < 2^(length(s')) ; i++ ){
string temp = "";
j = i;
index = 0;
while( j != 0){
if( j >> 1 ){
temp = s'[index] + "" + temp;
}
index++;
}
permutations[i] = temp;
}
3. for all permutations find all possible strings from dictionary , taking all permutations as dictionary key
we have variables : g = 2, e = 1, o = 1
- for all the permutations get hashtable[key] values
- loop through values , if isvalid() then print it.
isvalid(){
/* if character count in value = character count in permutation string */
}
class Solution {
public:
int maxProfit(vector<int> &prices) {
int f[3] = {0};
int g[3] = {0};
int n = prices.size() - 1;
for (int i = 0; i < n; ++i) {
int diff = prices[i+1] - prices[i];
int m = min(i+1, 2);
for (int j = m; j >= 1; --j) {
f[j] = max(f[j], g[j-1]) + diff;
g[j] = max(g[j], f[j]);
}
}
return max(g[1], g[2]);
}
};
say matrix(n*m) is :
1 1 1 1 1 1
1 1 1 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 1 1
1 1 1 1 1 1
Algo :
1. create a temporary matrix by calculating the number of 1's a 0 is surrounded with:
T(n*m)
0 0 0 0 0 0
0 0 0 2 3 0
0 2 2 2 3 0
0 2 2 2 4 0
0 3 3 4 0 0
0 0 0 0 0 0
code:
Boolean hasIsland( int matrix[][]){
int walls = 0;
int temp[][] = {0};
for(i = 0 ; i <n ; i++)
for(j = 0 ; j < m ; j++ )
if(matrix[i][j] == 0){
fill(matrix, i , j , temp, n , m );
if( temp[i][j] > walls )
walls = temp[i][j];
}
if(walls == 4){
system.out.print("has island");
return true;
}
}
void fill( int matrix[][], int i , int j , int temp[][], int n , int m ){
temp[i][j] = 0;
if( i == 0 || j == 0 || i == n-1 || j == m-1 ) return;
if( matrix[i][j-1] == 1 || temp[i][j-1] > 0 )
temp[i][j] += 1;
if( matrix[i-1][j] == 1 || temp[i-1][j] > 0 )
temp[i][j] += 1;
if( matrix[i+][j] == 1 )
temp[i][j] += 1;
if( matrix[i][j+1] == 1 )
temp[i][j] += 1;
return;
}
According to you , for { 100, 180, 260, 310, 295, 535, 695 } and k = 1 , possible subsequence would be : {100, 180, 260, 310} , {295, 535, 695} , profits are = 210, 400 , out of this ans = 400
but maximum profit would be when buy at day 1 and sell at last ie. 695-100 = 595
say pattern is abbab [2 a's and 3 b's] and string = redblueblueredblue [18 chars]
Let number of chars in 'a' = x and 'b' = y
2x + 3y = 18
find all possibilities of x and y,
here it came : x = 3 and y = 4
Loop over all possibilities of x and y
Check in one more loop if string is following that pattern or not
Check this...
#include<stdio.h>
struct Element{
int val;
struct Element *next;
};
struct BaseElements{
struct Element *nodes;
struct Element *head;
};
struct BaseElements *Base[10] ;
struct Element* InsertNewNode( int v ){
struct Element *node = (struct Element*)malloc(sizeof(struct Element));
node->val = v;
node->next = NULL;
return node;
}
void MakeList( int val ){
int index = ( val /10 == 0 ? val%10 : val/10);
struct Element *newnode = InsertNewNode( val );
if( !Base[index] ){
Base[index] = malloc( sizeof(struct BaseElements) );
Base[index]->nodes = newnode ;
}
else{
Base[index]->head->next = newnode;
}
Base[index]->head = newnode ;
//printf("%d , %d , %d\n",index , val,Base[index]->head->val);
return;
}
void main(){
int i = 0 , j = 0 , k = 0;
for( i = 2 ; i < 40 ; i++){
k = 0;
for( j = 2 ; j *j <= i ; j++){
if( i % j == 0){
k = 1;
break;
}
}
if( k == 0){
//printf("%d , %d\n",i,k);
MakeList(i);
}
}
for( i=0 ; i<10 ; i++){
if( !Base[i]){
continue;
}
else{
while( Base[i]->nodes != NULL){
printf("%d\n",Base[i]->nodes->val);
Base[i]->nodes = Base[i]->nodes->next;
}
}
}
return;
}
O(n) algo!!
- Source September 26, 2015