Skip to content

Instantly share code, notes, and snippets.

@sbsatter
sbsatter / Count8.java
Created August 19, 2016 14:59
Given a non-negative int n, compute recursively (no loops) the count of the occurrences of 8 as a digit, except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4. Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12). count8(8) → 1 co…
public int count8(int n) {
if(n==0)
return 0;
int rem100=n%100;
int div=n/10;
int rem=n%10;
if(rem100==88){
return 2+count8(div);
}
@sbsatter
sbsatter / NestedParenthesis.java
Created August 19, 2016 15:27
Find nested parenthesis recursively
public boolean nestParen(String str) {
int i= str.indexOf('('), j=str.lastIndexOf(')');
if(i==-1 ^ j==-1){
return false;
}
if(i==-1 && j==-1)
return true;
return nestParen(str.substring(i+1,j));
}
@sbsatter
sbsatter / CountPairs.java
Created August 19, 2016 15:45
http://codingbat.com/prob/p154048 Count overlapping pairs in the form AxA where A has a pair!
public int countPairs(String str) {
if(str.length()<3)
return 0;
String sub=str.substring(0,3);
int n= checkSubstringForPair(sub);
return n+countPairs(str.substring(1,str.length()));
}
public int checkSubstringForPair(String sub){
if(sub.charAt(0)==sub.charAt(2))
@sbsatter
sbsatter / GroupSum
Created August 19, 2016 16:16
Classic backtracking problem: Recursion-2 > groupSum prev | next | chance Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? This is a classic backtracking recursion problem. Once you understand the recursive backtracking strategy in this problem, you can use the same patte…
public boolean groupSum(int start, int[] nums, int target) {
if(target==0){
return true;
}
if(start>=nums.length){
return false;
}
if(groupSum(start+1, nums, target-nums[start])){
return true;
}else{
@sbsatter
sbsatter / GroupSum5
Created August 19, 2016 16:50
Backtracking: GroupSum5- Coding bat Recursive 2 http://codingbat.com/prob/p138907
public boolean groupSum5(int start, int[] nums, int target) {
if(start>=nums.length){
return target==0;
}
if(nums[start]%5 == 0 && start<nums.length-1 && nums[start+1]!=1){
return groupSum5(start+1, nums, target-nums[start]);
}else if(nums[start]%5==0){
return(groupSum5(start+2, nums, target-nums[start]));
}else if(groupSum5(start+1, nums, target-nums[start])){
return true;
@sbsatter
sbsatter / TheCelebrityProblem.java
Created August 20, 2016 07:20
Geeks4Geeks celebrity problem
class GfG
{
// The task is to complete this function
int getId(int M[][], int n)
{
java.util.Stack<Integer> stack= new java.util.Stack<Integer>();
// Your code here
for(int i=0; i<n; i++){
stack.push(i);
class Mergesort{
public static void main(String ... args){
int [] array= {5, 4, 3, 2, 1, 0};
printArray(mergerSort(copyOf(array,0, array.length)));
}
static void printArray(int [] array){
for(int i: array){
System.out.print(i+" ");
}
@sbsatter
sbsatter / Quicksort.py
Created August 20, 2016 16:59
Quicksort algorithm in python
def partition(alist, first, last):
pivotValue= alist[first]
left= first+1
right=last
done= False
while not done:
while alist[left]<pivotValue and left<right:
left=left+1
@sbsatter
sbsatter / palyndrome.java
Created November 17, 2016 18:04
Easiest and fastest palyndrome checker
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s=sc.next();
/* Enter your code here. Print output to STDOUT.
@sbsatter
sbsatter / -
Created April 20, 2017 08:31 — forked from anonymous/-
System: Host: sbsatter Kernel: 4.4.0-72-generic x86_64 (64 bit gcc: 5.4.0)
Desktop: Cinnamon 3.2.7 (Gtk 3.18.9-1ubuntu3.2) dm: mdm Distro: Linux Mint 18.1 Serena
Machine: System: Gigabyte product: N/A
Mobo: Gigabyte model: H170M-D3H-CF v: x.x Bios: American Megatrends v: F6 date: 03/07/2016
CPU: Quad core Intel Core i5-6500 (-MCP-) cache: 6144 KB
flags: (lm nx sse sse2 sse3 sse4_1 sse4_2 ssse3 vmx) bmips: 25535
clock speeds: min/max: 800/3600 MHz 1: 800 MHz 2: 800 MHz 3: 800 MHz 4: 800 MHz
Graphics: Card: Intel Sky Lake Integrated Graphics bus-ID: 00:02.0 chip-ID: 8086:1912
Display Server: X.Org 1.18.4 drivers: intel (unloaded: fbdev,vesa)
Resolution: 1366x768@59.79hz