DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

How does AI transform chaos engineering from an experiment into a critical capability? Learn how to effectively operationalize the chaos.

Data quality isn't just a technical issue: It impacts an organization's compliance, operational efficiency, and customer satisfaction.

Are you a front-end or full-stack developer frustrated by front-end distractions? Learn to move forward with tooling and clear boundaries.

Developer Experience: Demand to support engineering teams has risen, and there is a shift from traditional DevOps to workflow improvements.

Related

  • Memory Leak Due to Uncleared ThreadLocal Variables
  • Beyond Java Streams: Exploring Alternative Functional Programming Approaches in Java
  • Java Enterprise Matters: Why It All Comes Back to Jakarta EE
  • How to Identify the Underlying Causes of Connection Timeout Errors for MongoDB With Java

Trending

  • Monorepo Development With React, Node.js, and PostgreSQL With Prisma and ClickHouse
  • Revolutionizing Software Development: Agile, Shift-Left, and Cybersecurity Integration
  • How to Improve Software Architecture in a Cloud Environment
  • OTel Me Why: The Case for OpenTelemetry Beyond the Shine
  1. DZone
  2. Coding
  3. Java
  4. How to Find the Optimal Solution for Single Number LeetCode Problem?

How to Find the Optimal Solution for Single Number LeetCode Problem?

Java solution for the single number problem using different approaches in Java and their analysis.

By 
Tarun Telang user avatar
Tarun Telang
DZone Core CORE ·
Updated Aug. 13, 21 · Code Snippet
Likes (3)
Comment
Save
Tweet
Share
21.4K Views

Join the DZone community and get the full member experience.

Join For Free

Problem Specification

https://leetcode.com/problems/single-number

Solution Approaches

1. Using Brute Force

The most obvious solution is to start with a Brute Force approach. In this approach, you can compare each number with the rest of the numbers in the array. In case you find a duplicate proceed to the next number and in case you don’t find a duplicate you return the current number as a Single Number. 

Below is the Java code for the same.

Java
 
class Solution { 
    public int singleNumber(int[] numbers) {
    // ----------------------------------------------
    // Brute Force -- O(n**2),  Space Complexity O(1)
    // ----------------------------------------------
    int len = numbers.length;
    boolean isTwice = false; 
    for (int i=0; i < len; i++) { 
       isTwice = false;
       for (int j=0; j<len; j++) {
         if (isTwice) break;
         if (i != j)
            if(numbers[i] == numbers[j]) 
                isTwice = true
       }         
       if(!isTwice) return numbers[i];
     }
     return numbers[len - 1];
  }
}


2. Using Sorting

To improve on the brute force approach you can apply sorting first to avoid going back and forth in the array while comparing each number with the rest of the numbers in the array. After sorting you would just need a single pass on the array of numbers to find a single number. Sorting can be done in O(NlogN) time, this approach is faster than the above one. Also, we don’t need additional space so the space complexity would be O(1). Please find the Java code of the solution for this approach below.

Java
 
class Solution { 
    public int singleNumber(int[] numbers) { 
    // -----------------------------------------------------------
    // Sorting -- Time Complexity O(nlogn), Space Complexity O(1)
    // -----------------------------------------------------------
    Arrays.sort(numbers);
    int len = numbers.length;
    int result = numbers[len - 1]; 
    int i = 0;
    while (i < len - 2) {
      if (numbers[i] == numbers[i+1]) {
        i = i + 2;
      } else {
        return numbers[i];
      }
    }
    return numbers[len - 1];
  }
}


3. Using Hash Map

In order to reduce the time complexity further, you can instead use a HashMap. This way you don’t need to sort the array. This approach improves a space/time tradeoff to improved performance. This has a time complexity of O(N) whereas its space complexity is also O(N). Below is the Java code for this approach.

Java
 
class Solution { 
    public int singleNumber(int[] numbers) { 
        // -------------------------------------------------------------
        // Using Hash Map -- Time Complexity O(n), Space Complexity O(n)
        // -------------------------------------------------------------
        Map<Integer, Boolean> map = new HashMap();

        for (int number: numbers) {
           map.put(number, !map.getOrDefault(number, false));   
        }

        for (Map.Entry<Integer, Boolean> entry: map.entrySet()) {
           if (entry.getValue()) {
              return entry.getKey();
           }
        }
        return Integer.MIN_VALUE;
    }
}


4. Optimal Solution

The most optimal solution does not use any additional space and has linear time complexity. The idea is to start with 0 and apply use logical eXclusive OR (XOR) operator on the entire array. The final result would be the desired single number to be returned. Please find the Java code for this approach below.

Java
 
class Solution { 
  // -----------------------------------------------------
  // Using XOR Bit Manipulation -- 
  //         Time Complexity: O(n), Space Complexity: O(1)
  // -----------------------------------------------------
  public int singleNumber(int[] numbers) {
    int result = 0;
    for (int number: numbers) {
       result ^= number; // Logical XOR operator 
    }
    return result;
  }
}


Java (programming language)

Published at DZone with permission of Tarun Telang. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Memory Leak Due to Uncleared ThreadLocal Variables
  • Beyond Java Streams: Exploring Alternative Functional Programming Approaches in Java
  • Java Enterprise Matters: Why It All Comes Back to Jakarta EE
  • How to Identify the Underlying Causes of Connection Timeout Errors for MongoDB With Java

Partner Resources

×

Comments

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • [email protected]

Let's be friends: