supermonk247
BAN USERYes, For small N there is no solution.. after N=10, there is solution
- supermonk247 April 11, 2015Standard NQueen problem. But due to the Knight movement .. there will be no solution.
public class NQueens {
ArrayList<QNode> res = new ArrayList<QNode>();
public NQueens(){
}
public void printLocations(QNode[][] mat, int n){
// System.out.println(n);
if(n==mat.length){
printMat(mat);
}else{
for(int i=0;i<mat[0].length;i++){
mat[n][i] = new QNode(n,i);
//System.out.println(n + ""+i);
if(isFree(mat[n][i], mat)){
res.add(mat[n][i]);
printLocations(mat, n+1);
res.remove(mat[n][i]);
}
}
}
}
private void printMat(QNode[][] mat) {
for(int i=0;i<mat.length;i++){
for(int j=0;j<mat[0].length;j++){
if(res.contains(mat[i][j])){
System.out.printf("Q\t");
}else{
System.out.printf("*\t");
}
}
System.out.println();
}
System.out.println("----------------------------------");
System.out.println();
}
private boolean isFree(QNode node, QNode[][] mat) {
for(QNode cell : res){
if(cell.i == node.i || cell.j == node.j || ( Math.abs(node.i-cell.i)== Math.abs(node.j-cell.j))
||
(Math.abs(node.i-cell.i)==2 && Math.abs(node.j-cell.j)==1) ||
(Math.abs(node.i-cell.i)==1 && Math.abs(node.j-cell.j)==2)
){
return false;
}
}
return true;
}
public static void main(String[] args) {
NQueens q = new NQueens();
q.printLocations(new QNode[4][4], 0);
}
}
class QNode{
int i;
int j;
public QNode(int i, int j){
this.i = i;
this.j = j;
}
}
Not sure if I maintained O(1) :(
- supermonk247 February 25, 2015public class Majority {
public static int findMajority(String s){
int[] arr = new int[s.length()];
for(int i=0;i<s.length();i++)
arr[i] =s.charAt(i)-'0';
return findMajority(arr, 0, s.length()-1);
}
public static int findMajority(int[] arr, int st, int end){
if(st>end)
return -1;
if(end-arr[end]<2)
return -1;
int mid= st+(end-st)/2;
if(arr[mid]==arr[mid+1]){
int temp = arr[mid];
int k =mid;
int j=mid+1;
int count=0;
while(k>=st && arr[k]==temp){
count++;
k--;
}
while(j<=end && arr[j]==temp ){
count++;
j++;
}
if(count>=4)
return temp;
}
int left = findMajority(arr, st, mid);
if(left==-1)
return findMajority(arr, mid+1, end);
return left;
}
/**
* Find popular item in sorted array of natural numbers.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
* @param args
*/
public static void main(String[] args) {
// String x = "123444445678";
// System.out.println(findMajority(x));
String x1 = "123456789999";
System.out.println(findMajority(x1));
}
}
public class SubStringAddition {
public static void findSubStringAddition(int[] arr, int value){
for(int i=0;i<arr.length;i++){
int sum=0;
for(int j=i;j<arr.length;j++){
sum+=arr[j];
if(sum==value){
print(arr, i, j);
}
}
}
}
public static void print(int[] arr, int st, int end){
for(int i=st;i<=end;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int [] arr = {1, 7 ,6 ,3, 5, 8, 9 };
findSubStringAddition(arr, 16);
}
}
I believe this should work for all combinations..
- supermonk247 September 12, 2013package com;
import java.util.ArrayList;
public class SumNumbers {
public static void main(String[] args) {
findSumNumbers("17521");
}
private static void findSumNumbers(String string) {
if (string.length()<3) return;
char[] arr = string.toCharArray();
ArrayList<Node> res = basic(arr);
if(string.length()>3){
for(int i=3;i<arr.length;i++){
res = update(res,arr[i]);
}
}
for(Node I:res){
//System.out.println(I.str[0]+" + " + I.str[1] +" = "+I.str[2]);
if((Integer.parseInt(I.str[0])+Integer.parseInt(I.str[1]))==Integer.parseInt(I.str[2])){
System.out.println("Sucess " + I.str[0]+" + " + I.str[1] +" = "+I.str[2]);
}
}
}
private static ArrayList<Node> update(ArrayList<Node> res, char c) {
ArrayList<Node> update = new ArrayList<>();
for(Node node:res){
for(int j=0;j<node.str.length;j++){
for(int i=0;i<node.str[j].length()+1;i++){
Node temp = new Node();
temp.str[0]=node.str[0];temp.str[1]=node.str[1];temp.str[2]=node.str[2];
temp.str[j]=node.str[j].substring(0,i)+c+node.str[j].substring(i,node.str[j].length());
update.add(temp);
}
}
}
System.out.println(update.size()+" "+c);
return update;
}
private static ArrayList<Node> basic(char[] arr) {
ArrayList<Node> bas = new ArrayList<>();
for(int i=0;i<3;i++){
Node temp = new Node();
for(int j=0;j<3;j++){
int k =(j+i)%3;
temp.str[j]=arr[k]+"";
}
bas.add(temp);
}
System.out.println(bas.size());
return bas;
}
}
package com;
import java.util.LinkedList;
public class password {
public static void findNeighbours(int[][] pass, String num,int len){
LinkedList<Integer> li = new LinkedList<>();
li.add(Integer.parseInt(num));
for(int i=0;i<len;i++){
String back = num.substring(0,i);
String digit = num.substring(i,i+1);
String front = num.substring(i+1,len);
LinkedList<Integer> dd = findallowed(pass, Integer.parseInt(digit));
//li.add(Integer.parseInt(back+digit+front));
for(int j=0;j<dd.size();j++){
li.add(Integer.parseInt(back+dd.get(j)+front));
}
}
for(int i=0;i<li.size();i++){
System.out.println(li.get(i));
}
}
public static LinkedList<Integer> findallowed(int[][] pass, int digit){
LinkedList<Integer> ret = new LinkedList<>();
boolean f = false;
int k=0,h=0;
for(int i=0;i<pass.length;i++){
for(int j=0;j<pass[0].length;j++){
//System.out.println(pass[i][j]);
if(pass[i][j]==digit){
f=true;
k=i;h=j;
}
}
}
if (f==false)
return null;
else{
if(k+1<pass.length&& k+1>=0&&h<pass[0].length&& h>=0)
ret.add(pass[k+1][h]);
if(k-1<pass.length&& k-1>=0&&h<pass[0].length&& h>=0)
ret.add(pass[k-1][h]);
if(k<pass.length&& k>=0&&h+1<pass[0].length&& h+1>=0)
ret.add(pass[k][h+1]);
if(k<pass.length&& k>=0&&h-1<pass[0].length&& h-1>=0)
ret.add(pass[k][h-1]);
return ret;
}
}
public static void main(String[] args) {
int[][] pass ={{1,2,3},{4,5,6},{7,8,9}};
findNeighbours(pass,1178+"",4);
}
}
do longest common subsequence as per CLRS but reverse either the column or row of characters..
- supermonk247 November 26, 2012
I am guessing since both list and ith element are passed in function.
- supermonk247 May 30, 2015This problem is more like find Median from a list of elements.
so if we want O(n) then maintain two Heap ( Max Heap of elements below i and Min Heap of elements above i )
and we can run over the list of elements once and find the ith popular element