DEV Community: Jasraj Chouhan

Two sum problem solution in easy way [Day-03]

Jasraj Chouhan — Thu, 09 May 2024 09:24:26 +0000

Today is day 3 for our dsa series. Today we discussed about two sum problem which is very important to understand the use of hashmap and how to optimes the time complexity of solution.

Problem
you give an array num of length n and a target value k. you find out all the no of pair which sum is equal to k.

Input

num = [1,2,3,-1,4] , n = 5 , k = 5
Output
4

*Expiation *
1 + 2 + 3 + (-1) = 5
2 + 3 = 5
1 + 4 = 5
2 + (-1) + 4 = 5

Brute Approch
we point the two pointer i , j at index 0 of array. and move in complete in array and find out pair which sum of (num[i] + num[j) is equal to target value k if yes then increase the counter;

Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      System.out.println("Enter the size of an array");

      Scanner sc = new Scanner(System.in) ;

      int n = sc.nextInt();

      int a[] = new int[n] ;


      // 1,2,3,-1,4 


      // take the input from user for array's element
      for(int i = 0; i < n; i++) a[i] = sc.nextInt() ;

      System.out.println("Enter the value of k");
      int k = sc.nextInt() ;

      System.out.println("total no of pair is : " + totalPair(a , n , k));

  }


  public static int totalPair(int a[] , int n , int k) {
    int counter = 0;

    for(int i = 0; i < n ; i++) {
      for(int j = 0; j < n; j++) {
        if(a[i] + a[j] == k) counter++;
      }
    }

    return counter ;
  } 

}

Time complexity of above algorithm is O(N*N) or O(N^2) because we travel every time in loop for every iteration.

*If we optimes the above algorithm so we can use hashmap data structure which store the value and its frequency *

Approch

When we move in array then ele = a[i] we find out the a element which have value is (target - ele) in hashmap if yes then increase the counter ;

Code


import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of the array");
        int n = sc.nextInt();

        int[] arr = new int[n];
        System.out.println("Enter the elements of the array");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("Enter the value of k");
        int k = sc.nextInt();

        System.out.println("Total number of pairs is: " + totalPair(arr, k));
    }

    public static int totalPair(int[] arr, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;

        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for (int num : arr) {
            int complement = k - num;
            if (map.containsKey(complement)) {
                count++;

            }
        }

        return count ;
    }
}

Time complexity is O(n) and space Complexity is also O(n) because we use extra space.

if you any doubt related to this article please comment us.

swap the value of two variable Four method [Day-02]

Jasraj Chouhan — Wed, 08 May 2024 22:28:54 +0000

This is day 2 of learn DSA in this particular blog we learn about the how the swap the value of two variable.

swap the value of two variable is important concept because many of sorting algrorithm used this conecpt for eg. Bubble Sort , Insertion Sort and many algorithm.

We discussed three to four method swap the value of two variable.

input : 2 4
Output : 4 2
input : 5 0
Output : 0 5

Note : Second , third and fourth method is asked in many interviews so clearly understand these algorithm.

First Method
Take four variable and store the value of 2 variable into 2 another variabel and print this . This is word method because we take extra space.


import java.util.Scanner;

public class Second {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter any two numbers");
        int firstNum = sc.nextInt();
        int secondNum = sc.nextInt();

        int first = secondNum;
        int second = firstNum ;

        System.out.println("After swaping  " + first + " " + second);
        sc.close();


    }
}

Second Method
use the third variable and swap the value .
Approach :
take a third variable temp initially temp has null value or say nothing have a value .
in first step give value of first variable to temp.
in second step give value of first varibale to second num .
in third step give value of second variable to temp variable.

Code
import java.util.Scanner;

public class Second {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter any two numbers");
        int firstNum = sc.nextInt();
        int secondNum = sc.nextInt();

        int temp ;
        temp = firstNum ;
        firstNum = secondNum ;
        secondNum = temp ;

        System.out.println("After swaping  " + firstNum + " " + secondNum);
        sc.close();


    }
}

Third Method:
without using any third variable to swap the value of two variable.
Approach :
firstNum = fristNum + secondNum;
secondNum = fristNum - secondNum ;
firstNum = fristNum - secondNum;

import java.util.Scanner;

public class Second {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter any two numbers");
        int firstNum = sc.nextInt();
        int secondNum = sc.nextInt();

        firstNum = firstNum + secondNum ;
        secondNum = firstNum - secondNum ;
        firstNum = firstNum - secondNum ;

        System.out.println("After swaping  " + firstNum + " " + secondNum);
        sc.close();


    }
}

