radhika.nitk
BAN USERArray should be sorted
{
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void PrintArray(int* A, int* B, int arr_size)
{
printf("\n Picking Coins \n");
for(int i = 0; i <arr_size; i++)
{
printf("\n A[i] %d :: B[i] %d \n", A[i], B[i]);
}
return;
}
int SolveEquation(int* A, int* B, int total, int size, int arr_size, int coins )
{
static int min_coins = total;
if(size == 0)
{
if(total % A[size] == 0)
{
B[size] = total/A[size];
total = total - A[size]*B[size];
if(coins +B[size] < min_coins)
{
printf("\n current min coins %d min_coins %d \n", coins, min_coins);
min_coins = coins;
PrintArray(A, B, arr_size);
}
}
return min_coins;
}
int max = total/A[size];
for(int j = max; j >= 0; j--)
{
if(coins+j > min_coins)
break;
B[size] = j;
SolveEquation(A, B, total - A[size]*j , size-1, arr_size, coins+j);
}
return min_coins;
}
}
- radhika.nitk July 17, 2012{
#include <iostream>
#include <stdio.h>
bool checkForSum(int k, int n, int size, int* A, int start)
{
if(k == 0 && n == 0)
return true;
if(k == 0 && n > 0)
return false;
if(n < 0 )
return false;
if(start >= size)
return false;
printf("\n n %d k %d start %d A[start] %d \n", n, k, start, A[start]);
if(checkForSum(k-1, n- A[start], size, A, start +1))
{
printf("\n %d \n", A[start] );
return true;
}
else
{
return checkForSum(k,n, size, A, start+1);
}
}
int main()
{
int A[5] = {4, 1, 2, 0, 1};
checkForSum(3, 4, 5, A, 0 );
return 1;
}
}
- radhika.nitk July 17, 2012Do binary search on first row. Find index of last one in that row. Then for other rows check if one present on index+1 if no then check on next row if one is there then for binary search starting point would be index+1 rather than 0. IT will take time less than mlogn
{
#include <iostream>
#include <stdio.h>
int BinarySearch(int* A, int start, int end)
{
int mid = (end+start)/2;
if(start == end)
return start;
if(A[mid+1] == 1)
{
return BinarySearch(A, mid+1, end);
}
else
{
return BinarySearch(A, start, mid);
}
}
int MaxOnesInMatrixRow(int** matrix, int row_no, int start, int num_rows, int num_columns)
{
if(row_no == num_rows)
return start+1;
if(matrix[row_no][start+1] != 1)
{
return MaxOnesInMatrixRow(matrix, row_no+1, start, num_rows, num_columns);
}
else
{
int new_start = BinarySearch(matrix[row_no], start, num_columns);
return MaxOnesInMatrixRow(matrix, row_no+1, new_start, num_rows, num_columns);
}
}
}
- radhika.nitk July 17, 2012
I think it is n-way merge sort
- radhika.nitk February 08, 2015