*Fourth Method *
This method is awsome it take less time to another method which we discussed above. we use the concept of bit manipulation.
we take the xor(^) of two numbers.
But first understand xor (^) operator

0 ^ 0 = 0 1 ^ 1 = 0 1 ^ 0 = 1 0 ^ 1 = 1

xor(^) of two different value is always 1 but xor(^) of two same thing is 0

Code

import java.util.Scanner;

public class Second {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter any two numbers");
        int firstNum = sc.nextInt();
        int secondNum = sc.nextInt();

        firstNum = firstNum ^ secondNum ;
        secondNum = firstNum ^ secondNum ;
        firstNum = firstNum ^ secondNum ;

        System.out.println("After swaping  " + firstNum + " " + secondNum);
        sc.close();


    }
}

if you have any doubt please tell us in comment I try to answer your question.

if you not familiar with our dsa series please follow me .

Print Digits of a number Beginners Coding Problem [Day-01]

Jasraj Chouhan — Wed, 08 May 2024 07:50:50 +0000

Hello dear my fellow friends today we discussed the how the print digits of a number in reaverse order.

Example or test cases

input : 1234
output : 4 3 2 1

input : 2390
output : 0 9 3 2

Approch

1.we take the modula of the number by 10 then we get always last digit of a number.

for example

num = 123
divide the num by 10
num % 10 = 3

num = 4562
num % 10 = 2

it means we clear about this concept if we required last digit of number then we take the modula of number by 10 and get the last digit .

In second we required next digit so we reduced the num by num/10

for example
num = 123
num % 10 = 3

num = num / 10
num = 123 / 10
num = 12

ok then our num is reduced from 123 to 12

We repeat both the step until num is not zero.

ok let's move for coding section I used c, cpp, java and python language if you comming from another programming language so you can convert this code into your progamming language.

java

import java.util.Scanner;
class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Enter a number");
        Scanner sc = new Scanner(System.in) ;
        int n = sc.nextInt();       //take input from user

        printDigits(n) ;        // call the printDigits function which print the all digits of a number in reverse order


    }

    public static void printDigits(int n) {

        while(n != 0) {
            System.out.print(n % 10 + " ");
            n /= 10;
        }
    }
}


#include <stdio.h>

void printDigits(int n) {
    while(n != 0) {
        printf("%d ", n % 10);
        n /= 10;
    }
}

int main() {
    printf("Enter a number: ");
    int n;
    scanf("%d", &n);

    printDigits(n);

    return 0;
}

cpp

#include <iostream>

void printDigits(int n) {
    while(n != 0) {
        std::cout << n % 10 << " ";
        n /= 10;
    }
}

int main() {
    std::cout << "Enter a number: ";
    int n;
    std::cin >> n;

    printDigits(n);

    return 0;
}

python

def print_digits(n):
    while n != 0:
        print(n % 10, end=" ")
        n //= 10

n = int(input("Enter a number: "))
print_digits(n)

javascript

function printDigits(n) {
    while (n !== 0) {
        process.stdout.write(n % 10 + " ");
        n = Math.floor(n / 10);
    }
}

console.log("Enter a number:");
let n = parseInt(prompt());
printDigits(n);

if you have any doubt related to this question please comment your doubt.

if you are beggerner in coding please follow this series we covered complete dsa.

dsa #programming #daydsa Sure, here you go:

codingtips #programmerlife #techblog #learntocode #codegoals #codenewbie #algorithm #datastructures #pythonprogramming #javascript #webdevelopment #cplusplus #java #computerscience #developercommunity #codersofinstagram #codingisfun #programminghumor #codingbootcamp #codingjourney #codechef #hackerrank #codeforces #leetcode #interviewprep #softwareengineering #codingchallenge #100daysofcode #programmingquotes #codequality #debugging #codeart #codinglife #programmingmemes #womenintech #programminglanguage #codingproblems #codinginterview #frontenddevelopment #backenddevelopment #fullstackdeveloper #codebug #techcommunity #devlife #codingtutorial #codingislove #codingschool #programmingtips #opensource #programmingbooks #codingclub #codewars #programminglogic #codeaddict #codingworld #programmingthoughts #codingislife #programmerrepublic #codingforbeginners #codingwisdom #codingiscreativity #programmingeducation #codingisart #codingfromscratch #codingisawesome #programminglife #codingstudio #programming101 #codinginspiration #codered #codingmindset #programmingfun #codingisbeautiful #codingiscool #codingworld #codingtherapy #programmingjourney #codeyourfuture #codingexplained